Nonlinear transportation problem example#

nltrans.ipynb Open In Colab Kaggle Gradient Open In SageMaker Studio Lab Hits

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)

\[\begin{split}\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]}}\end{split}\]

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
;