Modeling Disjunctions through the Strip Packing Problem

2.2. Modeling Disjunctions through the Strip Packing Problem#

Prepared by: Prof. Alexander Dowling (adowling@nd.edu), Hailey Lynch (hlynch@nd.edu, 2023)

2.2.1. Introduction and Learning Objectives#

This notebook illustrates a more complicated example of generalized disjunctive programs. Students will practice applying concepts of Logical Modeling and Generalized Disjunctive Programs to the Strip Packing Problem. Critical thinking discussion questions will be included to connect concepts from CBE 60499.

See the following notebook for a primer on Logical Modeling and Generalized Disjunctive Programs: [Logical Modeling and Generalized Disjunctive Programs](LINK HERE)

2.2.2. Import Modules#

# Imports
import sys
if "google.colab" in sys.modules:
    !wget "https://raw.githubusercontent.com/ndcbe/optimization/main/notebooks/helper.py"
    import helper
    helper.easy_install()
else:
    sys.path.insert(0, '../')
    import helper
helper.set_plotting_style()

milp_solver = 'cbc'

2.2.3. Pyomo.GDP: Strip Packing Problem#

We will be looking at the Strip Packing Problem using Pyomo.GDP as an example for modeling disjunctions.

Aldo Vecchietti (1) and Ignacio Grossman (2)
(1) INGAR – Instituto de Desarrollo y Diseño – CONICET – UTN, Avellaneda 3657 – Santa Fe ‐ Argentina
(2) Carnegie Mellon University, 5000 Forbes Av. ‐ Pittsburgh, PA ‐ USA

Additional Information

Link

Reference

https://www.minlp.org/library/problem/index.php?i=121&lib=GDP

Description

https://www.minlp.org/problems/ver/156/over/Strip-Packing-Overview.pdf

Results

https://www.minlp.org/problems/ver/156/results/Strip-Packing-Results.pdf

Problem Formulation

https://www.sciencedirect.com/science/article/pii/S0098135405000992

2.2.3.1. Problem Statement#

The objective in this problem consists of minimizing the length of the strip \(lt\) and by representing every rectangle by its coordinates in the \((x,y)\) space such that no overlap occurs between rectangles.

\( \text{min} \ lt \)

subject to…

Thus, every rectangle \(i \in N\) has length \(L_{i}\), height \(H_{i}\), and coordinates \((x_{i}, y_{i})\), where the point of reference corresponds to the upper left corner of every rectangle.

\[ \begin{equation} \ lt \geq x_{i} + L_{i} \ \ \forall i \in N \end{equation} \]

By constraining every pair of rectangels \((i,j)\) where \((i,j \in N, i<j)\) that no overlap occurs, we obtain a series of disjunctions with four disjuncts each, where each disjunct represents the position of rectangle \(i\) in relation to rectangle \(j\).

\[\begin{split} \begin{equation} \begin{bmatrix} Y_{ij}^{1} \\ x_{i} + L_{i} \leq x_{j} \end{bmatrix} \lor \begin{bmatrix} Y_{ij}^{2} \\ x_{j} + L_{j} \leq x_{i} \end{bmatrix} \lor \begin{bmatrix} Y_{ij}^{3} \\ y_{i} - H_{i} \geq y_{j} \end{bmatrix} \lor \begin{bmatrix} Y_{ij}^{4} \\ y_{j} - H_{j} \geq y_{i} \end{bmatrix} \end{equation} \end{split}\]

Note that the y-coordinate of every rectange is bounded from above by the fixed width of the strip \(W\), and that the upper bound \(UB_{i}\), which in a best case scenario would correspond to the optimal value of \(lt\), is obtained using a bottom-left rectangle-placing heurisitc and serves as an upper bound for the x-coordinate of every rectangle.

\[ \begin{equation} x_{i} \leq UB_{i} - L_{i} \ \ \forall i \in N \tag{4} \end{equation} \]
\[ \begin{equation} H_{i} \leq y_{i} \leq W \ \ \forall i \in N \tag{5} \end{equation} \]
\[ \begin{equation} lt, x_{i}, y_{i} \in \mathbb{R}_{+}^{1}, Y_{ij}^{1}, Y_{ij}^{2}, Y_{ij}^{3}, Y_{ij}^{4} \in \text{\{True, False}\} \ \ \forall i, j \in N, i < j \end{equation} \]

