0

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 ?

LyLa
  • 1
  • 2
  • 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. – Charlie Vanaret Jan 16 '24 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? – A.Omidi Jan 16 '24 at 12:28
  • @CharlieVanaret, the LP optimum is lower than (or equal some times) the ILP optimum. So yes. Then, it makes sense ? – LyLa Jan 16 '24 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 Jan 16 '24 at 15:24
  • @CharlieVanaret, what I am kind of confused about is that the LP does not find a solution compared to the ILP one which does. I have an optimization problem where I have assignment requests. So for the same input and setting the LP is able to find not all the assignments compared to the ILP. Does this makes sense also ? – LyLa Jan 16 '24 at 16:00
  • The LP solver most likely finds fractional values for the discrete variables. Isn't that the case for you? That is the point of relaxation: when the integrality constraints are relaxed (e.g. $x \in [0, 1]$ instead of $x \in {0, 1}$), the problem becomes continuous and (generally) much easier to solve. – Charlie Vanaret Jan 16 '24 at 17:06
  • @CharlieVanaret, that is the case and I am getting an integral solution after rounding which is always less or equal to that of the ILP optimal solution. – LyLa Jan 16 '24 at 17:39
  • Probably because it's not feasible? – Charlie Vanaret Jan 16 '24 at 17:45
  • @CharlieVanaret, I checked the constraints and they are satisfied ! That is why i am confused. – LyLa Jan 16 '24 at 17:46
  • What's the status at the end of the ILP optimization? Is it completely solved (with small duality gap) or did the solver reach a time limit or a maximum number of nodes? – Charlie Vanaret Jan 16 '24 at 17:48
  • @CharlieVanaret, the optimality gap the solver reports is 0.0000%. – LyLa Jan 16 '24 at 17:50
  • Can you post the model? – Charlie Vanaret Jan 16 '24 at 19:11
  • 1
    @CharlieVanaret, this model is part of a joint collaboration with some people involved, I can provide you access on github. – LyLa Jan 16 '24 at 20:40
  • @LyLa, thanks for the clarification. What I can understand from the comments is that you have an MIQCP. You can solve this problem and have an optimal solution. 1) How do you ensure the solution you have is optimal? (e.g. have you tried a global solver to prove optimality). 2) To linearization the bi-linear term, do you try using this method in order to compare the result to the one you have by McCormick Envelopes? 3) Do you ensure that your model does not have a numerical issue? (e.g. very large coefficients, particularly BigM, or RHS, etc.) – A.Omidi Jan 17 '24 at 06:06
  • @A.Omidi, in my optimization model, the continuous variable $z$ is not multiplied by the binary variable $x$ as they are not linked in the constraints and the objective functions (for Q2)). The McCormick Envelopes is just where $x$ * $x$ appears only. For Q3) It seems that the solver which turns to be Gurobi (for Q1 optimality gap the solver reports is 0.0000%)) has a numerical issue with one instance of the problem as the others are fine. – LyLa Jan 17 '24 at 15:12
  • @LyLa if you haven't solved your problem, I'd like to have a look at the git repo ;) – Charlie Vanaret Jan 21 '24 at 07:11
  • @CharlieVanaret, I have solved it, thanks. – LyLa Feb 07 '24 at 19:55
  • Great! What was your problem? – Charlie Vanaret Feb 08 '24 at 11:13

0 Answers0