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

• Official comment

  

  Simranjit Kaur

  • Gurobi Staff

  November 13, 2026 01:47

  This post is more than two years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support.
• 

  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

Post is closed for comments.