2.2.3.2. Define model in Pyomo with GDP#

First we will define the model for the Strip Packing Problem in Pyomo.

'''
Instead of using
# import pyomo.environ as pyo
We can import specific functions/objects
'''
from pyomo.environ import (ConcreteModel, NonNegativeReals, Objective, Param,
                           Set, SolverFactory, TransformationFactory, Var, value)

# Strip-packing example from http://minlp.org/library/lib.php?lib=GDP

# This model packs a set of rectangles without rotation or overlap within a
# strip of a given width, minimizing the length of the strip.

def create_model():
    '''
    Build the strip packing problem model.

    Return:
    model: Pyomo model
    
    '''
    
    ## Model
    model = ConcreteModel(name="Rectangles strip packing")
    
    ## Sets
    model.rectangles = Set(ordered=True, initialize=[0, 1, 2, 3, 4, 5, 6, 7])

    ## Parameters
    # Width and length of each rectangle
    model.rect_width = Param(
        model.rectangles, initialize={0: 3, 1: 3, 2: 2, 3: 2, 4: 3, 5: 5,
                                      6: 7, 7: 7})
    
    # Parameter indexed by each rectangle
    # Length means height
    model.rect_length = Param(
        model.rectangles, initialize={0: 4, 1: 3, 2: 2, 3: 2, 4: 3, 5: 3,
                                      6: 4, 7: 4})

    model.strip_width = Param(
        initialize=10, doc="Available width of the strip")

    # Upperbound on length (default is sum of lengths of rectangles)
    model.max_length = Param(
        initialize=sum(model.rect_length[i] for i in model.rectangles),
        doc="Maximum length of the strip (if all rectangles were arranged "
        "lengthwise)")

    ## Variables
    # x (length) and y (width) coordinates of each of the rectangles
    model.x = Var(model.rectangles,
                  bounds=(0, model.max_length),
                  doc="Rectangle corner x-position (position across length)")

    # Width bounds
    def w_bounds(m, i):
        return (0, m.strip_width - m.rect_width[i])
    model.y = Var(model.rectangles,
                  bounds=w_bounds,
                  doc="Rectangle corner y-position (position down width)")
    # String length
    model.strip_length = Var(
        within=NonNegativeReals, doc="Length of strip required.")

    # Rectangle conflicts
    def rec_pairs_filter(model, i, j):
        return i < j
    model.overlap_pairs = Set(
        initialize=model.rectangles * model.rectangles,
        dimen=2, filter=rec_pairs_filter,
        doc="Set of possible rectangle conflicts")

    ## Constraints
    @model.Constraint(model.rectangles)
    def strip_ends_after_last_rec(model, i):
        return model.strip_length >= model.x[i] + model.rect_length[i]

    ## Objective
    model.total_length = Objective(expr=model.strip_length,
                                   doc="Minimize length")

    
    ## Insert the no-overlap disjunctions here!
    
    # Add your solution here

    return model
Click to see the solution to the activity
@model.Disjunction(
    model.overlap_pairs,
    doc="Make sure that none of the rectangles on the strip overlap in "
    "either the x or y dimensions.")
def no_overlap(m, i, j):
    return [
        m.x[i] + m.rect_length[i] <= m.x[j],
        m.x[j] + m.rect_length[j] <= m.x[i],
        m.y[i] + m.rect_width[i] <= m.y[j],
        m.y[j] + m.rect_width[j] <= m.y[i],
    ]

2.2.3.3. Transform and Solve with Big M Relaxation#

Now we will create the model and use Big-M Relaxation.

2.2.3.4. Big-M Implementation in Pyomo#

# Creating the model
model = create_model()

Next, let’s transform the model. The updated model is really big, so we will not print it. This is because the transformation factory replaced the disjunctions with many Big-M constraints.

# Applying Big-M relaxation to the model
# Add your solution here
Click to see the solution to the activity
TransformationFactory('gdp.bigm').apply_to(model)

Finally, we’ll solve the model and examine the solution.

# Solve and print the solution
SolverFactory(milp_solver).solve(model, tee=True)
for i in model.rectangles:
    print("Rectangle %s: (%s, %s)" % (i, value(model.x[i]), value(model.y[i])))
model.total_length.display()

Welcome to the CBC MILP Solver 
Version: 2.10.10 
Build Date: Jun  7 2023 

