7
$\begingroup$

Suppose I run a relaxation of an MIP. If my result is all integers, I have achieved the same min/max that the MIP would achieve. However, what can I say if some portion of my result is integer?

If half my decision variables come out integer, does that mean that those specific variables would/should keep the same integer value for the MIP result? Does it depend on the problem? Is it different if I'm using boolean variables only?

I'm not sure what to look for to find research on this topic. What are the distinct keywords? What is the existing research on this topic?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
5
$\begingroup$

It depends. It is true for the weighted node packing problem, where $x_i$ is a binary decision variable for each node and you want to maximize $\sum_i c_i x_i$ subject to $x_i + x_j \le 1$ for all edges $(i,j)$.

Search phrase: "Nemhauser-Trotter local optimization theorem"

Nemhauser, G.L., Trotter, L.E. Vertex packings: Structural properties and algorithms. Mathematical Programming 8, 232–248 (1975). https://doi.org/10.1007/BF01580444

Improve this answer
$\endgroup$
1
  • $\begingroup$ That Nemhauser paper is spot-on! Thanks. $\endgroup$
    – Brannon
    Apr 7, 2022 at 16:16
9
$\begingroup$

It is possible that your model could become infeasible if you fixed the variables with integer values in the LP relaxation. Consider, for example, the problem of minimizing $y$ subject to the single constraint $7x - 3y = 5$, where $x$ and $y$ are nonnegative integer variables. The solution to the LP relaxation is $x=5/7,\, y=0.$ Fix $y=0$ and the problem becomes infeasible.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ Even if this is true, fixing the integer variables with integral values and solving the resulting sub-MILP (if enough variables have been fixed) is a classical MILP heuristic called Relaxation Enforced Neighborhod Search (RENS) $\endgroup$
    – fontanf
    Apr 7, 2022 at 19:24
  • 1
    $\begingroup$ @fontanf your comment could be a good answer (if you added a reference or developed a bit more) $\endgroup$
    – Kuifje
    Apr 8, 2022 at 12:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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