In the classic Mixed-Integer Linear Programming (MILP), the variables are fixed to be either integer or real. I am interested in the following MILP variant, where only one thing different from the classic MILP:

Let $n$ be the number of the MILP variables. One variable (any variable) is real and $n-1$ variables are integers. Notice that we can choose the real variable among all the variables.

  • Is this MILP variant NP-hard?
  • Is there a way to know how to choose the real variable to maximize the chances to reach a feasible solution?

One trivial but naive solution to this problem would run $n$ MILPs, such that for each MILP, one different variable is allowed to be real. The output is the best output among the $n$ running. This solution is NP-hard.

  • 3
    $\begingroup$ or.stackexchange.com/questions/6851/… $\endgroup$
    – Kuifje
    Oct 8 '21 at 10:19
  • 1
    $\begingroup$ Interesting. Do you have any real-world examples of how this type of model arises? $\endgroup$ Oct 8 '21 at 13:59
  • $\begingroup$ Yes: Dividing $n$ divisible objects among $m$ agents such that only one object can be shared and no agent envies another agent. $\endgroup$ Oct 14 '21 at 15:56

An alternative approach that requires only one solve and no modification of the model is to modify branch and bound to prune by integrality when at most one integer variable takes a fractional value (rather than the usual requirement that all integer variables are integer-valued). You would also need to disable any presolve/cut routines that assume integrality. You would also need to relax the feasibility checker.

  • $\begingroup$ This is a very elegant solution. In practice, do you think this is easier to do with classical solvers on the market (+ open source ones), compared to modifying the model ? $\endgroup$
    – Kuifje
    Oct 8 '21 at 13:01
  • $\begingroup$ Thanks. I would say that it is easier to modify the model, as in the link you provided, but I would expect modifying the algorithm to be more efficient. $\endgroup$
    – RobPratt
    Oct 8 '21 at 13:47

Here's another single-solve solution. Replace each original variable $x_n$ with a sum of two variables, $x_n=y_n + z_n$, where $y_n$ is integer-valued and $z_n\in [0,1]$. Now define $\lbrace z_1,\dots, z_n\rbrace$ to be a type 1 special ordered set (SOS1). Assuming the solver supports SOS1 constraints, you'll end up with a solution in which at least $n-1$ of the $z$ variables are 0, meaning at least $n-1$ of the $x$ variables are integer.


Your Answer

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

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