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/CBE60499/main/notebooks/helper.py"
    import helper
    helper.install_idaes()
    helper.install_ipopt()
    # helper.install_cbc()
    helper.download_figures(['strip_packing.png'])

--2023-05-04 18:16:25--  https://raw.githubusercontent.com/ndcbe/CBE60499/main/notebooks/helper.py
Resolving raw.githubusercontent.com (raw.githubusercontent.com)... 185.199.108.133, 185.199.109.133, 185.199.110.133, ...
Connecting to raw.githubusercontent.com (raw.githubusercontent.com)|185.199.108.133|:443... connected.
HTTP request sent, awaiting response... 200 OK
Length: 7171 (7.0K) [text/plain]
Saving to: ‘helper.py’


helper.py             0%[                    ]       0  --.-KB/s               
helper.py           100%[===================>]   7.00K  --.-KB/s    in 0s      

2023-05-04 18:16:26 (65.2 MB/s) - ‘helper.py’ saved [7171/7171]

Installing idaes via pip...
idaes was successfully installed
Running idaes get-extensions to install Ipopt, k_aug, and more...
Ipopt 3.13.2 (x86_64-pc-linux-gnu), ASL(20190605)

[K_AUG] 0.1.0, Part of the IDAES PSE framework
Please visit https://idaes.org/ (x86_64-pc-linux-gnu), ASL(20190605)

Couenne 0.5.8 -- an Open-Source solver for Mixed Integer Nonlinear Optimization
Mailing list: couenne@list.coin-or.org
Instructions: http://www.coin-or.org/Couenne
couenne (x86_64-pc-linux-gnu), ASL(20190605)

Bonmin 1.8.8 using Cbc 2.10.8 and Ipopt 3.13.2
bonmin (x86_64-pc-linux-gnu), ASL(20190605)

Ipopt 3.13.3 (x86_64-pc-linux-gnu), ASL(20190605)

ipopt was successfully installed
k_aug was successfuly installed
cbc was successfuly installed
clp was successfuly installed
bonmin was successfuly installed
couenne was successfuly installed
ipopt_l1 was successfuly installed
 
Checking for ./figures/strip_packing.png
	Creating folder ./figures
	Downloading https://raw.githubusercontent.com/ndcbe/CBE60499/main/docs/figures/strip_packing.png

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

$\(\text{Additional Information}\)$	$\(\text{Link}\)$
$\(\text{Reference}\)$	https://www.minlp.org/library/problem/index.php?i=121&lib=GDP
$\(\text{Description}\)$	https://www.minlp.org/problems/ver/156/over/Strip-Packing-Overview.pdf
$\(\text{Results}\)$	https://www.minlp.org/problems/ver/156/results/Strip-Packing-Results.pdf
$\(\text{Problem Formulation}\)$	https://www.sciencedirect.com/science/article/pii/S0098135405000992

2.2.3.1. Problem Statement

\( \text{Min} \ lt \tag{1}\)

\( \text{s.t.} \ lt \geq x_{i} + L_{i} \ \ \forall i \in N \tag{2}\)

(2.18)\[\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} \tag{3} \end{equation}\]

(2.19)\[\begin{equation} x_{i} \leq UB_{i} - L_{i} \ \ \forall i \in N \tag{4} \end{equation}\]

(2.20)\[\begin{equation} H_{i} \leq y_{i} \leq W \ \ \forall i \in N \tag{5} \end{equation}\]

(2.21)\[\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}\]

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

• 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.

• 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\) (3).

• Note that the y-coordinate of every rectange is bounded from above by the fixed width of the strip \(W\) (5), 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 (4).

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

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

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.8 
Build Date: Feb  3 2023 