command line - /Users/adowling/.idaes/bin/cbc -printingOptions all -import /var/folders/3w/vr4xmyqs451dg23xk88pqcg00000gq/T/tmpfr4nysg9.pyomo.lp -stat=1 -solve -solu /var/folders/3w/vr4xmyqs451dg23xk88pqcg00000gq/T/tmpfr4nysg9.pyomo.soln (default strategy 1)
Option for printingOptions changed from normal to all
Presolve 148 (0) rows, 129 (0) columns and 464 (0) elements
Statistics for presolved model
Original problem has 112 integers (112 of which binary)
==== 128 zero objective 2 different
128 variables have objective of 0
1 variables have objective of 1
==== absolute objective values 2 different
128 variables have objective of 0
1 variables have objective of 1
==== for integers 112 zero objective 1 different
112 variables have objective of 0
==== for integers absolute objective values 1 different
112 variables have objective of 0
===== end objective counts


Problem has 148 rows, 129 columns (1 with objective) and 464 elements
Column breakdown:
1 of type 0.0->inf, 16 of type 0.0->up, 0 of type lo->inf, 
0 of type lo->up, 0 of type free, 0 of type fixed, 
0 of type -inf->0.0, 0 of type -inf->up, 112 of type 0.0->1.0 
Row breakdown:
0 of type E 0.0, 28 of type E 1.0, 0 of type E -1.0, 
0 of type E other, 0 of type G 0.0, 0 of type G 1.0, 
0 of type G other, 0 of type L 0.0, 0 of type L 1.0, 
120 of type L other, 0 of type Range 0.0->1.0, 0 of type Range other, 
0 of type Free 
Continuous objective value is 4 - 0.00 seconds
Cgl0004I processed model has 139 rows, 120 columns (103 integer (103 of which binary)) and 434 elements
Cbc0038I Initial state - 53 integers unsatisfied sum - 13.8138
Cbc0038I Pass   1: suminf.    5.20000 (20) obj. 11 iterations 33
Cbc0038I Pass   2: suminf.    2.20000 (10) obj. 12 iterations 28
Cbc0038I Pass   3: suminf.    2.00000 (10) obj. 12 iterations 5
Cbc0038I Pass   4: suminf.    1.60000 (8) obj. 12 iterations 16
Cbc0038I Pass   5: suminf.    1.40000 (8) obj. 12 iterations 4
Cbc0038I Pass   6: suminf.    2.20000 (8) obj. 12 iterations 9
Cbc0038I Pass   7: suminf.    1.80000 (8) obj. 12 iterations 5
Cbc0038I Pass   8: suminf.    1.20000 (6) obj. 14 iterations 14
Cbc0038I Pass   9: suminf.    0.80000 (4) obj. 14 iterations 8
Cbc0038I Pass  10: suminf.    0.80000 (4) obj. 14 iterations 6
Cbc0038I Pass  11: suminf.    3.60000 (14) obj. 18 iterations 38
Cbc0038I Pass  12: suminf.    2.80000 (12) obj. 19 iterations 14
Cbc0038I Pass  13: suminf.    1.00000 (4) obj. 20 iterations 15
Cbc0038I Pass  14: suminf.    0.40000 (2) obj. 20 iterations 6
Cbc0038I Pass  15: suminf.    0.40000 (2) obj. 20 iterations 5
Cbc0038I Pass  16: suminf.    4.37654 (21) obj. 13 iterations 62
Cbc0038I Pass  17: suminf.    3.11232 (15) obj. 15 iterations 20
Cbc0038I Pass  18: suminf.    1.72315 (7) obj. 16 iterations 23
Cbc0038I Pass  19: suminf.    0.20000 (2) obj. 19 iterations 8
Cbc0038I Pass  20: suminf.    0.35714 (1) obj. 16 iterations 4
Cbc0038I Solution found of 16
Cbc0038I Relaxing continuous gives 16
Cbc0038I Before mini branch and bound, 24 integers at bound fixed and 0 continuous
Cbc0038I Full problem 139 rows 120 columns, reduced to 110 rows 91 columns - 5 fixed gives 97, 78 - ok now
Cbc0038I Full problem 139 rows 120 columns, reduced to 94 rows 75 columns
Cbc0038I Mini branch and bound improved solution from 16 to 12 (0.04 seconds)
Cbc0038I Round again with cutoff of 11.2
Cbc0038I Pass  21: suminf.    5.20000 (20) obj. 11 iterations 0
Cbc0038I Pass  22: suminf.    3.00000 (16) obj. 11 iterations 13
Cbc0038I Pass  23: suminf.    1.62759 (9) obj. 11.2 iterations 22
Cbc0038I Pass  24: suminf.    1.62759 (9) obj. 11.2 iterations 6
Cbc0038I Pass  25: suminf.    1.60000 (8) obj. 11.2 iterations 18
Cbc0038I Pass  26: suminf.    1.40000 (6) obj. 11.2 iterations 14
Cbc0038I Pass  27: suminf.    1.40000 (6) obj. 11.2 iterations 8
Cbc0038I Pass  28: suminf.    5.01376 (20) obj. 11.2 iterations 29
Cbc0038I Pass  29: suminf.    2.93005 (11) obj. 11.2 iterations 14
Cbc0038I Pass  30: suminf.    2.93005 (11) obj. 11.2 iterations 0
Cbc0038I Pass  31: suminf.    1.79310 (9) obj. 11.2 iterations 17
Cbc0038I Pass  32: suminf.    1.70246 (7) obj. 11.2 iterations 15
Cbc0038I Pass  33: suminf.    1.60000 (6) obj. 11.2 iterations 12
Cbc0038I Pass  34: suminf.    1.57143 (6) obj. 11.2 iterations 9
Cbc0038I Pass  35: suminf.    4.91073 (21) obj. 11.2 iterations 28
Cbc0038I Pass  36: suminf.    3.20172 (16) obj. 11.2 iterations 22
Cbc0038I Pass  37: suminf.    2.72241 (14) obj. 11.2 iterations 2
Cbc0038I Pass  38: suminf.    2.44261 (14) obj. 11.2 iterations 16
Cbc0038I Pass  39: suminf.    2.82044 (18) obj. 11.2 iterations 28
Cbc0038I Pass  40: suminf.    3.37586 (13) obj. 11.2 iterations 26
Cbc0038I Pass  41: suminf.    2.76921 (13) obj. 11.2 iterations 5
Cbc0038I Pass  42: suminf.    3.14058 (17) obj. 11.2 iterations 20
Cbc0038I Pass  43: suminf.    2.14058 (15) obj. 11.2 iterations 5
Cbc0038I Pass  44: suminf.    1.94975 (13) obj. 11.2 iterations 15
Cbc0038I Pass  45: suminf.    1.16552 (7) obj. 11.2 iterations 16
Cbc0038I Pass  46: suminf.    2.03793 (9) obj. 11.2 iterations 11
Cbc0038I Pass  47: suminf.    2.03793 (9) obj. 11.2 iterations 0
Cbc0038I Pass  48: suminf.    1.35862 (9) obj. 11.2 iterations 13
Cbc0038I Pass  49: suminf.    1.16552 (9) obj. 11.2 iterations 2
Cbc0038I Pass  50: suminf.    1.68769 (9) obj. 11.2 iterations 9
Cbc0038I No solution found this major pass
Cbc0038I Before mini branch and bound, 22 integers at bound fixed and 0 continuous
Cbc0038I Full problem 139 rows 120 columns, reduced to 112 rows 93 columns - 11 fixed gives 74, 56 - ok now
Cbc0038I Mini branch and bound did not improve solution (0.05 seconds)
Cbc0038I After 0.05 seconds - Feasibility pump exiting with objective of 12 - took 0.05 seconds
Cbc0012I Integer solution of 12 found by feasibility pump after 0 iterations and 0 nodes (0.05 seconds)
Cbc0038I Full problem 139 rows 120 columns, reduced to 85 rows 66 columns
Cbc0031I 48 added rows had average density of 4.2916667
Cbc0013I At root node, 48 cuts changed objective from 4 to 9.699223 in 55 passes
Cbc0014I Cut generator 0 (Probing) - 1733 row cuts average 3.7 elements, 0 column cuts (21 active)  in 0.018 seconds - new frequency is 1
Cbc0014I Cut generator 1 (Gomory) - 531 row cuts average 22.5 elements, 0 column cuts (0 active)  in 0.008 seconds - new frequency is 1
Cbc0014I Cut generator 2 (Knapsack) - 1 row cuts average 3.0 elements, 0 column cuts (0 active)  in 0.005 seconds - new frequency is -100
Cbc0014I Cut generator 3 (Clique) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.001 seconds - new frequency is -100
Cbc0014I Cut generator 4 (MixedIntegerRounding2) - 309 row cuts average 2.5 elements, 0 column cuts (0 active)  in 0.005 seconds - new frequency is 1
Cbc0014I Cut generator 5 (FlowCover) - 9 row cuts average 2.0 elements, 0 column cuts (0 active)  in 0.007 seconds - new frequency is -100
Cbc0014I Cut generator 6 (TwoMirCuts) - 416 row cuts average 11.8 elements, 0 column cuts (0 active)  in 0.007 seconds - new frequency is 1
Cbc0010I After 0 nodes, 1 on tree, 12 best solution, best possible 9.699223 (0.18 seconds)
Cbc0038I Full problem 139 rows 120 columns, reduced to 65 rows 46 columns
Cbc0038I Full problem 139 rows 120 columns, reduced to 82 rows 63 columns
Cbc0038I Full problem 139 rows 120 columns, reduced to 78 rows 59 columns
Cbc0004I Integer solution of 11 found after 10939 iterations and 261 nodes (0.45 seconds)
Cbc0001I Search completed - best objective 11, took 11062 iterations and 267 nodes (0.45 seconds)
Cbc0032I Strong branching done 2076 times (15344 iterations), fathomed 12 nodes and fixed 38 variables
Cbc0035I Maximum depth 23, 2 variables fixed on reduced cost
Cuts at root node changed objective from 4 to 9.69922
Probing was tried 339 times and created 5383 cuts of which 21 were active after adding rounds of cuts (0.044 seconds)
Gomory was tried 244 times and created 1243 cuts of which 0 were active after adding rounds of cuts (0.019 seconds)
Knapsack was tried 55 times and created 1 cuts of which 0 were active after adding rounds of cuts (0.005 seconds)
Clique was tried 55 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.001 seconds)
MixedIntegerRounding2 was tried 244 times and created 751 cuts of which 0 were active after adding rounds of cuts (0.014 seconds)
FlowCover was tried 55 times and created 9 cuts of which 0 were active after adding rounds of cuts (0.007 seconds)
TwoMirCuts was tried 244 times and created 775 cuts of which 0 were active after adding rounds of cuts (0.017 seconds)
ZeroHalf was tried 1 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
ImplicationCuts was tried 38 times and created 54 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)

