# Mixed-Integer Linear Programming With Free Variables

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.

• or.stackexchange.com/questions/6851/… Oct 8 at 10:19
• Interesting. Do you have any real-world examples of how this type of model arises? Oct 8 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. Oct 14 at 15:56

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.