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.