1D Bin Packing Problem, big interval between bins filled

回答済み

Ma. Julie Anne Gala

2023年03月09日 08:30 編集済み

• 
• 
• 

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

• 正式なコメント

  

  Simranjit Kaur

  • Gurobi Staff

  2026年11月13日 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

  2023年03月13日 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

投稿コメントは受け付けていません。