Wednesday, June 16, 2010

ipopt for very small NLPs

In the paper http://www.palgrave-journals.com/jors/journal/v61/n3/full/jors200977a.html 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:

$ontext

   
minimize fuel use by optimizing speed on shipping routes

   
Reference:
     
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

$offtext

set
  i
'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

;

scalars
   minspeed
'knots' /14/
   maxspeed
'knots' /20/
;

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

positive variables
   v(i)
'speed (knots)'
   t(i)
'time'
;
free variable fuel;

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

t.lo(i) = data(i,
'early')*24;
t.up(i) = data(i,
'last')*24;

*--------------------------------------------------------------------
* speed model
*--------------------------------------------------------------------

equations
  obj1
  time1(i)
;

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
  dt(i)
'sailing time'
;
* prevent division by zero by assuming lowerbound of 1
dt.lo(i) = 1;
equations
  obj2
  time2(i)
;

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.