command line - /content/cbc -printingOptions all -import /tmp/tmpyvqxaz49.pyomo.lp -stat=1 -solve -solu /tmp/tmpyvqxaz49.pyomo.soln (default strategy 1)
Option for printingOptions changed from normal to all
Presolve 148 (-1) rows, 129 (-1) columns and 464 (-1) elements
Statistics for presolved model
Original problem has 112 integers (112 of which binary)
Presolved 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.6138
Cbc0038I Pass   1: suminf.    5.20000 (20) obj. 11 iterations 30
Cbc0038I Pass   2: suminf.    2.20000 (10) obj. 12 iterations 27
Cbc0038I Pass   3: suminf.    2.00000 (10) obj. 12 iterations 4
Cbc0038I Pass   4: suminf.    1.60000 (8) obj. 12 iterations 10
Cbc0038I Pass   5: suminf.    1.40000 (8) obj. 12 iterations 3
Cbc0038I Pass   6: suminf.    2.20000 (8) obj. 12 iterations 7
Cbc0038I Pass   7: suminf.    1.80000 (8) obj. 12 iterations 4
Cbc0038I Pass   8: suminf.    1.20000 (6) obj. 14 iterations 12
Cbc0038I Pass   9: suminf.    0.80000 (4) obj. 14 iterations 6
Cbc0038I Pass  10: suminf.    0.80000 (4) obj. 14 iterations 4
Cbc0038I Pass  11: suminf.    2.80000 (10) obj. 22 iterations 37
Cbc0038I Pass  12: suminf.    2.80000 (12) obj. 22 iterations 11
Cbc0038I Pass  13: suminf.    1.00000 (4) obj. 23 iterations 14
Cbc0038I Pass  14: suminf.    0.40000 (2) obj. 23 iterations 4
Cbc0038I Pass  15: suminf.    0.40000 (2) obj. 23 iterations 3
Cbc0038I Pass  16: suminf.    4.59723 (21) obj. 13 iterations 63
Cbc0038I Pass  17: suminf.    3.33404 (16) obj. 12 iterations 19
Cbc0038I Pass  18: suminf.    1.05714 (5) obj. 16 iterations 23
Cbc0038I Pass  19: suminf.    0.20000 (2) obj. 19 iterations 6
Cbc0038I Pass  20: suminf.    0.35714 (1) obj. 17 iterations 4
Cbc0038I Solution found of 17
Cbc0038I Relaxing continuous gives 17
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 87 rows 68 columns
Cbc0038I Mini branch and bound improved solution from 17 to 12 (0.07 seconds)
Cbc0038I Round again with cutoff of 11.2
Cbc0038I Pass  21: suminf.    5.20000 (20) obj. 11 iterations 0
Cbc0038I Pass  22: suminf.    2.60000 (14) obj. 11 iterations 17
Cbc0038I Pass  23: suminf.    2.60000 (14) obj. 11 iterations 0
Cbc0038I Pass  24: suminf.    1.68473 (11) obj. 11.2 iterations 20
Cbc0038I Pass  25: suminf.    1.48473 (11) obj. 11.2 iterations 3
Cbc0038I Pass  26: suminf.    2.40000 (10) obj. 11.2 iterations 11
Cbc0038I Pass  27: suminf.    2.40000 (10) obj. 11.2 iterations 4
Cbc0038I Pass  28: suminf.    2.40000 (10) obj. 11.2 iterations 3
Cbc0038I Pass  29: suminf.    5.86207 (24) obj. 11.2 iterations 42
Cbc0038I Pass  30: suminf.    2.91137 (17) obj. 11.2 iterations 22
Cbc0038I Pass  31: suminf.    1.73104 (8) obj. 11.2 iterations 23
Cbc0038I Pass  32: suminf.    1.53104 (8) obj. 11.2 iterations 6
Cbc0038I Pass  33: suminf.    2.55985 (12) obj. 11.2 iterations 16
Cbc0038I Pass  34: suminf.    1.55985 (10) obj. 11.2 iterations 4
Cbc0038I Pass  35: suminf.    1.55985 (10) obj. 11.2 iterations 3
Cbc0038I Pass  36: suminf.    2.11256 (10) obj. 11.2 iterations 15
Cbc0038I Pass  37: suminf.    1.91256 (10) obj. 11.2 iterations 6
Cbc0038I Pass  38: suminf.    2.55985 (12) obj. 11.2 iterations 15
Cbc0038I Pass  39: suminf.    1.55985 (10) obj. 11.2 iterations 5
Cbc0038I Pass  40: suminf.    1.55985 (10) obj. 11.2 iterations 1
Cbc0038I Pass  41: suminf.    2.11256 (10) obj. 11.2 iterations 13
Cbc0038I Pass  42: suminf.    1.91256 (10) obj. 11.2 iterations 9
Cbc0038I Pass  43: suminf.    2.55985 (12) obj. 11.2 iterations 17
Cbc0038I Pass  44: suminf.    1.55985 (10) obj. 11.2 iterations 4
Cbc0038I Pass  45: suminf.    1.55985 (10) obj. 11.2 iterations 2
Cbc0038I Pass  46: suminf.    2.11256 (10) obj. 11.2 iterations 13
Cbc0038I Pass  47: suminf.    1.91256 (10) obj. 11.2 iterations 7
Cbc0038I Pass  48: suminf.    2.55985 (12) obj. 11.2 iterations 16
Cbc0038I Pass  49: suminf.    1.55985 (10) obj. 11.2 iterations 4
Cbc0038I Pass  50: suminf.    1.55985 (10) obj. 11.2 iterations 2
Cbc0038I No solution found this major pass
Cbc0038I Before mini branch and bound, 31 integers at bound fixed and 1 continuous
Cbc0038I Mini branch and bound did not improve solution (0.11 seconds)
Cbc0038I After 0.11 seconds - Feasibility pump exiting with objective of 12 - took 0.10 seconds
Cbc0012I Integer solution of 12 found by feasibility pump after 0 iterations and 0 nodes (0.11 seconds)
Cbc0038I Full problem 139 rows 120 columns, reduced to 84 rows 65 columns
Cbc0031I 53 added rows had average density of 5.9433962
Cbc0013I At root node, 53 cuts changed objective from 4 to 8 in 32 passes
Cbc0014I Cut generator 0 (Probing) - 1033 row cuts average 2.7 elements, 0 column cuts (0 active)  in 0.024 seconds - new frequency is 1
Cbc0014I Cut generator 1 (Gomory) - 414 row cuts average 27.6 elements, 0 column cuts (0 active)  in 0.014 seconds - new frequency is 1
Cbc0014I Cut generator 2 (Knapsack) - 0 row cuts average 0.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.002 seconds - new frequency is -100
Cbc0014I Cut generator 4 (MixedIntegerRounding2) - 224 row cuts average 2.6 elements, 0 column cuts (0 active)  in 0.009 seconds - new frequency is 1
Cbc0014I Cut generator 5 (FlowCover) - 8 row cuts average 2.0 elements, 0 column cuts (0 active)  in 0.007 seconds - new frequency is -100
Cbc0014I Cut generator 6 (TwoMirCuts) - 336 row cuts average 15.0 elements, 0 column cuts (0 active)  in 0.013 seconds - new frequency is 1
Cbc0010I After 0 nodes, 1 on tree, 12 best solution, best possible 8 (0.32 seconds)
Cbc0004I Integer solution of 11 found after 3238 iterations and 26 nodes (0.61 seconds)
Cbc0001I Search completed - best objective 11, took 3305 iterations and 28 nodes (0.62 seconds)
Cbc0032I Strong branching done 576 times (7536 iterations), fathomed 0 nodes and fixed 2 variables
Cbc0035I Maximum depth 18, 0 variables fixed on reduced cost
Cuts at root node changed objective from 4 to 8
Probing was tried 73 times and created 1721 cuts of which 0 were active after adding rounds of cuts (0.040 seconds)
Gomory was tried 70 times and created 519 cuts of which 0 were active after adding rounds of cuts (0.024 seconds)
Knapsack was tried 32 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.005 seconds)
Clique was tried 32 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.002 seconds)
MixedIntegerRounding2 was tried 70 times and created 329 cuts of which 0 were active after adding rounds of cuts (0.017 seconds)
FlowCover was tried 32 times and created 8 cuts of which 0 were active after adding rounds of cuts (0.007 seconds)
TwoMirCuts was tried 70 times and created 469 cuts of which 0 were active after adding rounds of cuts (0.019 seconds)
ZeroHalf was tried 1 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.001 seconds)
ImplicationCuts was tried 20 times and created 26 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)

