9
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ or.stackexchange.com/questions/6851/… $\endgroup$
    – Kuifje
    Commented Oct 8, 2021 at 10:19
  • 1
    $\begingroup$ Interesting. Do you have any real-world examples of how this type of model arises? $\endgroup$
    – Mark L. Stone
    Commented Oct 8, 2021 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$
    – Samuel Bismuth
    Commented Oct 14, 2021 at 15:56

2 Answers 2

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Oct 8, 2021 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
    Commented Oct 8, 2021 at 13:47
  • $\begingroup$ 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. $\endgroup$
    – Samuel Bismuth
    Commented Jan 31, 2022 at 17:06
9
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Samuel Bismuth
    Commented Jan 31, 2022 at 17:06
  • $\begingroup$ 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$. $\endgroup$
    – prubin ♦
    Commented Jan 31, 2022 at 19:14
  • $\begingroup$ 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? $\endgroup$
    – Samuel Bismuth
    Commented Feb 1, 2022 at 11:44
  • $\begingroup$ 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. $\endgroup$
    – prubin ♦
    Commented Feb 1, 2022 at 16:25

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