Pattern Enumeration

Description: Pattern enumeration 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 amplpy matplotlib numpy

# 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

Basic pattern-cutting model

%%ampl_eval
param nPatterns integer > 0;
set PATTERNS = 1..nPatterns; # patterns
set WIDTHS; # finished widths
param order {WIDTHS} >= 0; # rolls of width j ordered
param overrun; # permitted overrun on any width
param rolls {WIDTHS,PATTERNS} >= 0 default 0; # rolls of width i in pattern j

var Cut {PATTERNS} integer >= 0; # raw rolls to cut in each pattern

minimize TotalRawRolls: sum {p in PATTERNS} Cut[p];

subject to FinishedRollLimits {w in WIDTHS}:
  order[w] <= sum {p in PATTERNS} rolls[w,p] * Cut[p] <= order[w] + overrun;

Enumeration routine

from math import floor


def patternEnum(roll_width, widths, prefix=[]):
    max_rep = int(floor(roll_width / widths[0]))
    if len(widths) == 1:
        patmat = [prefix + [max_rep]]
    else:
        patmat = []
        for n in reversed(range(max_rep + 1)):
            patmat += patternEnum(roll_width - n * widths[0], widths[1:], prefix + [n])
    return patmat

Plotting routine

def cuttingPlot(roll_width, widths, solution):
    import numpy as np
    import matplotlib.pyplot as plt

    ind = np.arange(len(solution))
    acc = [0] * len(solution)
    for p, (patt, rep) in enumerate(solution):
        for i in range(len(widths)):
            for j in range(patt[i]):
                vec = [0] * len(solution)
                vec[p] = widths[i]
                plt.bar(ind, vec, width=0.35, bottom=acc)
                acc[p] += widths[i]
    plt.title("Solution")
    plt.xticks(ind, tuple("x {:}".format(rep) for patt, rep in solution))
    plt.yticks(np.arange(0, roll_width, 10))
    plt.show()

Set & generate data

roll_width = 64.5
overrun = 6
orders = {6.77: 10, 7.56: 40, 17.46: 33, 18.76: 10}
widths = list(sorted(orders.keys(), reverse=True))
patmat = patternEnum(roll_width, widths)

Send data to AMPL (Java/C++ style)

# Send scalar values
ampl.get_parameter("overrun").set(overrun)
ampl.get_parameter("nPatterns").set(len(patmat))
# Send order vector
ampl.get_set("WIDTHS").set_values(widths)
ampl.get_parameter("order").set_values(orders)
# Send pattern matrix
ampl.get_parameter("rolls").set_values(
    {
        (widths[i], 1 + p): patmat[p][i]
        for i in range(len(widths))
        for p in range(len(patmat))
    }
)

Send data to AMPL (alternative style)

# Send scalar values
ampl.param["overrun"] = overrun
ampl.param["nPatterns"] = len(patmat)
# Send order vector
ampl.set["WIDTHS"] = widths
ampl.param["order"] = orders
# Send pattern matrixc
ampl.param["rolls"] = {
    (widths[i], 1 + p): patmat[p][i]
    for i in range(len(widths))
    for p in range(len(patmat))
}

Solve and report

# Solve
ampl.solve(solver="gurobi")
assert ampl.solve_result == "solved", ampl.solve_result

# Retrieve solution
cutvec = ampl.var["Cut"].to_list(skip_index=True)

# Display solution
solution = [(patmat[p], cutvec[p]) for p in range(len(patmat)) if cutvec[p] > 0]
cuttingPlot(roll_width, widths, solution)

Gurobi 9.5.0: optimal solution; objective 18
6 simplex iterations
1 branch-and-cut nodes