纸浆：最小化一组向量的最大值

问题描述

我有一个要解决的线性规划问题，它的所有数据都来自一个表。

该表的大小为(m*n)，如下所示：

    |    c0      c1       c2       c3      ...       cn        sum
--- + ------ + ------ + ------ + ------ + ------ + ------ +++ ----- +
r0  |                                                     |||  Σ r0 
r1  |                                                     |||  Σ r1
r2  |                                                     |||  Σ r2
r3  |                                                     |||  Σ r3
r4  |                                                     |||
 .  |                                                     |||
 .  |                                                     |||
 .  |                                                     |||
rm  |                                                     |||  Σ rm
------------------------------------------------------------------- +
max |max(c0)  max(c1)  max(c2)  max(c3)           max(cn) |||  Σ max(c0...n)

优化问题后，此表中的所有垃圾箱都将保留浮点值。

我正在尝试最小化每列(ΣMAX(c0...n))的最大值总和。

我已创建一个LpProblem：

problem = pulp.LpProblem("problem",pulp.LpMinimize)

我已经创建了LpVariables，表示表中的每个垃圾箱：

variables = pulp.LpVariable.dicts("bin",
                                  ((r,c) for r in rows for c in columns),
                                  lowBound=0,
                                  cat='Continuous')

我预先知道每一行的总和(ΣRx)，并且约束条件是一行的x的值必须等于ΣRx。作为这些数据的一个特征，只有一行中的索引子集可以对此ΣRX值做出贡献。例如，只有第0行中的箱子(0，1)和(0，3)可能具有非零值。这些投入箱的索引各行不同；某些行可能只有一个投入箱，而其他行有多个(或全部)投入箱。我已经通过为每一行创建约束来说明这一点。

for row in rows:
    column_set # a list of bin indexes for this row that make up the sum.
    variable_set = [ variables[(row,c)] for c in column_set ]
    problem += pulp.lpSum(variable_set) == row_sum # the sum of the row.

我的问题在于如何定义我的目标函数。由于Python的max()不适用于LpVariable对象，因此我尝试考虑如何获取任意列的最大值并将其分配给自己的LpVariable对象。

执行此操作的一种方法可能是遍历给定列中表示存储箱的每个LpVariable，执行类似v = variable.value()的操作并将所有v添加到列表中，然后对此列表执行max()并将LpVariable设置为等于该值，但这只会获得LpVariable的初始值，并且当求解器在solve()过程中更改数据时，这些最大值将不会动态更新。

我还尝试使用单独的LpVariable来表示每列的最大值，设置如下：

pulp.LpVariable("Max___{}".format(s),
                lowBound=max([v.value() for v in column]),
                upBound=max([v.value() for v in column]),
                cat=pulp.LpContinuous
               )

但同样，这似乎只是从每个LpVariable的初始条件中获取值，并对其运行solve()返回'infeasible'解决方案。

有什么建议吗？

---

解决方案

A高级说明：

• m rows, n cols
• 引入n新连续变量m_0, m_1, ..., m_(n-1)
• 添加表单的m*n新约束：
  • m_0 >= entry(r_0,c_0)
  • m_0 >= entry(r_1,c_0)
  • ...
  • m_0 >= entry(r_(m-1),c_0)
  • ...
  • ...
  • m_1 >= entry(r_0,c_1)
  • m_1 >= entry(r_1,c_1)
  • ...
  • m_1 >= entry(r_(m-1),c_1)
  • ...
• 目标：
  • minimize(m_0 + m_1 + ... + m_(n-1))

备注：

• 只有当每个m都被求解器以某种方式向下推时，这才起作用！
  • 此处：最小化总和->确定！
• 它独立于条目的类型(二进制、整数、连续)