Result - Optimal solution found

Objective value:                11.00000000
Enumerated nodes:               267
Total iterations:               11062
Time (CPU seconds):             0.46
Time (Wallclock seconds):       0.53

Total time (CPU seconds):       0.46   (Wallclock seconds):       0.53

Rectangle 0: (7.0, 7.0)
Rectangle 1: (4.0, 0.0)
Rectangle 2: (2.0, 0.0)
Rectangle 3: (0.0, 0.0)
Rectangle 4: (0.0, 2.0)
Rectangle 5: (0.0, 5.0)
Rectangle 6: (7.0, 0.0)
Rectangle 7: (3.0, 3.0)
total_length : Size=1, Index=None, Active=True
    Key  : Active : Value
    None :   True :  11.0

2.2.3.5. Transform and Solve with Convex Hull Relaxation#

We will repeat the procedure above using Convex Hull Relaxation.

2.2.3.6. Convex Hull Implementation in Pyomo#

# Creating the model
model = create_model()

# Applying convex hull relaxation to the model
# Add your solution here

# Solve and print the solution
SolverFactory(milp_solver).solve(model, tee=True)
for i in model.rectangles:
    print("Rectangle %s: (%s, %s)" % (i, value(model.x[i]), value(model.y[i])))
model.total_length.display()