Result - Optimal solution found

Objective value:                11.00000000
Enumerated nodes:               28
Total iterations:               3305
Time (CPU seconds):             0.62
Time (Wallclock seconds):       0.67

Total time (CPU seconds):       0.63   (Wallclock seconds):       0.67

Rectangle 0: (3.0, 0.0)
Rectangle 1: (8.0, 7.0)
Rectangle 2: (7.0, 0.0)
Rectangle 3: (9.0, 0.0)
Rectangle 4: (0.0, 0.0)
Rectangle 5: (8.0, 2.0)
Rectangle 6: (0.0, 3.0)
Rectangle 7: (4.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.8 
Build Date: Feb  3 2023 

command line - /content/cbc -printingOptions all -import /tmp/tmp5_k8jzkf.pyomo.lp -stat=1 -solve -solu /tmp/tmp5_k8jzkf.pyomo.soln (default strategy 1)
Option for printingOptions changed from normal to all
Presolve 484 (-113) rows, 353 (-113) columns and 1696 (-1) 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 - 68 integers unsatisfied sum - 16.8341
Cbc0038I Pass   1: suminf.    6.94830 (28) obj. 11.0857 iterations 196
Cbc0038I Pass   2: suminf.    5.37687 (20) obj. 11.0857 iterations 27
Cbc0038I Pass   3: suminf.    3.34286 (12) obj. 18.8571 iterations 27
Cbc0038I Pass   4: suminf.    3.19507 (13) obj. 14.8571 iterations 1
Cbc0038I Pass   5: suminf.    3.32266 (13) obj. 19.9286 iterations 58
Cbc0038I Pass   6: suminf.    3.13218 (10) obj. 19.9286 iterations 20
Cbc0038I Pass   7: suminf.    1.14286 (4) obj. 18 iterations 24
Cbc0038I Pass   8: suminf.    1.14286 (4) obj. 18 iterations 9
Cbc0038I Pass   9: suminf.    1.14286 (4) obj. 18 iterations 14
Cbc0038I Pass  10: suminf.    1.71429 (6) obj. 22.1429 iterations 83
Cbc0038I Pass  11: suminf.    1.14286 (4) obj. 22.1429 iterations 10
Cbc0038I Pass  12: suminf.    1.67241 (11) obj. 16.1724 iterations 35
Cbc0038I Pass  13: suminf.    0.85714 (2) obj. 18 iterations 30
Cbc0038I Pass  14: suminf.    0.85714 (2) obj. 18 iterations 0
Cbc0038I Pass  15: suminf.    0.00000 (0) obj. 21 iterations 3
Cbc0038I Solution found of 21
Cbc0038I Relaxing continuous gives 21
Cbc0038I Before mini branch and bound, 22 integers at bound fixed and 104 continuous
Cbc0038I Full problem 463 rows 332 columns, reduced to 376 rows 204 columns - 7 fixed gives 268, 149 - still too large
Cbc0038I Full problem 463 rows 332 columns, reduced to 210 rows 119 columns
Cbc0038I Mini branch and bound improved solution from 21 to 14 (0.08 seconds)
Cbc0038I Freeing continuous variables gives a solution of 14
Cbc0038I Round again with cutoff of 13.2
Cbc0038I Pass  16: suminf.    6.94830 (28) obj. 11.0857 iterations 0
Cbc0038I Pass  17: suminf.    5.37687 (20) obj. 11.0857 iterations 35
Cbc0038I Pass  18: suminf.    2.53251 (13) obj. 13.2 iterations 57
Cbc0038I Pass  19: suminf.    2.53251 (13) obj. 13.2 iterations 15
Cbc0038I Pass  20: suminf.    3.47143 (14) obj. 13.2 iterations 61
Cbc0038I Pass  21: suminf.    2.82233 (11) obj. 13.2 iterations 34
Cbc0038I Pass  22: suminf.    1.97241 (10) obj. 13.2 iterations 36
Cbc0038I Pass  23: suminf.    1.84433 (10) obj. 13.2 iterations 21
Cbc0038I Pass  24: suminf.    3.03673 (13) obj. 13.2 iterations 43
Cbc0038I Pass  25: suminf.    2.50509 (10) obj. 13.2 iterations 18
Cbc0038I Pass  26: suminf.    4.57253 (21) obj. 13.2 iterations 89
Cbc0038I Pass  27: suminf.    4.00110 (19) obj. 13.2 iterations 6
Cbc0038I Pass  28: suminf.    2.58591 (14) obj. 13.2 iterations 57
Cbc0038I Pass  29: suminf.    2.46798 (12) obj. 13.2 iterations 12
Cbc0038I Pass  30: suminf.    3.20131 (12) obj. 13.2 iterations 34
Cbc0038I Pass  31: suminf.    2.84321 (12) obj. 13.2 iterations 21
Cbc0038I Pass  32: suminf.    2.68941 (14) obj. 13.2 iterations 32
Cbc0038I Pass  33: suminf.    2.33005 (11) obj. 12.6207 iterations 16
Cbc0038I Pass  34: suminf.    3.97143 (19) obj. 13.2 iterations 47
Cbc0038I Pass  35: suminf.    2.94058 (16) obj. 13.2 iterations 23
Cbc0038I Pass  36: suminf.    2.63218 (13) obj. 13.2 iterations 56
Cbc0038I Pass  37: suminf.    2.52062 (13) obj. 13.2 iterations 12
Cbc0038I Pass  38: suminf.    3.12273 (14) obj. 13.2 iterations 34
Cbc0038I Pass  39: suminf.    2.22459 (12) obj. 13.2 iterations 25
Cbc0038I Pass  40: suminf.    3.00361 (14) obj. 13.2 iterations 31
Cbc0038I Pass  41: suminf.    2.90837 (13) obj. 13.2 iterations 8
Cbc0038I Pass  42: suminf.    1.71429 (6) obj. 13.2 iterations 26
Cbc0038I Pass  43: suminf.    0.83350 (6) obj. 13.2 iterations 14
Cbc0038I Pass  44: suminf.    2.23810 (8) obj. 13.2 iterations 24
Cbc0038I Pass  45: suminf.    1.57143 (5) obj. 13.2 iterations 12
Cbc0038I No solution found this major pass
Cbc0038I Before mini branch and bound, 20 integers at bound fixed and 96 continuous
Cbc0038I Mini branch and bound did not improve solution (0.20 seconds)
Cbc0038I After 0.20 seconds - Feasibility pump exiting with objective of 14 - took 0.18 seconds
Cbc0012I Integer solution of 14 found by feasibility pump after 0 iterations and 0 nodes (0.20 seconds)
Cbc0038I Full problem 463 rows 332 columns, reduced to 396 rows 247 columns - 23 fixed gives 225, 116 - ok now
Cbc0038I Full problem 463 rows 332 columns, reduced to 220 rows 111 columns
Cbc0031I 34 added rows had average density of 65.823529
Cbc0013I At root node, 34 cuts changed objective from 6 to 8 in 100 passes
Cbc0014I Cut generator 0 (Probing) - 573 row cuts average 2.9 elements, 0 column cuts (0 active)  in 0.143 seconds - new frequency is 1
Cbc0014I Cut generator 1 (Gomory) - 2335 row cuts average 181.7 elements, 0 column cuts (0 active)  in 0.384 seconds - new frequency is 1
Cbc0014I Cut generator 2 (Knapsack) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.022 seconds - new frequency is -100
Cbc0014I Cut generator 3 (Clique) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.008 seconds - new frequency is -100
Cbc0014I Cut generator 4 (MixedIntegerRounding2) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.176 seconds - new frequency is -100
Cbc0014I Cut generator 5 (FlowCover) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.104 seconds - new frequency is -100
Cbc0014I Cut generator 6 (TwoMirCuts) - 276 row cuts average 65.1 elements, 0 column cuts (0 active)  in 0.054 seconds - new frequency is 1
Cbc0010I After 0 nodes, 1 on tree, 14 best solution, best possible 8 (2.97 seconds)
Cbc0038I Full problem 463 rows 332 columns, reduced to 310 rows 171 columns - 15 fixed gives 213, 107 - ok now
Cbc0038I Full problem 463 rows 332 columns, reduced to 213 rows 107 columns
Cbc0038I Full problem 463 rows 332 columns, reduced to 338 rows 191 columns - 18 fixed gives 216, 109 - ok now
Cbc0038I Full problem 463 rows 332 columns, reduced to 213 rows 107 columns
Cbc0004I Integer solution of 13 found after 14982 iterations and 105 nodes (4.75 seconds)
Cbc0004I Integer solution of 12 found after 15000 iterations and 106 nodes (4.75 seconds)
Cbc0038I Full problem 463 rows 332 columns, reduced to 347 rows 197 columns - 4 fixed gives 327, 185 - still too large
Cbc0038I Full problem 463 rows 332 columns, reduced to 327 rows 185 columns - too large
Cbc0004I Integer solution of 11 found after 29977 iterations and 300 nodes (6.24 seconds)
Cbc0001I Search completed - best objective 11, took 31618 iterations and 309 nodes (6.40 seconds)
Cbc0032I Strong branching done 1244 times (30120 iterations), fathomed 0 nodes and fixed 15 variables
Cbc0035I Maximum depth 26, 1 variables fixed on reduced cost
Cuts at root node changed objective from 6 to 8
Probing was tried 483 times and created 6535 cuts of which 0 were active after adding rounds of cuts (0.301 seconds)
Gomory was tried 412 times and created 4116 cuts of which 0 were active after adding rounds of cuts (0.519 seconds)
Knapsack was tried 100 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.022 seconds)
Clique was tried 100 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.008 seconds)
MixedIntegerRounding2 was tried 100 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.176 seconds)
FlowCover was tried 100 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.104 seconds)
TwoMirCuts was tried 412 times and created 494 cuts of which 0 were active after adding rounds of cuts (0.153 seconds)
ZeroHalf was tried 1 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.001 seconds)
ImplicationCuts was tried 89 times and created 141 cuts of which 0 were active after adding rounds of cuts (0.002 seconds)

Result - Optimal solution found

Objective value:                11.00000000
Enumerated nodes:               309
Total iterations:               31618
Time (CPU seconds):             6.43
Time (Wallclock seconds):       11.35

Total time (CPU seconds):       6.44   (Wallclock seconds):       11.36

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

2.2.4. Discussion Questions

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

2. How do disjunctions affect a 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)?

# Discussion Questions
# Add your solution here