I have a minimization problem for which I am having some misunderstandings and confusions with regard to some results I am getting for an ILP and its LP relaxation.

In the ILP I have two decision variables, one is binary while the other is continuous. There is a bilinear term involving the product of the binary variable in the ILP. I introduced the McCormick Envelopes to eliminate the bi-linear term in the relaxed version.

What I do not understand is that after a deterministic rounding scheme I developed, the value of the cost function is less than or equal to the optimal cost function value. Is that correct ? Am I missing something somehow ?

  • $\begingroup$ If I understood you correctly, the LP optimum is lower than the ILP optimum? Makes sense, the LP is a relaxation (the feasible set is larger), so you can achieve a lower objective value. $\endgroup$ Commented Jan 16 at 11:52
  • $\begingroup$ @LyLa, welcome to OR.SE. Would you elaborate more on a deterministic rounding scheme I developed and what you have tried to do? $\endgroup$
    – A.Omidi
    Commented Jan 16 at 12:28
  • $\begingroup$ @CharlieVanaret, the LP optimum is lower than (or equal some times) the ILP optimum. So yes. Then, it makes sense ? $\endgroup$
    – LyLa
    Commented Jan 16 at 15:22
  • $\begingroup$ @A.Omidi, the deterministic rounding technique is for assignment-type optimization models and it truly dependent on the problem structure I have for which the randomized rounding and other existing rounding techniques are not getting good results. I tried to build a tree of all possibilites from the fractional solutions. Then, I select the one with min cost. $\endgroup$
    – LyLa
    Commented Jan 16 at 15:24
  • 1
    $\begingroup$ @CharlieVanaret, this model is part of a joint collaboration with some people involved, I can provide you access on github. $\endgroup$
    – LyLa
    Commented Jan 16 at 20:40


Your Answer

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