Infeasible model with fixed feasible solution

GAMS
1

Hi,

I am having trouble with my model, as it appears to be integer infeasible (CPLEX error 1217), even when I fix the binary variable x(i,j,m) for specific links to 1, establishing a feasible solution. This model is a MILP formulation of a time dependent VRP, where the goal is to minimize the total time of all routes by choosing the best time interval m for each link (i,j).

I have analysed all the equations back and forth and they seem correct, I don’t understand why the model isn’t working. The presolver says:

“Bound infeasibility column x(3.1.2)”

I don’t understand what this means. Also, in the equation listing, for Eq5(3,1,1):

Eq5(3,1,1)… t(1) - t(3) - 500000000*x(3,1,1) =E= -499998691 ;

(LHS = -500000000, INFES = 1309 ****)

Shouldn’t t(1) =1309? Because x(3,1,1) and t(3) are already fixed in the formulation, so I don’t understand why does t(1) not respect the equation.
I will attach the model and the input files. There are descriptions throughout the depot to make it easier to understand

Any help would be much appreciated! Thank you in advance,

Manuel
TDVRP.gms (3.2 KB)
lsup.xlsx (13.2 KB)
tviag.xlsx (15.2 KB)

2

Hi Manuel,

the equation listing refers to the model at generation and not to its solution. If you do net set variable levels (via .l or .fx) default values (0) are assumed for the starting point.

I did not analyze your model in depth but I have no doubt that it is truly infeasible. Even when solved as an RMIP (integrality requirements of discrete variables relaxed) it is still infeasible.
There is no single way of figuring out the source of infeasibility. It very much depends on your knowledge and understanding of the original problem and it’s implementation as a model. A good way to go about analyzing infeasibilities is to provide a “feasible” solution to the problem by manually setting the variable level values (x.l(…) = …) and then generating the model with a full equation listing (option limrow=1e9;) This will flag the constraints that are infeasible with your “feasible” solution in the equation listing.
If you don’t want to work with your own feasible solution, you can ask solvers (e.g. Cplex) to provide you with the smallest set of constraints that are infeasible (you need to change the model type to rmip) via the iis option (see https://www.gams.com/latest/docs/S_CPLEX.html#CPLEXiis). You can also ask Cplex you give you the smallest relaxation of your model to make it feasible (look for option FeasOpt: https://www.gams.com/latest/docs/S_CPLEX.html#CPLEXfeasopt ).

I also noticed that you have huge coefficients in your model (~5e8). That often results in numerical difficulties. I don’t know what sort of values these huge coefficients reflect, but if this is related to some sort of bigM formulation, you should choose your bigM as small as possible.

I hope this helps!

Fred