Nonlinear transportation problem example

Description: book example autogenerated using nltransd.mod, nltrans.dat, and nltrans.run

Tags: ampl-only, ampl-book, nonlinear

Notebook author: Marcos Dominguez Velad <marcos@ampl.com>

Model author: N/A

# Install dependencies
%pip install -q amplpy

# Google Colab & Kaggle integration
from amplpy import AMPL, ampl_notebook

ampl = ampl_notebook(
    modules=["coin"],  # modules to install
    license_uuid="default",  # license to use
)  # instantiate AMPL object and register magics

Nonlinear transportation model

This is a variation of the linear transportation model presented on the Chapter 3 of the AMPL book, containing a nonlinear objective. There are a set of origin nodes, and a set of destination nodes (net model).

• Sets:

  • ORIG: origin nodes

  • DEST: final nodes

• Parameters:

  • supply {ORIG}: available units at origins

  • demand {DEST}: required units at destinations

  • limit {ORIG,DEST}: maximum capacity on routes between two nodes

  • rate {ORIG,DEST}: base shipment costs per unit

• Variables:

  • Trans {ORIG,DEST}: units to be shipped

• Objective: minimize total cost (nonlinear)

$$\sum \limits_{\substack{i \in ORIG \ j \in DEST}} rate[i,j] \cdot \frac{Trans[i,j]^{0.8}}{1 - \frac{Trans[i,j]}{limit[i,j]}}$$

The bigger the Trans[i,j] value, the closer to limit[i,j] (upper bound) so denominator tends to $1-1=0$ implying high costs.

• Constraints:

  • Supply {ORIG}: node ships units equal to supply capacity:

  $$\sum \limits_{j \in DEST} Trans[i,j] = supply[i]$$

  • Demand {DEST}: node gets units equal to demand:

  $$\sum \limits_{i \in ORIG} Trans[i,j] = demand[j]$$

Remark: as the objective function is highly nonlinear, some bounds are fixed in order to help the solver and getting a consistent solution. The first guess for variables is away from zero in 0.5*limit[i,j].

%%writefile nltrans_final.mod
set ORIG;   # origins
set DEST;   # destinations

param supply {ORIG} >= 0;   # amounts available at origins
param demand {DEST} >= 0;   # amounts required at destinations

   check: sum {i in ORIG} supply[i] = sum {j in DEST} demand[j];

param rate {ORIG,DEST} >= 0;   # base shipment costs per unit
param limit {ORIG,DEST} > 0;   # limit on units shipped

var Trans {i in ORIG, j in DEST}
   >= 1e-10, <= .9999 * limit[i,j], := 0.5*limit[i,j];
# actual units to be shipped

minimize Total_Cost:
   sum {i in ORIG, j in DEST}
      rate[i,j] * Trans[i,j]^0.8 / (1 - Trans[i,j]/limit[i,j]);

subject to Supply {i in ORIG}:  
   sum {j in DEST} Trans[i,j] = supply[i];

subject to Demand {j in DEST}:  
   sum {i in ORIG} Trans[i,j] = demand[j];
   

Overwriting nltrans_final.mod

%%writefile nltrans.dat
data;

param: ORIG:  supply :=
        GARY   1400    CLEV   2600    PITT   2900 ;

param: DEST:  demand :=
        FRA     900    DET    1200    LAN     600 
        WIN     400    STL    1700    FRE    1100 
        LAF    1000 ;

param rate :  FRA  DET  LAN  WIN  STL  FRE  LAF :=
        GARY   39   14   11   14   16   82    8
        CLEV   27    9   12    9   26   95   17
        PITT   24   14   17   13   28   99   20 ;

param limit :  FRA  DET  LAN  WIN  STL  FRE  LAF :=
        GARY   500 1000 1000 1000  800  500 1000
        CLEV   500  800  800  800  500  500 1000
        PITT   800  600  600  600  500  500  900 ;

Overwriting nltrans.dat

%%ampl_eval
model nltrans_final.mod;
data nltrans.dat;
option solver ipopt;
option ipopt_options 'outlev=0';
solve;
display Total_Cost, Trans;

Ipopt 3.12.13: outlev=0


******************************************************************************
This program contains Ipopt, a library for large-scale nonlinear optimization.
 Ipopt is released as open source code under the Eclipse Public License (EPL).
         For more information visit http://projects.coin-or.org/Ipopt
******************************************************************************

 
Ipopt 3.12.13: Restoration Phase Failed.

suffix ipopt_zU_out OUT;
suffix ipopt_zL_out OUT;
Total_Cost = 354279

Trans [*,*] (tr)
:      CLEV         GARY         PITT      :=
DET   586.429   191.805         421.765
FRA   292.089    75.1764        532.735
FRE   365.333   370.173         364.494
LAF   488.914     0.0937081     510.992
LAN   298.74      0.000276411   301.26
STL   469.177   762.751         468.072
WIN    99.318     9.99922e-05   300.682
;

previous

Nonlinear transportation model

next

Optimization Methods in Finance: Chapter 3