Multicommodity transportation problem¶

Description: Multicommodity transportation model with binary variables

Tags: ampl-only, ampl-book, mixed-integer-linear

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

Model¶

There are a set of origin nodes, a set of destination nodes, and products to be demanded/supplied from origins to destinations.

Sets:
- ORIG: origin cities that supply products
- DEST: final cities that demand and receive products
- PROD: set of products to deliver
Parameters:
- supply {ORIG,PROD}: amounts of product available at origins
- demand {DEST,PROD}: amounts required at destinations
- limit {ORIG,DEST}: maximum capacity on routes between two nodes
- vcost {ORIG,DEST,PROD}: variable shipment cost on routes that depends on the units of product sent
- fcost {ORIG,DEST}: fixed cost for using a route
Variables:
- Trans {ORIG,DEST,PROD}: units to be shipped
- Use {ORIG,DEST}: binary variable equals to 1 if route is used, else 0
Objective: minimize total cost

$$ \sum \limits_{\substack{i \in ORIG \ j \in DEST \ p \in PROD}} vcost[i,j,p] \cdot Trans[i,j,p]

\sum \limits_{\substack{i \in ORIG \ j \in DEST}} fcost[i,j] \cdot Use[i,j]$$

Constraints:
- Supply {ORIG,PROD}: node ships units equal to supply capacity
$$\sum \limits_{j \in DEST} Trans[i,j,p] = supply[i,p]$$
- Demand {DEST,PROD}: node gets units equal to demand
$$\sum \limits_{i \in ORIG} Trans[i,j,p] = demand[j,p]$$
- Multi {ORIG,DEST}: links capacity is bounded
$$\sum \limits_{p \in PROD} Trans[i,j,p] \leq limit[i,j] \cdot Use[i,j]$$

%%writefile multmip1.mod
set ORIG;   # origins
set DEST;   # destinations
set PROD;   # products

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

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

param limit {ORIG,DEST} >= 0;   # maximum shipments on routes

param vcost {ORIG,DEST,PROD} >= 0; # variable shipment cost on routes
var Trans {ORIG,DEST,PROD} >= 0;   # units to be shipped

param fcost {ORIG,DEST} >= 0;      # fixed cost for using a route
var Use {ORIG,DEST} binary;        # = 1 only for routes used

minimize Total_Cost:
   sum {i in ORIG, j in DEST, p in PROD} vcost[i,j,p] * Trans[i,j,p]
 + sum {i in ORIG, j in DEST} fcost[i,j] * Use[i,j];

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

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

subject to Multi {i in ORIG, j in DEST}:
   sum {p in PROD} Trans[i,j,p] <= limit[i,j] * Use[i,j];

Writing multmip1.mod

%%writefile multmip1.dat
data;

set ORIG := GARY CLEV PITT ;
set DEST := FRA DET LAN WIN STL FRE LAF ;
set PROD := bands coils plate ;

param supply (tr):  GARY   CLEV   PITT :=
            bands    400    700    800
            coils    800   1600   1800
            plate    200    300    300 ;

param demand (tr):
               FRA  DET  LAN  WIN  STL  FRE  LAF :=
       bands   300  300  100   75  650  225  250
       coils   500  750  400  250  950  850  500
       plate   100  100    0   50  200  100  250 ;

param limit default 625 ;

param vcost :=

 [*,*,bands]:  FRA  DET  LAN  WIN  STL  FRE  LAF :=
        GARY    30   10    8   10   11   71    6
        CLEV    22    7   10    7   21   82   13
        PITT    19   11   12   10   25   83   15

 [*,*,coils]:  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

 [*,*,plate]:  FRA  DET  LAN  WIN  STL  FRE  LAF :=
        GARY    41   15   12   16   17   86    8
        CLEV    29    9   13    9   28   99   18
        PITT    26   14   17   13   31  104   20 ;

param fcost:   FRA  DET  LAN  WIN  STL  FRE  LAF :=
        GARY  3000 1200 1200 1200 2500 3500 2500
        CLEV  2000 1000 1500 1200 2500 3000 2200
        PITT  2000 1200 1500 1500 2500 3500 2200 ;

Writing multmip1.dat

%%ampl_eval
model multmip1.mod;
data multmip1.dat;
option solver cbc;
solve;
option display_eps .000001;
option display_transpose -10;
display Use;
display Trans;

CBC 2.10.5: CBC 2.10.5 optimal, objective 229850
6 nodes, 1785 iterations, 0.457534 seconds
Use [*,*]
:    DET FRA FRE LAF LAN STL WIN    :=
CLEV   1   1   0   1   1   1   1
GARY   0   0   1   0   1   1   0
PITT   1   1   1   1   0   1   0
;

Trans [CLEV,*,*]
:   bands coils plate    :=
DET     0   525   100
FRA   275     0     0
FRE     0     0     0
LAF     0   375    50
LAN     0   350     0
STL   350   100   100
WIN    75   250    50

 [GARY,*,*]
:   bands coils plate    :=
DET     0     0     0
FRA     0     0     0
FRE     0   525   100
LAF     0     0     0
LAN   100    50     0
STL   300   225   100
WIN     0     0     0

 [PITT,*,*]
:   bands coils plate    :=
DET   300   225     0
FRA    25   500   100
FRE   225   325     0
LAF   250   125   200
LAN     0     0     0
STL     0   625     0
WIN     0     0     0
;

Magic sequences

N-Queens