Welcome to the CBC MILP Solver 
Version: 2.10.10 
Build Date: Jun  7 2023 

command line - /Users/adowling/.idaes/bin/cbc -printingOptions all -import /var/folders/3w/vr4xmyqs451dg23xk88pqcg00000gq/T/tmplx9dkbbu.pyomo.lp -stat=1 -solve -solu /var/folders/3w/vr4xmyqs451dg23xk88pqcg00000gq/T/tmplx9dkbbu.pyomo.soln (default strategy 1)
Option for printingOptions changed from normal to all
Presolve 484 (-112) rows, 353 (-112) columns and 1696 (0) elements
Statistics for presolved model
Original problem has 112 integers (112 of which binary)
Presolved problem has 112 integers (112 of which binary)
==== 352 zero objective 2 different
352 variables have objective of 0
1 variables have objective of 1
==== absolute objective values 2 different
352 variables have objective of 0
1 variables have objective of 1
==== for integers 112 zero objective 1 different
112 variables have objective of 0
==== for integers absolute objective values 1 different
112 variables have objective of 0
===== end objective counts


Problem has 484 rows, 353 columns (1 with objective) and 1696 elements
Column breakdown:
1 of type 0.0->inf, 240 of type 0.0->up, 0 of type lo->inf, 
0 of type lo->up, 0 of type free, 0 of type fixed, 
0 of type -inf->0.0, 0 of type -inf->up, 112 of type 0.0->1.0 
Row breakdown:
0 of type E 0.0, 28 of type E 1.0, 0 of type E -1.0, 
0 of type E other, 0 of type G 0.0, 0 of type G 1.0, 
0 of type G other, 336 of type L 0.0, 0 of type L 1.0, 
120 of type L other, 0 of type Range 0.0->1.0, 0 of type Range other, 
0 of type Free 
Continuous objective value is 6 - 0.00 seconds
Cgl0003I 0 fixed, 0 tightened bounds, 21 strengthened rows, 0 substitutions
Cgl0004I processed model has 463 rows, 332 columns (103 integer (103 of which binary)) and 1594 elements
Cbc0038I Initial state - 57 integers unsatisfied sum - 14.153
Cbc0038I Pass   1: suminf.    7.62993 (32) obj. 11.0857 iterations 154
Cbc0038I Pass   2: suminf.    5.59836 (25) obj. 15.3 iterations 24
Cbc0038I Pass   3: suminf.    5.19836 (21) obj. 15.8 iterations 2
Cbc0038I Pass   4: suminf.    4.84663 (22) obj. 12.6207 iterations 12
Cbc0038I Pass   5: suminf.    2.52062 (14) obj. 19.069 iterations 53
Cbc0038I Pass   6: suminf.    2.35412 (12) obj. 15.6207 iterations 6
Cbc0038I Pass   7: suminf.    2.02857 (11) obj. 22.5238 iterations 29
Cbc0038I Pass   8: suminf.    1.96552 (9) obj. 23.069 iterations 4
Cbc0038I Pass   9: suminf.    1.96552 (11) obj. 19.6207 iterations 1
Cbc0038I Pass  10: suminf.    3.65681 (15) obj. 18.3333 iterations 28
Cbc0038I Pass  11: suminf.    3.26348 (13) obj. 18.6207 iterations 8
Cbc0038I Pass  12: suminf.    2.90633 (12) obj. 17.9286 iterations 9
Cbc0038I Pass  13: suminf.    2.83218 (9) obj. 18.069 iterations 36
Cbc0038I Pass  14: suminf.    2.73695 (9) obj. 18.069 iterations 5
Cbc0038I Pass  15: suminf.    2.53695 (7) obj. 27 iterations 23
Cbc0038I Pass  16: suminf.    1.73695 (9) obj. 27 iterations 10
Cbc0038I Pass  17: suminf.    1.73695 (9) obj. 27 iterations 0
Cbc0038I Pass  18: suminf.    3.14552 (10) obj. 27 iterations 19
Cbc0038I Pass  19: suminf.    3.12062 (10) obj. 27 iterations 3
Cbc0038I Pass  20: suminf.    2.23810 (8) obj. 27 iterations 29
Cbc0038I Pass  21: suminf.    2.18367 (8) obj. 27 iterations 6
Cbc0038I Pass  22: suminf.    2.56552 (8) obj. 27 iterations 31
Cbc0038I Pass  23: suminf.    2.56552 (8) obj. 27 iterations 0
Cbc0038I Pass  24: suminf.    1.16552 (5) obj. 27 iterations 25
Cbc0038I Pass  25: suminf.    1.16552 (7) obj. 27 iterations 2
Cbc0038I Pass  26: suminf.    2.18000 (8) obj. 27 iterations 17
Cbc0038I Pass  27: suminf.    2.15510 (8) obj. 27 iterations 3
Cbc0038I Pass  28: suminf.    1.66667 (6) obj. 27 iterations 25
Cbc0038I Pass  29: suminf.    1.61224 (6) obj. 27 iterations 6
Cbc0038I Pass  30: suminf.    1.60000 (5) obj. 27 iterations 27
Cbc0038I No solution found this major pass
Cbc0038I Before mini branch and bound, 36 integers at bound fixed and 114 continuous
Cbc0038I Full problem 463 rows 332 columns, reduced to 287 rows 168 columns - too large
Cbc0038I Mini branch and bound did not improve solution (0.02 seconds)
Cbc0038I Full problem 464 rows 332 columns, reduced to 464 rows 332 columns - too large
Cbc0038I After 0.03 seconds - Feasibility pump exiting - took 0.02 seconds
Cbc0031I 24 added rows had average density of 56.416667
Cbc0013I At root node, 24 cuts changed objective from 6 to 8 in 100 passes
Cbc0014I Cut generator 0 (Probing) - 323 row cuts average 2.3 elements, 0 column cuts (0 active)  in 0.120 seconds - new frequency is 1
Cbc0014I Cut generator 1 (Gomory) - 1530 row cuts average 170.6 elements, 0 column cuts (0 active)  in 0.071 seconds - new frequency is 1
Cbc0014I Cut generator 2 (Knapsack) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.014 seconds - new frequency is -100
Cbc0014I Cut generator 3 (Clique) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.003 seconds - new frequency is -100
Cbc0014I Cut generator 4 (MixedIntegerRounding2) - 3 row cuts average 8.0 elements, 0 column cuts (0 active)  in 0.036 seconds - new frequency is -100
Cbc0014I Cut generator 5 (FlowCover) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.043 seconds - new frequency is -100
Cbc0014I Cut generator 6 (TwoMirCuts) - 291 row cuts average 67.1 elements, 0 column cuts (0 active)  in 0.026 seconds - new frequency is 1
Cbc0010I After 0 nodes, 1 on tree, 1e+50 best solution, best possible 8 (0.82 seconds)
Cbc0012I Integer solution of 19 found by DiveCoefficient after 10553 iterations and 5 nodes (1.16 seconds)
Cbc0038I Full problem 463 rows 332 columns, reduced to 403 rows 253 columns - too large
Cbc0012I Integer solution of 18 found by DiveCoefficient after 10558 iterations and 6 nodes (1.18 seconds)
Cbc0016I Integer solution of 16 found by strong branching after 15117 iterations and 40 nodes (1.57 seconds)
Cbc0038I Full problem 463 rows 332 columns, reduced to 279 rows 153 columns - 5 fixed gives 246, 132 - ok now
Cbc0004I Integer solution of 12 found after 17131 iterations and 81 nodes (1.70 seconds)
Cbc0038I Full problem 463 rows 332 columns, reduced to 205 rows 107 columns
Cbc0038I Full problem 463 rows 332 columns, reduced to 264 rows 143 columns - 2 fixed gives 244, 130 - ok now
Cbc0038I Full problem 463 rows 332 columns, reduced to 226 rows 127 columns
Cbc0038I Full problem 463 rows 332 columns, reduced to 275 rows 148 columns - 1 fixed gives 272, 146 - still too large
Cbc0038I Full problem 463 rows 332 columns, reduced to 270 rows 146 columns - too large
Cbc0038I Full problem 463 rows 332 columns, reduced to 236 rows 127 columns
Cbc0038I Full problem 463 rows 332 columns, reduced to 231 rows 125 columns
Cbc0038I Full problem 463 rows 332 columns, reduced to 317 rows 182 columns - 3 fixed gives 292, 166 - still too large
Cbc0038I Full problem 463 rows 332 columns, reduced to 288 rows 166 columns - too large
Cbc0010I After 1000 nodes, 11 on tree, 12 best solution, best possible 8 (4.15 seconds)
Cbc0038I Full problem 463 rows 332 columns, reduced to 304 rows 166 columns - 2 fixed gives 290, 158 - still too large
Cbc0038I Full problem 463 rows 332 columns, reduced to 287 rows 158 columns - too large
Cbc0038I Full problem 463 rows 332 columns, reduced to 364 rows 216 columns - 2 fixed gives 347, 203 - still too large
Cbc0038I Full problem 463 rows 332 columns, reduced to 347 rows 203 columns - too large
Cbc0038I Full problem 463 rows 332 columns, reduced to 372 rows 226 columns - 3 fixed gives 355, 216 - still too large
Cbc0038I Full problem 463 rows 332 columns, reduced to 355 rows 216 columns - too large
Cbc0038I Full problem 463 rows 332 columns, reduced to 291 rows 155 columns - 3 fixed gives 268, 138 - still too large
Cbc0038I Full problem 463 rows 332 columns, reduced to 265 rows 138 columns - too large
Cbc0010I After 2000 nodes, 21 on tree, 12 best solution, best possible 8 (6.05 seconds)
Cbc0038I Full problem 463 rows 332 columns, reduced to 261 rows 138 columns - 4 fixed gives 234, 117 - ok now
Cbc0038I Full problem 463 rows 332 columns, reduced to 219 rows 117 columns
Cbc0010I After 3000 nodes, 14 on tree, 12 best solution, best possible 8 (7.34 seconds)
Cbc0038I Full problem 463 rows 332 columns, reduced to 235 rows 129 columns
Cbc0010I After 4000 nodes, 13 on tree, 12 best solution, best possible 8 (8.75 seconds)
Cbc0038I Full problem 463 rows 332 columns, reduced to 277 rows 144 columns - 4 fixed gives 243, 124 - ok now
Cbc0038I Full problem 463 rows 332 columns, reduced to 229 rows 124 columns
Cbc0010I After 5000 nodes, 14 on tree, 12 best solution, best possible 8 (10.09 seconds)
Cbc0004I Integer solution of 11 found after 285152 iterations and 5174 nodes (10.35 seconds)
Cbc0001I Search completed - best objective 11, took 286086 iterations and 5185 nodes (10.41 seconds)
Cbc0032I Strong branching done 3520 times (78869 iterations), fathomed 33 nodes and fixed 260 variables
Cbc0035I Maximum depth 41, 7 variables fixed on reduced cost
Cuts at root node changed objective from 6 to 8
Probing was tried 5564 times and created 73868 cuts of which 0 were active after adding rounds of cuts (0.910 seconds)
Gomory was tried 4529 times and created 25863 cuts of which 0 were active after adding rounds of cuts (0.602 seconds)
Knapsack was tried 100 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.014 seconds)
Clique was tried 100 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.003 seconds)
MixedIntegerRounding2 was tried 100 times and created 3 cuts of which 0 were active after adding rounds of cuts (0.036 seconds)
FlowCover was tried 100 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.043 seconds)
TwoMirCuts was tried 4529 times and created 463 cuts of which 0 were active after adding rounds of cuts (0.563 seconds)
ZeroHalf was tried 1 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
ImplicationCuts was tried 272 times and created 495 cuts of which 0 were active after adding rounds of cuts (0.002 seconds)

