Search code examples
pyomoconstraint-programmingscip

How to rewrite MAX function for a constraint optimization problem in Python Pyomo SCIP?


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?


Solution

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