1D Bin Packing Problem, big interval between bins filled

Answered

Ma. Julie Anne Gala

March 09, 2023 08:30 Edited

• 
• 
• 

Hi,

I have the following code on Python for a 1D bin packing problem:

import gurobipy as gp
from gurobipy import GRB
import numpy as np

n = 10
UB = n
c = 10
w = [1, 2, 3, 4, 5, 1, 3, 3, 4, 2]

model = gp.Model ()
x = model.addVars(n, UB, vtype=GRB.BINARY)
y = model.addVars (UB, vtype=GRB.BINARY)

# minimize the number of bins used
model.setObjective(gp.quicksum(y[j] for j in range(UB) ), GRB.MINIMIZE)

# pack each item in exactly one bin
model.addConstrs(gp.quicksum(x[i,j] for j in range(UB)) == 1 for i in range(n))

# bin capacity constraint
model.addConstrs(gp.quicksum(w[i] * x[i,j] for i in range(n)) <= c * y[j] for j in range (UB))

# solve
model.optimize()

bin_for_item = [-1 for i in range(n)]

for i in range(n):
    for j in range(UB):
        if x[i,j].X > 0.5:
            bin_for_item[i] = j

print(f"n bins = {model. ObjVal}")
print(f"Bin assignment for each item: {bin_for_item}")

 

When running the code, I do get an optimal solution but the items are packed in bins like this:

 

Bin assignment for each item: [8, 1, 8, 8, 1, 1, 8, 1, 8, 5]

Is there a way to modify the optimization so bins are filled sequentially?

0

• 

  Mario Ruthmair

  • Gurobi Staff

  March 13, 2023 09:36

  Hi Julie,

  You could enforce an order for bins to be used in the sense that bin i+1 is only allowed to be used if bin i is already used:

  model.addConstrs( y[i+1] <= y[i] for i in range(UB-1), name="order")

  Best regards,
  Mario

  0

Please sign in to leave a comment.