2
$\begingroup$

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?

$\endgroup$

1 Answer 1

-2
$\begingroup$

There are indeed several problem domains where researchers have investigated the use of mixed-integer programming (MIP), which combines both continuous (real-valued) and discrete (integer) variables, to make problem-solving more computationally tractable. Here are a few examples:

1. Vehicle Routing Problems (VRP): In vehicle routing problems, we need to decide the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers. Typically, the decision variables are binary (0 or 1), indicating whether a route is selected or not. However, the problem can become more tractable by allowing the fleet size or the quantity of goods in a vehicle to be continuous.

2. Production Planning and Scheduling: In these problems, the objective is often to minimize costs or maximize production efficiency. Continuous variables could represent quantities of raw materials or products, while discrete variables could represent decisions such as the on/off status of machines. The flexibility of considering some variables as continuous can help to obtain better solutions.

3. Energy System Optimization: In the optimization of energy systems (for example, smart grid management), variables could be treated as continuous (like the amount of energy generated or consumed) or discrete (like the on/off status of a generator or a decision to invest in a certain technology). The use of continuous variables can make these problems easier to solve.

4. Facility Location Problems: In these problems, decisions need to be made about where to locate facilities (like factories or warehouses) to minimize costs or maximize service. By default, these problems are solved using binary variables (1 if a facility is opened at a location and 0 otherwise). However, allowing some facilities to be partially open could improve the computational efficiency of the problem.

5. Supply Chain Optimization: These problems can involve decisions like how much of a product to manufacture, where to store inventory, and how to transport goods. The decision variables can be either continuous (like the amount of goods to produce or transport) or discrete (like the decision to open or close a warehouse). The ability to treat some variables as continuous can make these problems easier to solve.

6. Portfolio Optimization: In finance, portfolio optimization involves choosing the best portfolio from a set of investment choices. Here, decision variables can be either continuous (like the proportion of wealth invested in an asset) or discrete (like the decision to include or exclude an asset from the portfolio). The use of continuous variables can often make these problems more tractable.

While the use of continuous variables can often make these problems easier to solve, it's worth noting that this approach can also result in solutions that are less precise or realistic. It's important to strike a balance between computational efficiency and the precision of the solution.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.