Differente Reduced cost values obtained with cplex and minos

[Alessandro Oscar Gilardino Arias]

Dear all, good night.

I have a question, when I solve my model with Minos I have the following values of reduced cost.

ampl: display P.rc;

P.rc [*] :=

 1  0

 2  0

 3  0

 4  0

 5  0

 6  0

 7  0

 8  0

 9  0

10  0

11  0

12  0

13  0

14  0

15  0

16  0

17  0

18  0

19  0.153846

20  0

;

But when I solve the same problem with cplex I have the following reduced cost

ampl: display P.rc;

P.rc [*] :=

 1   0

 2   0

 3   0

 4   0

 5   0

 6   0

 7  -1.77636e-15

 8   0

 9   0

10   0

11   0

12   0

13   0

14   0

15   0

16   0

17   0

18   0

19   0

20   0

;

Why the difference?

I am attaching my model and data files.

Thanks in advance

[Michael Saunders]

Buenos dias Alessandro,

LP problems can have alternative optimal basis matrices,

and these can give alternative optimal reduced costs.

You can impose bounds on your variables more efficiently as follows:

var P {i in Productos} >= Demandamin[i], <= Demandamax[i];

Perhaps this will help the reduced costs agree.

See what happens.

Michael

--
You received this message because you are subscribed to the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ampl+uns...@googlegroups.com.
To post to this group, send email to am...@googlegroups.com.
Visit this group at https://groups.google.com/group/ampl.
For more options, visit https://groups.google.com/d/optout.

[Alessandro Oscar Gilardino Arias]

Thanks for your answer Michael, But I have a question, this means that Minos and cplex return different optimal values, like alternative optimals?

Alessandro Gilardino Arias

Red Peruana de Ciclo de Vida

Departamento de Ingenieria

Pontificia Universidad Catolica del Peru

[Michael Saunders]

Hi Alessandro,

I mean that the optimal objective is the same, but

the optimal basis is possibly different, so the dual variables

and reduced costs all have the correct sign but perhaps are different.

The solution needs to be (primal or dual?) degenerate,

but this is normal for LP models.

Michael

[Alessandro Oscar Gilardino Arias]

Thanks Michael, I did what you told me, now I am using

var P {i in Productos} >= Demandamin[i], <= Demandamax[i];

 but know I have the following values.

With MINOS:

ampl: display P.lb, P, P.ub, P.rc;

:  P.lb      P     P.ub       P.rc        :=

1    10   150       150    1.42308

2    15    80        80    4.21154

3     0    90        90    4.73077

4     0   100       100    3.01923

5    10   180       180    1

6     0   150       150    1.90385

7    10   122.906   150   -1.77636e-15

8     0   145       145    0.461538

9    20   100       100    6.42308

10   25   110       110    5.46154

11   15   150       150    6.5

12   10   160       160    8.5

13    0   165       165    3.15385

14    0   155       155    3.5

15    0   150       150    7.76923

16   10   250       250   13.2308

17    0   150       150   17.6923

18    0   200       200    4.19231

19    0   250       250    0.153846

20    0   180       180    6.76923

with Cplex:

ampl: display P.lb, P, P.ub, P.rc;

:  P.lb      P     P.ub       P.rc        :=

1    10   150       150    1.42308

2    15    80        80    4.21154

3     0    90        90    4.73077

4     0   100       100    3.01923

5    10   180       180    1

6     0   150       150    1.90385

7    10   122.906   150   -1.77636e-15

8     0   145       145    0.461538

9    20   100       100    6.42308

10   25   110       110    5.46154

11   15   150       150    6.5

12   10   160       160    8.5

13    0   165       165    3.15385

14    0   155       155    3.5

15    0   150       150    7.76923

16   10   250       250   13.2308

17    0   150       150   17.6923

18    0   200       200    4.19231

19    0   250       250    0.153846

20    0   180       180    6.76923

now they are the same, but the results are different from the first model I use, why that difference?

Thanks in advance

Alessandro Gilardino Arias

Red Peruana de Ciclo de Vida

Departamento de Ingenieria

Pontificia Universidad Catolica del Peru

[Alessandro Oscar Gilardino Arias]

Hi Michael, we have already check and the solution is not degenerate.

That difference between the results of reduced cost using minos and cplex could be tat both have different ussages or are designed for different types of problems?

[Michael Saunders]

Hi Alessandro,

If your constraint matrix A is m x n, more than m zero reduced costs

means the solution is dual degenerate.  A nonbasic column with zero

reduced cost could enter the basis without altering the objective.

This would normally change the dual variables and reduced costs

(but not the objective).  It's an alternative solution.

For linear problems, minos uses primal simplex; cplex uses either

primal or dual simplex.  The tests for optimality are the same, but

they depend on the final basis.

If you want to make the solution unique, you could add a term

gamma * x^T x to the objective (and minos could handle it),

but the solution would vary with gamma.

Remember that alternative solutions have the same objective

(so they are equally good by some measure).

In real life there are often equally good ways to do the same thing.

If you still have questions, you could tell us what your concern is.

Michael

[Alessandro Oscar Gilardino Arias]

Hi Michael, I still have that question.

I did some research in my operations research books and read that the values of reduced cost that Minos returns should be 0, because in the example  all the variables P are basic variables, that means that the reduced cost should be cero.

Also, if a basic variable has a reduced cost different than cero, there will be a contradiction with the complementary slackness theorem. Thats what I can't understand very well.

Regards

Alessandro Gilardino Arias

Red Peruana de Ciclo de Vida

Departamento de Ingenieria

Pontificia Universidad Catolica del Peru

[Michael Saunders]

Ok Alessandro, it's true that reduced costs are zero for basic variables.

I thought you were looking at reduced costs for nonbasic variables.

If A = [B N] and c = [c_B; c_N], simplex solves B'y = c_B to get dual variables y

and forms reduced costs z_N = c_N - N'y for the nonbasic variables.

If we define z = c - A'y, you see that z_B = 0 by definition.

So in your last paragraph, "if a basic variable has a reduced cost different than zero"

is never true.

Best wishes for understanding,

Michael