7

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?

Peter Mortensen
  • 147
  • 7
Brannon
  • 900
  • 2
  • 12

2 Answers2

9

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.

prubin
  • 39,078
  • 3
  • 37
  • 104
  • 3
    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) – fontanf Apr 07 '22 at 19:24
  • 1
    @fontanf your comment could be a good answer (if you added a reference or developed a bit more) – Kuifje Apr 08 '22 at 12:16
5

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

RobPratt
  • 32,006
  • 1
  • 44
  • 84