GEKKO 箱平衡优化

Question

我有一个与工作相关的问题，我正在尝试使用 GEKKO 等优化包来解决。我正在尝试平衡 3 个整数箱，以便它们的总和尽可能接近（如果不相等的话）。

• 通过将整数从一个容器移动到另一个容器来实现平衡。
• 这些整数要么是 1、2 要么 3，并且每个整数都有一个唯一的标识符，因此我们可以跟踪它最终进入哪个 bin。
• 垃圾箱的长度不需要与开始时相同。
• 我无法将整数的一部分移动到新的 bin 中（例如：如果 bin 是 [2,3]，我无法从中移动 1）。
• 最后，我也想尽量减少移动次数（例如：我宁愿从 bin 1 中移动一个 3，也不愿移动三个 1）。我试图将其视为二进制成本变量，因此如果整数保留在其容器中，则它不花费任何成本 (0)，但如果它移动，则花费 1。

我正在尝试使用 GEKKO 在 Python 中编写此代码，但这是我第一次尝试使用此类包，其中很多内容超出了我的理解范围。理想情况下，我希望将重新平衡的垃圾箱作为输出，以查看平衡是如何完成的。我已经写了下面的内容来开始。它并不完整，但我只是想边写边写下概念。

下面是我一直在尝试使用的一些示例 bin 和 ID：

bin1 = [1,2,2,1,1,1,3,1]
bin2 = [2,2,1,1,3,1,1]
bin3 = [2,1,2,1,1,1,1]

bin1_IDs=[15,28,39,111,202,300,411,415]
bin2_IDs=[2,10,56,117,132,189,367]
bin3_IDs=[44,102,211,227,351,389,406]

# Original bin contents and their sums
bins = [bin1, bin2, bin3]
original_sums = [sum(bin) for bin in bins]
num_bins = len(bins)
num_items = sum(len(bin) for bin in bins)

# Create GEKKO model
m = GEKKO(remote=False)

# Decision variables
# x[i][j] = 1 if item i is in bin j, 0 otherwise

# Create binary decision variables
x = [[m.Var(integer=True, lb=0, ub=1) for j in range(num_bins)] for i in range(num_items)]

# Ensure each item is assigned to exactly one bin
for i in range(num_items):
    m.Equation(sum(x[i][j] for j in range(num_bins)) == 1)

# Solve the optimization problem
m.solve(disp=True)

# Output the results
for j in range(num_bins):
    print(f"Bin {j+1} contents: ", end="")
    for i in range(num_items):
        if x[i][j].value[0] > 0.5:  # Item assigned to bin j
            print(items[i], end=" ")

Answer 1

这里有一个使用

pyomo

的破解方法，它是线性编程的替代包。 我确信如果需要的话可以将其转录为 GEKKO，我只是不太熟悉 GEKKO 的语法。

这基本上是一个大型的二进制整数程序，其中二进制变量表示每个项目的移动（或不移动），因此关键变量是

x[item, orig, final]

，其中

orig, final

对被简化为仅可能的值该项目可以更严格地限制问题。

目标的关键指标是最小最大，其中我们减少最高容器的值，因此容器值被均匀地“压缩”。 移动会受到轻微的惩罚，必须仔细权衡最大仓值。

值得注意的是，如果您的“实际问题”比这大得多，可能需要其他技术，因为这可能无法扩展到巨大的问题规模，但它可以在一瞬间解决这个问题

代码：

import pyomo.environ as pyo

# DATA
bin1 = [1, 2, 2, 1, 1, 1, 3, 1]
bin2 = [2, 2, 1, 1, 3, 1, 1]
bin3 = [2, 1, 2, 1, 1, 1, 1]
# bin1 = [0, 0, 0, 0, 0, 0, 0, 0]

bin1_IDs = [15, 28, 39, 111, 202, 300, 411, 415]
bin2_IDs = [2, 10, 56, 117, 132, 189, 367]
bin3_IDs = [44, 102, 211, 227, 351, 389, 406]

values = {}
values.update(dict(zip(bin1_IDs, bin1)))
values.update(dict(zip(bin2_IDs, bin2)))
values.update(dict(zip(bin3_IDs, bin3)))

orig_loc = {}
orig_loc.update({item: "b1" for item in bin1_IDs})
orig_loc.update({item: "b2" for item in bin2_IDs})
orig_loc.update({item: "b3" for item in bin3_IDs})

bins = ["b1", "b2", "b3"]
poss_moves = {
    item: {(orig, other) for other in bins} for item, orig in orig_loc.items()
}

all_moves = {(b, bb) for b in bins for bb in bins}
non_moves = {(b, b) for b in bins}


# MODEL
m = pyo.ConcreteModel("bin_shuffler")

# SETS
m.I = pyo.Set(initialize=values.keys(), doc="items")
m.B = pyo.Set(initialize=bins, doc="bin")
m.M = pyo.Set(within=m.B * m.B, initialize=all_moves, doc="moves")

# indexed set of the item : possible moves for that item
m.IM = pyo.Set(m.I, domain=m.M, initialize=poss_moves, doc="possible moves")
# a "flat" set of same for use in variable indexing
m.IM_flat = pyo.Set(
    domain=m.I * m.M, initialize={(item, move) for item in m.IM for move in m.IM[item]}
)

# PARAMS
m.value = pyo.Param(m.I, initialize=values)
move_cost = 0.01  # very small weight such that it never eclipses the max_bin value objective

# VARS
# item i makes move m
m.x = pyo.Var(m.IM_flat, domain=pyo.Binary)
m.max_value = pyo.Var()
m.move_count = pyo.Var()

# OBJ
# mini-max:  minimize the max sum of largest bin, and minimize moves w/ small penalty
m.obj = pyo.Objective(expr=m.max_value + move_cost * m.move_count, sense=pyo.minimize)

# CONSTRAINTS

# all items must make a move
@m.Constraint(m.I)
def make_move(m, i):
    return sum(m.x[i, move] for move in m.IM[i]) == 1


# count all of the moves that are not non-moves
m.set_move_count = pyo.Constraint(
    expr=m.move_count
    >= sum(m.x[i, move] for i in m.I for move in m.IM[i] if move not in non_moves)
)


# catch the max bin value
@m.Constraint(m.B)
def max_bin(m, bin):
    return m.max_value >= sum(
        m.value[i] * m.x[i, orig, final]
        for i in m.I
        for (orig, final) in m.IM[i]
        if final == bin
    )

# inspect it...
m.pprint()

# solve it...
opt = pyo.SolverFactory("appsi_highs")
res = opt.solve(m, tee=True)

# report it...
if pyo.check_optimal_termination(res):
    print(res)
    m.display()
    for i in m.I:
        for orig, final in m.IM[i]:
            if pyo.value(m.x[i, orig, final]) > 0.5 and orig != final:
                print(f"move {i} from {orig} to {final}")

    for b in m.B:
        # get the sum
        bin_total = sum(
            m.value[i] * pyo.value(m.x[i, orig, final])
            for i in m.I
            for (orig, final) in m.IM[i]
            if final == b
        )
        print(f"total value of bin {b}: {bin_total}")
else:
    print("solve failed")

最终结果（不是唯一的）：

move 415 from b1 to b3
total value of bin b1: 11.0
total value of bin b2: 11.0
total value of bin b3: 10.0