Knapsack: Exercise 1.5 - NLP vs MIP Solvers

Here we solve the knapsack problem with Ipopt instead of CBC. What happened? Why?

Learning Objectives:

• Understand different solver types (NLP vs MIP)

• Learn when to use continuous vs discrete solvers

• See the effects of solver choice on solution quality

• Understand the importance of matching problem type to solver type

import pyomo.environ as pyo
import os
os.environ['PATH'] += ':solvers'
A = ['hammer', 'wrench', 'screwdriver', 'towel']
b = {'hammer':8, 'wrench':3, 'screwdriver':6, 'towel':11}
w = {'hammer':5, 'wrench':7, 'screwdriver':4, 'towel':3}
W_max = 14

model = pyo.ConcreteModel()
model.x = pyo.Var( A, within=pyo.Binary )

model.obj = pyo.Objective(
    expr = sum( b[i]*model.x[i] for i in A ), 
    sense = pyo.maximize )

model.weight_con = pyo.Constraint(
    expr = sum( w[i]*model.x[i] for i in A ) <= W_max )

opt = pyo.SolverFactory('ipopt')
opt_success = opt.solve(model)

model.pprint()

1 Var Declarations
    x : Size=4, Index={hammer, wrench, screwdriver, towel}
        Key         : Lower : Value              : Upper : Fixed : Stale : Domain
             hammer :     0 : 1.0000000095722053 :     1 : False : False : Binary
        screwdriver :     0 : 1.0000000094153156 :     1 : False : False : Binary
              towel :     0 :  1.000000009742034 :     1 : False : False : Binary
             wrench :     0 : 0.2857142884855867 :     1 : False : False : Binary

1 Objective Declarations
    obj : Size=1, Index=None, Active=True
        Key  : Active : Sense    : Expression
        None :   True : maximize : 8*x[hammer] + 3*x[wrench] + 6*x[screwdriver] + 11*x[towel]

1 Constraint Declarations
    weight_con : Size=1, Index=None, Active=True
        Key  : Lower : Body                                                      : Upper : Active
        None :  -Inf : 5*x[hammer] + 7*x[wrench] + 4*x[screwdriver] + 3*x[towel] :  14.0 :   True

3 Declarations: x obj weight_con