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.

3 comments:

  1. OPL/CP does not do to well with this generic formulation ... 46 seconds on half knot accuracy.

    ---
    /*********************************************
    * Fuel consumption minimization
    * OPL 6.3 Model
    * Author: karsten.konrad
    * Creation Date: 17.06.2010 at 12:56:25

    Reference:
    http://yetanothermathprogrammingconsultant.blogspot.com/2010/06/ipopt-for-very-small-nlps.html#links
    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
    *********************************************/

    using CP;

    tuple Leg {

    // nulmber of leg
    key int index;

    // distance to
    int distance;

    // earliest day at dock
    int early;

    // latest day at docl
    int late;

    }

    {Leg} leg = { <1, 510, 1, 5>,
    <2, 2699, 9, 13>,
    <3, 838, 11, 15>,
    <4, 3625, 20, 24>,
    <5, 3437, 32, 36>,
    <6, 2263, 35, 39> };;

    int minspeed = 14;
    int maxspeed = 20;

    int scale = 2;

    range SpeedRange = minspeed*scale..maxspeed*scale;

    dvar int choices[l in leg] in SpeedRange;

    dvar int time[l in leg] in l.early*24..l.late*24;

    dexpr float speed[l in leg] = choices[l]/scale;

    dexpr float fuel = sum(l in leg) l.distance * (0.0036*pow(speed[l],2) - 0.1015*speed[l] + 0.8848);

    minimize
    fuel;

    subject to {

    forall(l, k in leg: k.index == l.index + 1) time[k] - time[l] >= k.distance/speed[k];

    }

    ReplyDelete
  2. I don't think this model is correct: one constraint is missing (there should be 6 constraints w.r.t. time, and you generate only 5).

    ReplyDelete
  3. Well, I don't speak GAMS too well, its behavior wrt indexes seems to differ from OPL. Could it be this?

    forall(l in leg: l.index == 1) time[l] >= l.distance/speed[l];

    ReplyDelete