Originally posted by: SystemAdmin

[BigInJapan said:]

I am in need to solve MILP problem and find Lagrange multipliers.
With CPLEX 11 optimal X finds perfect but LM sometimes (depends on incoming data) equal zeros. Why?
I tryied to setup DEPIND param, but I cannot understand what is going on with it.
What else I should setup?
Thanks.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[prubin said:]

I gather that by "Lagrange multipliers" you mean dual variables for constraints (as opposed to penalty multipliers in a Lagrangean relaxation).  Are you getting zero dual values for binding constraints?

/Paul
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[BigInJapan said:]

Hi, Paul!

Yes, you are exactly right - I meant dual variables.

How I can find out which constraint is binding and which is not? I thought I should use dual variables for this.
By sense I can see which constraint is binding and its dual variable sometimes equals 0. Sometimes all dual variables are zeros. Is it possible?

IMHO, CPLEX can through out some constraints to reduce the problem and for this constraints duals are always 0. Am I right?
So if I want to get all duals I have to switch off reduction. Params DEPIND, PREIND and may be others?
PS: my problem has much more constraints then variables, many constraints are redundant.

In case I am right - why CPLEX returns 0 in case when it cannot work out the dual variable? If NULL is not possible may be special value can help such as MaxInt.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[prubin said:]

