AMPL/Cplex: No solver needed

 

Hello,

Anyone can help?
I have run the following model using AMPL code with CPLEX 11.2 solver
in window xp. The program run well and take a couple seconds for the
small size of problem. But once the problem size is more than 200 (of
j and k), the solve time increases dramatically. When the problem size
of set j and set k is 900 ,  it took so long ( longer than 10 hrs) to
find the solution. I wonder, since the model looks simple with only 2
variables per constraint. I'm not sure did I write the AMPL code wrong
or there is something wrong about this. (However, I checked the
solution from CPLEX after it done. The solution is correct). Thank you
very much.

Best regards,
Alex

The Mathematical Model is:

Objective: Min Delta
S.t. (1) Xj *(Bj + Sum(i) M(ICij + TC1ij + TC2ijk)) <= Delta,     For all j, k

(2) Sum(i) Xj = 1

(3) Xj = {0, 1}

The AMPL code is:

set stag ;
set sup;
set w;

param tc1{i in sup,j in stag}>=0;
param b{j in stag}>=0;
param ic {i in sup,j in stag}>=0;
param M integer;
param tc2{i in sup,j in stag,k in w}>=0;

var x{j in stag} binary;
var Delta;

minimize cost: Delta;
subject to delt{k in w, j in stag}:  x[j]*(b[j]+ sum{i in sup} (M*(ic[i,j]+ tc1[i,j]+ tc2[i,j,k]) )) <= Delta;
subject to c: sum{j in stag} x[j] = 1;

Ten hours is a long time for 900 binary variables in this rather simple model. The problem has many rows as a result of the way the max is formulated. This construct where we minimize the max is sometimes difficult for MIP solvers. Note that some MIP models are just very difficult to solve (example). However in this case, I believe this problem can be solved extremely fast without even using Cplex. First we calculate a[j,k] such that we can simplify the problem to:

minimize cost: Delta;
subject to delt{k in w, j in stag}:  x[j]*a[j,k] <= Delta;
subject to c: sum{j in stag} x[j] = 1;

The first constraint can be interpreted as: if (x[j]=1) then Delta = max_k a[j,k]. The complete model can now be restated as:

param a{j in stag, k in w} := b[j] + sum{i in sup} (M*(ic[i,j]+ tc1[i,j]+ tc2[i,j,k]));
param d{j in stag} := max{k in w} a[j,k];
param dmin := min{j in stag} d[j];
var x{j in stag} binary := if (d[j]=dmin) then 1 else 0;
var Delta := dmin;
display x,Delta;

(I left as an exercise to make sure there is only one x[j]=1 in case multiple d[j]’s assume the value dmin). If you really want to call Cplex (especially after shelling out big bucks for it), the following should be very fast:

var x{j in stag} binary;
var Delta;

minimize cost: Delta;
subject to c: sum{j in stag} x[j] = 1;
subject to c2: sum{j in stag} x[j]*d[j] = dmin;
subject to c3: Delta = dmin;

option solver cplex;
solve;

This formulation automatically deals with the problem of multiple d[j]’s being equal to the minimum.