What are the examples (applications) of the MIPs in which the objective function has nonzero coefficients for only continuous variables?

Question

I'm specifically looking for real applications of the following form of MIP:

$$\max\,Cx$$

subject to:

\begin{align}Ax +By &= D\\Ax &= E\\By &= F\\ x &\ge 0\\ y &\in \mathbb{Z}^{+}\end{align}

Part of these constraints can be excluded. The important thing for me is to have integer (or binary) variables in the constraints but not objective function.

Answer 1

An example in the field of public transport is the Periodic Event Scheduling Problem, which is used to model periodic timetabling problems. The objective is typically to minimize the total travel time of passengers, which can be represented as a weighted sum of continuous variables representing driving, dwelling and transfer times. The constraints impose lower and upper bounds for various activity durations (e.g. minimum driving times and minimum separation times between services). To ensure that the timetable is periodic, integer variables are needed in these constraints, but these do not appear in the objective function.

Answer 2

An example can be shipping products from plants ($i$) to warehouses ($j$), where you are interested in minimizing the total transportation cost subject to some constraints. Now, if you calculate transportation cost based on the amount you ship from plant to warehouse ($x_{ij}$), then you can have constraints where this amount is bounded by the number of trucks you need to use to ship your products between locations ($y_{ij}$). So, your constraint can be something like the following:

$$ x_{ij} \le C_{ij}y_{ij}$$ $$x_{ij} \ge 0, y_{ij} \in \mathbb{Z}^+$$

where $C_{ij}$ was the capacity of the truck shipping products from plant $i$ to warehouse $j$ (I used it that way for generality).

Also (as I said in a comment), take a look at this answer. Anytime you have a min/max constraint, introduce binary variables to linearize it. Those binary variables are not in your objective function!

Answer 3

If you are dealing with feasibility problems then you won't worry about an objective function as you only need one feasible solution. A classical feasibility problem is a Sudoku. A ($9\times 9$) Sudoku can be formulated as a MIP in the following way:

$$\begin{aligned} & {\text{minimize}} & &0 \\ & \text{subject to} & & \sum_{i=1}^9 x_{ijk} = 1 \; \text{ for } j,k = 1, \ldots, 9\\ && & \sum_{j=1}^9 x_{ijk} = 1 \; \text{ for } i,k = 1, \ldots, 9\\ && & \sum_{k=1}^9 x_{ijk} = 1 \; \text{ for } i,j = 1, \ldots, 9\\ && & \sum_{i=3p-2}^{3p} \sum_{j=3q-2}^{3q} x_{ijk} = 1 \; \text{ for } k= 1, \ldots, 9 \text{ and } p,q = 1,\ldots,3\\ \end{aligned}$$

The objective function does not play a role since there is no "best" Sudoku solution. You only need a feasible one. You could even change the objective to max $x_{123}$ for example, even though this would not be in the sense of your question since you asked for problems where the objective coefficients of the integer variables are 0.

The Sudoku is just one example. The same also holds for every other feasibility problem.

Answer 4

To complete @EhsanK's answer, a relevant yet more general class of problems is the $p$-median problem, which is a variant of facility location problems aiming to minimize total transportation costs via locating only $p$ facilities. In this class of problems, a facility must be located (i.e., binary decision variables) before allowing transporting goods from it to customers (i.e., continuous decision variables). A simple variant of the problem is modeled as follows:

$$ \min\,\sum_{i \in C,j \in F}h_{i}c_{ij}x_{ij}$$ subject to: $$ \sum_{j \in F}x_{ij}=1\qquad \forall i \in C$$ $$ x_{ij} \le y_{j} \qquad \forall i \in C\,\&\,\forall j \in F$$ $$ \sum_{j \in F}y_{j}=p$$ $$0 \le x_{ij} \le 1\qquad \forall i \in C\,\&\,\forall j \in F$$ $$y_{j} \in \{0,1\}\qquad \forall j \in F$$

Answer 5

A couple of related examples (with a minimization objective, but the idea is the same):

• This structure comes up in many minimax optimization problems. Say you have binary/integer variables $x_i$ and corresponding costs $c_i$, and you want to minimize a "bottleneck" cost: $$\min [\max_{i} \{c_i x_i\}]$$ You would then introduce a continuous variable $y$, add constraints $y \geq c_i x_i$ for all $i$, and instead solve $\min y$.
• In this approach to school bus scheduling by Zeng et al., the total number of buses required is minimized as a continuous variable, but all of the scheduling variables in the constraints are binary (see p. 7 of linked paper).

Answer 6

A problem that sometimes arises in logistics is to find a minimum cost shipping schedule from warehouses to customers (think min cost flow network) with a side constraint that each customer must receive deliveries from at most $K$ sources, where $K$ is an integer (typically small, say 2). Binary variables are used to signal which sources are supplying which customers, but do not appear in the objective.

I believe I've seen similar structures in work allocation models, where the "customers" are projects, the "delivery quantity" is time/effort devoted to the project, the sources are workers and the binary variables are used to limit either how many projects a single worker can be asked to contribute to or how many workers can be asked to share a single project (or both).

Answer 7

You can find lots of applications of MIPs in the explained form in the engineering fields. As an example, you can look at topology and size optimization problems in the design of structures in the field of civil or mechanical engineering. Where in the objective function you have the volume of the structure ($V = \sum l_i \cdot A_i$) and in the constraints, you have both continuous and binary variables for all the elements. Continuous variables, for example, can explain the cross-sectional area of each member and binary variables can be an indicator of whether you have an element in the specific location of the structure or not. In paper [1], the authors explained this formulation.

---

_Reference

_{[1] Kanno, Yoshihiro, and Xu Guo. "A mixed integer programming for robust truss topology optimization with stress constraints." International Journal for Numerical Methods in Engineering 83.13 (2010): 1675-1699.}