Wednesday, June 16, 2010

ipopt for very small NLPs

In the paper a small NLP model is developed to minimize fuel use for commercial ships by optimizing speed. The GAMS representation of the proposed model can look like:


minimize fuel use by optimizing speed on shipping routes

Reducing fuel emissions by optimizing speed on
shipping routes, K Fagerholt, G Laporte and I Norstad,
Journal of the Operational Research Society (2010) 61, 523 --529


'segments' /
s1  Antwerp-Milford Haven
s2  Milford Haven - Boston
s3  Boston - Charleston
s4  Charleston - Algeciras
s5  Algeciras - Point Lisas
s6  Point Lisas - Houston

table data(i,*)
distance  early last
s1      510      1    5
s2     2699      9   13
s3      838     11   15
s4     3625     20   24
s5     3437     32   36
s6     2263     35   39


'knots' /14/
'knots' /20/

parameter d(i) 'distance (nautical miles)';
d(i) = data(i,

positive variables
'speed (knots)'
free variable fuel;

v.lo(i) = minspeed;
v.up(i) = maxspeed;

t.lo(i) = data(i,
t.up(i) = data(i,

* speed model


obj1..  fuel =e=
sum(i, d(i)*(0.0036*sqr(v(i))-0.1015*v(i)+0.8848) );

time1(i).. t(i) - t(i-1) =g= d(i)/v(i);

model m1 /obj1,time1/;

* time model

positive variable
'sailing time'
* prevent division by zero by assuming lowerbound of 1
dt.lo(i) = 1;

obj2..  fuel =e=
sum(i, d(i)*(0.0036*sqr(d(i)/dt(i))-0.1015*(d(i)/dt(i))+0.8848) );

time2(i).. t(i) - t(i-1) =g= dt(i);

model m2 /obj2,time2/;

solve m2 using nlp minimizing fuel;

The second model has only linear constraints so that may be preferable in general. The waiting time is handled implicitly in this model. I would probably make the model slightly larger by making this more explicit by introducing a positive variable wt(i):

time1(i).. t(i) - t(i-1) =e= d(i)/v(i) + wt(i);

The paper mentions that IPOPT solves these models in about .5 seconds, and suggest that a discretization yielding a shortest path problem is much faster. I would suggest to try also some other NLP solvers, as IPOPT is really geared towards large scale problems. Other solvers may be a lot faster than IPOPT on these small problems. Indeed with CONOPT I see:

               S O L V E      S U M M A R Y

     MODEL   m1                  OBJECTIVE  fuel
     TYPE    NLP                 DIRECTION  MINIMIZE
     SOLVER  CONOPT              FROM LINE  65

**** SOLVER STATUS     1 Normal Completion        
**** MODEL STATUS      2 Locally Optimal          
**** OBJECTIVE VALUE             2266.4832

RESOURCE USAGE, LIMIT          0.000      1000.000
ITERATION COUNT, LIMIT        17    2000000000
EVALUATION ERRORS              0             0

The reported time is 0 seconds. (It is noted that the larger test problems in the paper are a little bit larger than this example, but not by much). Probably a good dense solver like DONLP will do very good on a model like this.