Contents

Integer Programming with Simple Branch and Bound

Contents

8.1. Integer Programming with Simple Branch and Bound#

\[\begin{split}\begin{align*} \min \quad & Z = x + y_1 + 3 y_2 + 2 y_3 \\ \mathrm{s.t.} \quad & -x + 3 y_1 + 2 y_2 + y_3 \leq 0 \\ & -5 y_1 - 8 y_2 - 3 y_3 \leq -9 \\ & x \geq 0, y \in \{0,1\}^3 \end{align*}\end{split}\]

from pyomo.environ import *
from pyomo.opt import SolverStatus, TerminationCondition

def create_relaxation():
    
    ## Create Pyomo Model
    m = ConcreteModel()
    
    ## Declare variables (all continous for now)
    m.x = Var(domain=NonNegativeReals)
    m.y1 = Var(bounds=(0,1))
    m.y2 = Var(bounds=(0,1))
    m.y3 = Var(bounds=(0,1))
    
    ## Declare constraints
    def con1_rule(m):
        return -1.0*m.x + 3.0*m.y1 + 2.0*m.y2 + m.y3 <= 0
    m.con1 = Constraint(rule=con1_rule)
    
    def con2_rule(m):
        return -5.0*m.y1 - 8.0*m.y2 - 3.0*m.y3 <= -9
    m.con2 = Constraint(rule=con2_rule)
    
    ## Declare objective
    def obj_rule(m):
        return m.x + m.y1 + 3*m.y2 + 2*m.y3
    
    m.obj = Objective(rule=obj_rule,sense=minimize)
    
    return m

def solve_print(m,verbose=False):
    
    # Solve the model
    opt = SolverFactory('cbc')
    results = opt.solve(m, tee=verbose)

    if (results.solver.status == SolverStatus.ok) and (results.solver.termination_condition == TerminationCondition.optimal):
        # Print solution when the solution is optimal
        print("x = ",value(m.x))
        print("y1 = ",value(m.y1))
        print("y2 = ",value(m.y2))
        print("y3 = ",value(m.y3))
        print("Z = ",value(m.obj))
    
    elif (results.solver.termination_condition == TerminationCondition.infeasible):
        print("Infeasible.")
        
    else:
        # Something else is wrong
        print('Solver Status:',result.solver.status)
    
    # m.pprint()

8.1.1. Node 1 (Root)#

Full LP relaxation.

m = create_relaxation()
solve_print(m,False)

x =  2.6
y1 =  0.2
y2 =  1.0
y3 =  0.0
Z =  5.800000000000001

8.1.2. Node 2#

m = create_relaxation()
m.y1.fix(0.0)
solve_print(m,False)

x =  2.3333333
y1 =  0.0
y2 =  1.0
y3 =  0.33333333
Z =  5.999999959999999

8.1.3. Node 3#

m = create_relaxation()
m.y1.fix(1.0)
solve_print(m,False)

x =  4.0
y1 =  1.0
y2 =  0.5
y3 =  0.0
Z =  6.5

8.1.4. Node 4#

m = create_relaxation()
m.y1.fix(0.0)
m.y3.fix(0.0)
solve_print(m,False)

WARNING: Loading a SolverResults object with a warning status into
    model.name="unknown";
      - termination condition: infeasible
      - message from solver: <undefined>
Infeasible.

8.1.5. Node 5#

m = create_relaxation()
m.y1.fix(0.0)
m.y3.fix(1.0)
solve_print(m,False)

x =  2.5
y1 =  0.0
y2 =  0.75
y3 =  1.0
Z =  6.75

8.1.6. Node 6#

m = create_relaxation()
m.y1.fix(1.0)
m.y2.fix(0.0)
solve_print(m,False)

WARNING: Loading a SolverResults object with a warning status into
    model.name="unknown";
      - termination condition: infeasible
      - message from solver: <undefined>
Infeasible.

8.1.7. Node 7#

m = create_relaxation()
m.y1.fix(1.0)
m.y2.fix(1.0)
solve_print(m,False)

x =  5.0
y1 =  1.0
y2 =  1.0
y3 =  0.0
Z =  9.0

8.1.8. Node 8#

m = create_relaxation()
m.y1.fix(0.0)
m.y3.fix(1.0)
m.y2.fix(0.0)
solve_print(m,False)

WARNING: Loading a SolverResults object with a warning status into
    model.name="unknown";
      - termination condition: infeasible
      - message from solver: <undefined>
Infeasible.

8.1.9. Node 9#

m = create_relaxation()
m.y1.fix(0.0)
m.y3.fix(1.0)
m.y2.fix(1.0)
solve_print(m,False)

x =  3.0
y1 =  0.0
y2 =  1.0
y3 =  1.0
Z =  8.0