9

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.

Samuel Bismuth
  • 173
  • 7
  • 3
    https://or.stackexchange.com/questions/6851/gurobi-how-to-add-a-constraint-to-make-there-be-only-one-non-integer-value/6852#6852 – Kuifje Oct 08 '21 at 10:19
  • 1
    Interesting. Do you have any real-world examples of how this type of model arises? – Mark L. Stone Oct 08 '21 at 13:59
  • Yes: Dividing $n$ divisible objects among $m$ agents such that only one object can be shared and no agent envies another agent. – Samuel Bismuth Oct 14 '21 at 15:56

2 Answers2

9

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.

prubin
  • 39,078
  • 3
  • 37
  • 104
  • Is there any paper associated with your answer? I would like to implement your solution and I would be happy to have some more details about the algorithmic part. – Samuel Bismuth Jan 31 '22 at 17:06
  • Sorry, but I'm not aware of any papers with this solution in them. SOS1 support in MIP solvers is fairly common, and if the solver does not explicitly support SOS1 you just make the $z_n$ binary and add the constraint $\sum_n z_n \le 1$. – prubin Jan 31 '22 at 19:14
  • If $z_n$ is binary-valued, every variable would be integer-valued, which is not what I am looking for. Maybe, you are aware of a paper that describes an efficient MILP with SOS1 support? – Samuel Bismuth Feb 01 '22 at 11:44
  • Sorry, my previous comment was in error. You would leave $z_n\in [0,1]$, add binary variables $w_n$ with $\sum_n w_n \le 1$, and add $z_n \le w_n$ for all $n$. SOS1 support is a function of the solver, not a model (MILP) property. – prubin Feb 01 '22 at 16:25
8

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.

RobPratt
  • 32,006
  • 1
  • 44
  • 84
  • 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 ? – Kuifje Oct 08 '21 at 13:01
  • 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. – RobPratt Oct 08 '21 at 13:47
  • Is there any paper associated with your answer? I would like to implement your solution and I would be happy to have some more details about the algorithmic part. – Samuel Bismuth Jan 31 '22 at 17:06