A typical optimization problem looks like the following, where $f$ represents the objective and $g$ the constraints:

$$ \text{maximize}~~~f(x1,\ldots,x_n)~~~\text{subject to}: \\ g(x_1,\ldots,x_n)=0, \\ x_1,\ldots,x_k\in \mathbb{Z}, \\ x_{k+1},\ldots,x_n\in \mathbb{R} $$

In particular, each decision variable should be either discrete or continuous.

In practice, we can often choose whether to treat a variable as discrete or continuous. For example, suppose there are several assets that have to be divided among heirs. By default the assets are discrete, so the variable that says "asset A goes to heir B" would be in $\mathbb{Z}$ (0 or 1). But when equal division is required, one may decide to share some of the assets, e.g. give 30% of asset A to heir B (and the rest to heir C). Since sharing is cumbersome, the number of such sharings should be bounded. So the problem becomes:

$$ \text{maximize}~~~f(x1,\ldots,x_n)~~~\text{subject to}: \\ g(x_1,\ldots,x_n)=0 \\ x_i\in \mathbb{Z} ~~~\text{for some $k$ indices $i\in[n]$,} \\ x_j\in \mathbb{R} ~~~\text{for the other $n-k$ indices $j\in[n]$} $$

The flexibility in choosing the continuous variables may potentially make the problem computationally easier.

I have a paper that takes advantage of this flexibility in the context of fair division. Besides this, I found this paper which studies a related problem in the context of vertex cover: a minimum fractional vertex cover in which the number of fractional vertices is minimized.

What are some other problems for which the variant with flexible variables has been studied?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.