I am trying to solve the following bin packing constraint optimization problem using Pyomo SCIP solver. Besides the objective of reducing the number of bins used for packing, I would also like to minimize the maximum values of the items of each bin.
obj2 = sum(max(model.bins_loc[i, j] * item_values[i] for i in range(num_items)) for j in range(max_num_bins))
bins_loc - binary variable of the combination of number of items and maximum number of bins. Indicates is item is assigned to bin
But I understand that SCIP does not allow the use of MAX function since it is deemed as a boolean function and will raise the follow error:
raise PyomoException("""
Cannot convert non-constant Pyomo expression (%s) to bool.
This error is usually caused by using a Var, unit, or mutable Param in a
Boolean context such as an "if" statement, or when checking container
membership or equality.
Full code to recreate problem:
import pyomo.environ as pyo
from pyomo.opt import SolverFactory
bin_capacity = 8
item_weights = [2, 4, 2, 5, 1, 1, 3, 4, 2, 3]
item_values = [10, 15, 20, 34, 22, 1, 23, 3, 25, 90]
num_items = len(item_weights)
max_num_bins = len(item_weights)
model = pyo.ConcreteModel()
#variables
model.bins_loc = pyo.Var(range(num_items), range(max_num_bins), within=pyo.Binary)
model.bins_on = pyo.Var(range(max_num_bins), within=pyo.Binary)
#constraints
model.bins_on_constraint = pyo.ConstraintList()
for j in range(max_num_bins):
model.bins_on_constraint.add(expr= (1 - model.bins_on[j]) * (sum(model.bins_loc[i, j] for i in range(num_items))) <= 0)
model.capacity_exceed_constraint = pyo.ConstraintList()
for j in range(max_num_bins): model.capacity_exceed_constraint.add(expr= sum((model.bins_loc[i, j] * item_weights[i]) for i in range(num_items)) <= bin_capacity)
if max_num_bins > 1:
model.onebin_per_item_constraint = pyo.ConstraintList()
for i in range(num_items): model.onebin_per_item_constraint.add(expr= sum(model.bins_loc[i, j] for j in range(max_num_bins)) == 1)
#objectives
obj1 = sum(model.bins_on[j] for j in range(max_num_bins))
obj2 = sum(max(model.bins_loc[i, j] * item_values[i] for i in range(num_items)) for j in range(max_num_bins))
model.obj = pyo.Objective(expr= obj1+obj2, sense=pyo.minimize)
opt = SolverFactory('scipampl', executable=r'scipampl.exe')
opt.solve(model)
How should I rewrite my variables and constraints to solve this problem?
max
is a nonlinear function. Better is to introduce an extra variable z[j]
and write:
z[j] >= bins_loc[i, j] * item_values[i] for all i,j
and then use
obj2 = sum(z[j])
This works because we are minimizing obj2. This is a very common modeling trick. Well worth knowing about it.