[quote author=BigInJapan link=topic=1241.msg3519#msg3519 date=1246608490]
How I can find out which constraint is binding and which is not? I thought I should use dual variables for this.


In an LP, yes; in an ILP or MILP, no.  For one thing, it is possible that no constraints are binding.  Simple example:  maximize x1 + x2 subject to x1 + x2 <= 2.5, with both x1 and x2 binary.  The IloCplex class has a getSlacks method you can use to find out which constraints are binding.<br />
[quote author=BigInJapan link=topic=1241.msg3519#msg3519 date=1246608490]
By sense I can see which constraint is binding and its dual variable sometimes equals 0. Sometimes all dual variables are zeros. Is it possible?


First off, as seen in the example above, it is possible that no constraints are binding.  Second, even if a constraint is binding, it may have a zero dual value, because the corner may be degenerate when you factor in either integrality constraints or cuts.  Another simple example:

maximize 2*x1 + x2
s.t. 3*x1 + 2*x2 <= 5<br />x2 <= 1<br />x1, x2 integer.

The solution to the LP relaxation is (5/3, 0).  The branch-and-cut algorithm adds the cut x1 <= 1 and the new LP solution is (1,1), which is in fact the global optimum.  Both of the original constraints and the added cut intersect at (1,1), so the corner is degenerate, and there are multiple dual solutions to the node LP, including one extreme point solution to the dual where the shadow prices are 0 for the first constraint, 1 for the second constraint and 2 for the added cut.  My guess is that, with enough added cuts, it is entirely possible that a node LP with an integer-feasible solution has multiple original constraints binding at the optimum, all with zero shadow prices (the added cuts carrying the nonzero shadow prices).<br />
[quote author=BigInJapan link=topic=1241.msg3519#msg3519 date=1246608490]
IMHO, CPLEX can through out some constraints to reduce the problem and for this constraints duals are always 0. Am I right?
So if I want to get all duals I have to switch off reduction. Params DEPIND, PREIND and may be others?
PS: my problem has much more constraints then variables, many constraints are redundant.


You can turn off all the "extra" cuts, but branch-and-cut (or branch-and-bound) has to add cuts to separate nodes, and as the example above shows, that's enough to cause zero shadow prices.

[quote author=BigInJapan link=topic=1241.msg3519#msg3519 date=1246608490]
In case I am right - why CPLEX returns 0 in case when it cannot work out the dual variable? If NULL is not possible may be special value can help such as MaxInt.


CPLEX returns 0 because 0 is the correct value.  Consider the second example above.  If I change the RHS of the first constraint from 5 to 5 + epsilon (0 < epsilon < 1), no new integer-feasible points are added to the feasible region, so the objective value does not change.&nbsp; Therefore 0 is a correct dual value for the constraint.<br />
/Paul
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[BigInJapan said:]

1. ok, I understand why "<=" constraint's duals are 0, but how can "==" constraint's duals can be 0?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[prubin said:]

Node LP:

[tt]max  x1 + x2
s.t. x1 + x2 =  2
    x1      <= 1<br />          x2 <= 1[/tt]<br />(x >= 0).  The optimal solution (trivially) is x = (1,1).

Dual problem:

[tt]min 2*y1 + y2 + y3
s.t.  y1 + y2      >= 1
      y1      + y3 >= 1[/tt]

(y1 free; y2, y3 >= 0).  True or false: (0, 1, 1) is an optimal dual solution?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[BigInJapan said:]

(0, 1, 1) - is one of many optimal Y.
I understand, dual for "==" constraint can be 0 in case when this constraint exactly matches another.

Paul, I found this text on another forum:
CPLEX: Get the dual: Relax the MIP problem ?
sylvain.ross@gmail.com wrote:
Hello, I am trying to get the shadow price of some constraints of a
MIP problem with CPLEX 10.1.
>
When calling the GetDual(MyConstraint) on the cplex object, I get an
exception since my problem is a MIP. Although I think I should get the
relaxed LP problem and then get the dual, but I did not find a quick
way to get the optimal dual value associated with the constraint of my
relaxed program.
>
Is there a quick way to do this ?
>


If you're trying to get duals corresponding to the optimal solution, try
the following:

1. solve the MIP;
2. invoke cplex.solveFixed() to solve the LP with the integer variables
fixed at their optimal values;
3. use cplex.getDuals() to access the shadow prices.

Not sure if that works (haven't tried it myself). If not, you may have
to solve the MIP, change the lower and upper bounds on the integer
variables to equal the optimal values, solve again (should be an LP
now), then use getDuals().

/Paul
We failed to find out duals this way(last paragraph), some of them equal 0. But if we set UB=xmin+eps and LB=xmin-eps where eps = 0.01 - everything is ok. 0.000005 - is OK, but 0.000001 - is not OK, one of duals becomes equal 0.
So if we tighten the neighborhood we lose correct answer for dual problem.
What's wrong?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[frenky_ser said:]

Paul,
I will add a question of the topicstarter.
I have a trivial example

[b]Primal:[/b]
[b]min[/b] -5x1 + 5x2 + 0.1x3
[b]st[/b] x1 - x2 - x3 = 0

lb = (0 0 0) ub = (16 28 0.001)

My steps:
[b]1. Solve MILP -> change problem type on CPXPROB_FIXEDMILP -> reoptimize(lpopt)[/b]
/* I use callable library and this is my code /

  / create problem /
  [problemPtr, env, status] = calllib(cplexLibName, 'CPXcreateprob', EnvCPLEX, 0, 'testMilpProblem');

  / send data to problem /
  status = calllib(cplexLibName, 'CPXcopylp', EnvCPLEX, problemPtr, size(A,2), size(A,1), fn_CPLEX_Consts('CPX_MIN'),...
                        full(f), full(b), sense, matbeg, matcnt, matind, matval, full(lb), full(ub), []);

  / change problem type /
  status = calllib(cplexLibName, 'CPXchgprobtype', EnvCPLEX, problemPtr, fn_CPLEX_Consts('CPXPROB_MILP'));

  ...variable types are integer (I)

  / solve /
  status = calllib(cplexLibName, 'CPXmipopt', EnvCPLEX, problemPtr)

  / change problem type on CPXPROB_FIXEDMILP /
  status = calllib(cplexLibName, 'CPXchgprobtype', EnvCPLEX, problemPtr, fn_CPLEX_Consts('CPXPROB_FIXEDMILP'));

  / re-optimize */
  status = calllib(cplexLibName, 'CPXlpopt', EnvCPLEX, problemPtr);

This algorithm is described in the ILOG CPLEX 11 user's manual...

[b]Lagrange multipliers equal zeros :(([/b]

[b]2. turn off dependency checker, presolve. Sometimes (on the big examples) it helped:[/b]
        status = calllib(cplexLibName, 'CPXsetintparam', EnvCPLEX, fn_CPLEX_Consts('CPX_PARAM_PREIND'), 0);
        status = calllib(cplexLibName, 'CPXsetintparam', EnvCPLEX, fn_CPLEX_Consts('CPX_PARAM_DEPIND'), 0);
        status = calllib(cplexLibName, 'CPXsetintparam', EnvCPLEX, fn_CPLEX_Consts('CPX_PARAM_RELAXPREIND'), 0);

[b]Lagrange multipliers equal zeros :(([/b]

[b]3. Change target function (f)[/b]
 
  [b]min[/b] -5x1 + (5-e)x2 + 0.1x3

[b]Lagrange multipliers are correct!!! up to e < 1e-07[/b]<br />
[b]4. re-optimize in a solution point (X)[/b]
 
  lb - lower bounds
  ub - upper bounds
  X - optimal solution

  lb = X, ub = X

[b]Lagrange multipliers equal zeros :(([/b]

5. re-optimize in solution epsilon neighborhood

  lb = max(lb, lb - E)
  ub = min(ub, ub + E)

[b]Lagrange multipliers equal zeros (Does not depend on epsilon neighborhood):(([/b]

6. Search of LM by means of LP
  Lagrange multipliers are correct on all interval of admissible values (without changing lb and ub) and in solution epsilon neighborhood,
is but X is incorrect (X tends to lb)...

There are two questions.
1. Why LM = 0 at the [u]equal prices[/u]?
2. Why X tends to lower bounds(lb) at the LP?
 
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[prubin said:]

Three general comments to this thread:

1.  A dual value of zero may not be what you want, but if it is part of a legitimate optimal solution to the dual, then it is correct.

2.  If the optimal solution to a primal LP is degenerate, the dual LP has multiple optimal solutions, so there are multiple (valid!) multipliers for at least some of the constraints.  If you are getting a (valid!) zero multiplier and you want a nonzero multiplier (and presuming one exists), you have to perturb the primal constraints a bit.

3.  If the primal is degenerate (and the dual has multiple optima), some of the multipliers you get (the ones that have multiple values) only apply to changes to the constraint in one direction, or possibly not at all (meaning that any nonzero perturbation of the right-hand side of the constraint in either direction produces a different multiplier).  So if you are getting a zero multiplier and want a nonzero one, be sure that the nonzero multiplier actually is valid for whatever direction of change in the RHS you are interested in.  (Perturbation in that direction should get you the multiplier you want in any case.)

/Paul

#CPLEXOptimizers
#DecisionOptimization