Roll Cutting - Revision 1 & 2¶

Description: Pattern tradeoff example with amplpy

Tags: amplpy, example

Notebook author: Filipe Brandão <fdabrandao@gmail.com>

Model author: N/A

References: N/A

# Install dependencies
%pip install -q amplpy

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

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

Roll Cutting - Revision 1¶

%%ampl_eval
param roll_width > 0;

set WIDTHS;
param orders {WIDTHS} > 0;

param nPAT integer >= 0;
param nbr {WIDTHS,1..nPAT} integer >= 0;

var Cut {1..nPAT} integer >= 0;

minimize Number:
   sum {j in 1..nPAT} Cut[j];
minimize Waste:
   sum {j in 1..nPAT} Cut[j] * (roll_width - sum {i in WIDTHS} i * nbr[i,j]);

subj to Fulfill {i in WIDTHS}:
   sum {j in 1..nPAT} nbr[i,j] * Cut[j] >= orders[i];

%%ampl_eval
data;
param roll_width := 64.5;

param: WIDTHS: orders :=
         6.77    10
         7.56    40
        17.46    33
        18.76    10 ;

param nPAT := 9 ;

param nbr:  1  2  3  4  5  6  7  8  9 :=
     6.77   0  1  1  0  3  2  0  1  4
     7.56   1  0  2  1  1  4  6  5  2
    17.46   0  1  0  2  1  0  1  1  1
    18.76   3  2  2  1  1  1  0  0  0 ;

Optimal solution for the objective Number¶

ampl.option["solver"] = "gurobi"
ampl.eval("objective Number; solve;")
ampl.display("Number", "Waste")

Gurobi 9.5.0: optimal solution; objective 20
3 simplex iterations
1 branch-and-cut nodes
Number = 20
Waste = 63.62

Optimal solution for the objective Waste¶

ampl.eval("objective Waste; solve;")
ampl.display("Number", "Waste")

Gurobi 9.5.0: optimal solution; objective 15.62
2 simplex iterations
1 branch-and-cut nodes
Number = 35
Waste = 15.62

Reset session in order to load a new model¶

ampl.reset()

Roll Cutting - Revision 2¶

%%ampl_eval
param roll_width > 0;
param over_lim integer >= 0;

set WIDTHS;
param orders {WIDTHS} > 0;

param nPAT integer >= 0;
param nbr {WIDTHS,1..nPAT} integer >= 0;

var Cut {1..nPAT} integer >= 0;

minimize Number:
   sum {j in 1..nPAT} Cut[j];
minimize Waste:
   sum {j in 1..nPAT} Cut[j] * (roll_width - sum {i in WIDTHS} i * nbr[i,j]);

subj to Fulfill {i in WIDTHS}:
   orders[i] <= sum {j in 1..nPAT} nbr[i,j] * Cut[j] <= orders[i] + over_lim;

%%ampl_eval
data;
param roll_width := 64.5;
param over_lim := 10 ;

param: WIDTHS: orders :=
         6.77    10
         7.56    40
        17.46    33
        18.76    10 ;

param nPAT := 9 ;

param nbr:  1  2  3  4  5  6  7  8  9 :=
     6.77   0  1  1  0  3  2  0  1  4
     7.56   1  0  2  1  1  4  6  5  2
    17.46   0  1  0  2  1  0  1  1  1
    18.76   3  2  2  1  1  1  0  0  0 ;

Initial solve¶

ampl.option["solver"] = "gurobi"
ampl.eval("objective Number; solve;")
min_number = ampl.get_value("Number")
min_numwaste = ampl.get_value("Waste")
ampl.eval("objective Waste;")

Gurobi 9.5.0: optimal solution; objective 20
7 simplex iterations
1 branch-and-cut nodes

over_lim = int(ampl.param["over_lim"].value())
prev_number = float("inf")
min_waste = {}
min_wastenum = {}
for k in reversed(range(over_lim)):
    ampl.param["over_lim"] = k
    ampl.solve()
    if ampl.solve_result == "infeasible":
        break
    number = ampl.get_value("Number")
    if number < prev_number:
        min_waste[k] = ampl.get_value("Waste")
        min_wastenum[k] = number
        prev_number = number
    if number == min_number:
        break

Gurobi 9.5.0: optimal solution; objective 46.72
4 simplex iterations
1 branch-and-cut nodes
Gurobi 9.5.0: optimal solution; objective 46.72
4 simplex iterations
1 branch-and-cut nodes
Gurobi 9.5.0: optimal solution; objective 47.89
4 simplex iterations
1 branch-and-cut nodes
Gurobi 9.5.0: optimal solution; objective 49.16
4 simplex iterations
1 branch-and-cut nodes
Gurobi 9.5.0: optimal solution; objective 54.76
5 simplex iterations
1 branch-and-cut nodes

Report¶

print("Min{:3.0f} rolls with waste{:6.2f}\n".format(min_number, min_numwaste))
print("Over\tWaste\tNumber")
for k in sorted(min_waste.keys(), reverse=True):
    print("{}\t{}\t{:.0f}".format(k, min_waste[k], min_wastenum[k]))

Min 20 rolls with waste 62.04

Over	Waste	Number
9	46.71999999999988	22
7	47.88999999999987	21
5	54.75999999999988	20

Robust Linear Programming with Ellipsoidal Uncertainty

Simple sudoku solver using logical constraints (with GUI)