Result - Optimal solution found

Objective value:                11.00000000
Enumerated nodes:               5185
Total iterations:               286086
Time (CPU seconds):             10.43
Time (Wallclock seconds):       10.96

Total time (CPU seconds):       10.43   (Wallclock seconds):       10.96

Rectangle 0: (4.0, 7.0)
Rectangle 1: (8.0, 7.0)
Rectangle 2: (3.0, 0.0)
Rectangle 3: (5.0, 0.0)
Rectangle 4: (0.0, 0.0)
Rectangle 5: (4.0, 2.0)
Rectangle 6: (0.0, 3.0)
Rectangle 7: (7.0, 0.0)
total_length : Size=1, Index=None, Active=True
    Key  : Active : Value
    None :   True :  11.0
Click to see the solution to the activity
TransformationFactory('gdp.hull').apply_to(model)

2.2.4. Discussion Questions#

  1. What is the advantage of using the decorator notation for optimization problems?

  2. How do disjunctions affect the degree of freedom analysis?

  3. Why is it necessary to make separate variables for length and width?

  4. Compare the outputs of Big-M and Convex Hull. How are they different (if at all)?

Click to see the ideas for the discussion questions

  1. Decorators are a more compact (less typing) way to declare components in Pyomo.

  2. Disjunctions change the number of constraints.

  3. The coordinates for length and width differ.

  4. It gives the same optimal solution, but convex hull requires more iterations (for this problem and solver)