I solved a MIP and now I cannot extract the duals!


There is no established general theory for the concept of duals (multipliers, Lagrange variables) in integer programming. Hence, no solver construct or return any such information. What some people are interested in is the dual variables when solving the linear relaxations. However, this is also problematic as the relaxation is an internal concept inside the solver with a lot of presolve, fixed variables, and cuts added to the model. However, the following model solves the MIP, and then solves a relaxation where the binary variables are relaxed from being binary, but forced to take on the value found when solving the MIP

A1 = randn(20,5);
A2 = randn(20,5);
b = rand(20,1);
c = randn(5,1);
x = sdpvar(5,1);
y = binvar(5,1);
Constraint = [A1*x + A2*y <= b];
optimize([Constraint, y == value(y)],c'*x,sdpsettings('relax',2));

Leave a Comment