Infeasible model becomes feasible when a constraint is added

Answered

Sami Ozarik

• June 22, 2020 17:11

Hi, 

I am working on a VRP which has a binary variable x[i,j,k] (gets 1 if the arc between i,j is traveled by vehicle k). In the optimal solution found by Gurobi, x[0,10,2]=1. One alternative solution can be x[0,10,1]=1 meaning that another vehicle is travelling on that arc (there is no constraint on vehicles which would cause any infeasibility: Imagine there are two routes: A and B. Route A (B) is served by vehicle 1 (2) and there is no difference if route B (A) is served by vehicle 1 (2)). However, when I add the following line (coded in python) to the model, it becomes infeasible: 

m.addConstr(x[0,10,1] == 1, name='force1')

More interestingly, when the following two lines are added to the model (again in the optimal solution x[10,8,2]=1), it becomes feasible again (both models are run without any early termination criterion):

m.addConstr(x[0,10,1] == 1, name='force1')   => (same constraint)
m.addConstr(x[10,8,1] == 1, name='force2')

What can be the reason of such behavior? How can the model become feasible when extra constraints are added? 

Kind regards,

Sami Ozarik

 

 

 

 

0

• Official comment

  

  Simranjit Kaur

  Gurobi Staff

  • December 06, 2024 00:44

  This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
• 

  Eli Towle

  Gurobi Staff

  • June 22, 2020 21:20

  Hi Sami,

  Can you post a minimal working example of the code that reproduces this behavior? Also, which version of Gurobi are you using?

  Thanks,

  Eli

  0
• 

  Sami Ozarik

  • June 23, 2020 12:54

  

  

  

  Dear Eli,

  I am using Gurobi 9.0.1

  I think I found the problem. Most probably, it is caused by a small violation of a constraint in some cases.  

  Solution quality statistics for model netflow :
  Maximum violation:
  Bound : 0.00000000e+00
  Constraint : 1.00000000e-11 (time bucket assignment 3)
  Integrality : 0.00000000e+00
  Optimization Status: 2

  Without the additional constaints, the model is infeasible but when 'force2' is added in the model as in the previous example it becomes feasible with the violation of some other constraint ('time bucket assignment 3').  I guess the solution for me is to tighten primal, dual, and integrality tolerances. When I do that, the model becomes totally infeasible regardless of the additional constraints. Maybe you can confirm that this may be the explanation of such behavior. 

  Thanks for your help. 

  Kind regards,

  Sami

   

  0
• 

  Yuriy Zinchenko

  Gurobi Staff

  • October 09, 2020 22:42

  Yes, when the model is not well-posed from a numerical stand-point, this is not unexpected.

  0

Post is closed for comments.