how can I get the dual variable in MILP by savesolveroutput?

[覃岭]

hi johan:

  as we know, yalmip can't extract the dual variable in MILP, and I notice that you ever mentioned that this can be done by 'savesolveroutput' in sdpsettings instead, but can you show me some demo in detail?thanks.

 

x = sdpvar(1,10);

y = binvar(1,10);

obj = ...;

 

cons0=[.....];

cons1=[x==1];

solvesdp([cons0,cons1],obj);

 

lambda = dual(cons1);%return Nan

 

we hope extract the dual value from a MILP. Now I have to solve a MILP first for y*, and then solve a LP with y as sdpvar and fix it by y==double(y*). thus we have to solve the same problem twice and it is ineffective.

[Johan Löfberg]

There is no such thing as a dual, when you have a MILP, so I don't understand what you are trying to achieve.

x = intvar(5,1);

A = randn(25,5);

ops = sdpsettings('solver','cplex','savesolveroutput',1);

sol = solvesdp([A*x <= 10],sum(x),ops)
sol.solveroutput 

ans = 

           x: [5x1 double]

        fval: -17

    exitflag: 1

      lambda: []

      output: [1x1 struct]

sol.solveroutput.output

ans = 

          cplexstatus: 101

    cplexstatusstring: 'integer optimal solution'

           iterations: 21

            algorithm: 12

                 time: 0.0620

              message: 'Function converged to a solution x.'

Note that lambda is empty (dual), as no such info is returned by the solver (since it is an integer problem).

[覃岭]

Oh, let me make some explain:

I have a complicated model of a master problem and several subproblems. 

so I need do iteration to solve.

for each iteration: x is first solved in the master problem and passed to a subproblem. then we solve the subproblem, when this is done, I would like to get the dual variable of constraint [sub_x==double(master_x)] to generate a new cut constraint and add it to the master problem.

for i=1:MaxIterNum

 sub_x = sdpvar(1,10);

 sub_y = binvar(1,10);

 sub_obj = ...; 

 sub_cons0=[.....];

 sub_cons1=[sub_x==double(master_x)];%master_x is updated from master problem

 solvesdp([sub_cons0,sub_cons1],sub_obj);%MILP

 lambda = dual(sub_cons1);%here I can't get the lambda because subprblem is MILP, which used to correct the master_x later in form of cut

  ...%converge check

 master_const0=[.....];

 master_const1=[master_const1, ...+lambda*(master_x-double(sub_x))<=alpha ];%add a new cut

 solvesdp([ master_cons0, master_cons1], master_obj);

end

now lambda can't be extract from MILP subproblem, how can we get the dual variable lambda?My ineffective method is:

for i=1:MaxIterNum

 sub_x = sdpvar(1,10);

 sub_y = binvar(1,10);

 sub_obj = ...; 

 sub_cons0=[.....];

 sub_cons1=[sub_x==double(master_x)];%master_x is updated from master problem 

 solvesdp([sub_cons0,sub_cons1],sub_obj);%1. first solve a MILP for get the value sub_y

 

 sub_yR = double(sub_y);%2.convert it from binvar to sdpvar.

 sub_cons0LP=[.....];%3.replace all sub_y as  double(sub_y) in constr0 and objective

 solvesdp([sub_cons0LP,sub_cons1],sub_objLP);%4.now subproblem is a LP,solve it again

 lambda = dual(sub_cons1);%5.so lambda can be extract this time, my god....

  ......

my question is: can we do it in a better way instead of solve the subproblem twice?

many thanks to you and yalmip.

[Johan Löfberg]

If you want the duals associated with the solution when the binaries are fixed, I see no other way than solving the MILP first, and then solving an LP. MILP solvers do not return any dual information.

[覃岭]

so expensive calculation. anyway, thanks for your advise.