Weird behaviour of cplex when solving an unbounded problem.

[Jose Soto]

I am trying to test ampl with a very simple 3 variables and 3 constraints 

linear program. The model is very simple and can be solved by hand.

This is my model (example.mod)

var a;

var b <= 0;

var c;

minimize valor: a + 12*b;

subject to r1: 13*a+2*b+12*c <= 5;

subject to r2: a + c >= 1;

subject to r3: 15*a-2*b = 14;

I want to use cplex to compute a ray of feasible solutions.

If I load the model in ampl, solve it using cplex and display the unbounded directions I get the following:

ampl: model example.mod;

ampl: solve;

CPLEX 12.6.0.1: unbounded problem.

2 dual simplex iterations (2 in phase I)

variable.unbdd returned

suffix unbdd OUT;

ampl: display _varname, _var, _var.unbdd;

: _varname   _var _var.unbdd    :=

1   a         0       -1

2   b        -7.5     -7.5

3   c         1        1

;

But it is easy to see that the point (0,-7.5,1) does not satisfy the third restriction, and that (0,-7.5,1)+t(-1,-7.5,1) is NOT a ray of feasible solutions.

However, if I enter the command solve again, I get a different (correct) ray of feasible solutions (0,-7.5,1)+t(-1,-7.5,1).

ampl: solve;

CPLEX 12.6.0.1: unbounded problem.

0 simplex iterations (0 in phase I)

variable.unbdd returned

ampl: display _varname, _var, _var.unbdd;

: _varname _var _var.unbdd    :=

1   a         0     -1

2   b        -7     -7.5

3   c         1      1

;

Do you know what is going on?

[Robert Fourer]

When CPLEX (or another MIP solver) returns an unbounded ray in _var.unbdd, there is no guarantee that the _var values will give a feasible solution. To get a reliably feasible solution (or to determine that there is no feasible solution), you would need to drop the objective (with the command "drop valor;" in your situation) and then solve again.

The underlying reason for this is that unboundedness of the linear program is independent of right-hand side constants of the constraints. Hence unboundedness may in some cases be determined before any feasible solution has been found.

For the particular example that you give, in the first solve CPLEX uses the dual simplex method and determines an unbounded direction without finding a feasible solution. But in the second solve CPLEX uses the primal simplex method which does return a feasible solution along with the unboundedness direction. CPLEX behaves differently in the two cases because the first solve returns to AMPL some basis status information; then AMPL sends the basis status information back to CPLEX to help with the second solve. Given the basis status information, the primal simplex solve is trivial and CPLEX does not choose the dual simplex.

Bob Fourer
am...@googlegroups.com

=======