# Cost function value of relaxed ILP after rounding is less than or equal to the optimal one

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 ?

• 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. Commented Jan 16 at 11:52
• @LyLa, welcome to OR.SE. Would you elaborate more on a deterministic rounding scheme I developed and what you have tried to do? Commented Jan 16 at 12:28
• @CharlieVanaret, the LP optimum is lower than (or equal some times) the ILP optimum. So yes. Then, it makes sense ?
– LyLa
Commented Jan 16 at 15:22
• @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.
– LyLa
Commented Jan 16 at 15:24
• @CharlieVanaret, this model is part of a joint collaboration with some people involved, I can provide you access on github.
– LyLa
Commented Jan 16 at 20:40