线性规划：我可以制定一个目标来同时最大化多个变量吗？
lif*_*med 1 algorithm mathematical-optimization linear-programming or-tools
假设我有以下系统说明的一些变量和约束：
灰线可以拉伸和收缩它们顶部的范围给定的量。蓝线只是端点，显示了灰线如何相互作用。
我的目标：我想使用线性规划来均匀地最大化灰线的大小，如图所示。你可以想象带有弹簧的灰色线条，它们都同样向外推。一个糟糕的解决方案是将所有蓝线尽可能推向一侧。请注意，此描述中有一点余地，并且可能有多种解决方案 - 我所需要的只是让它们合理均匀，并且不要让一个值最大化压扁其他所有内容。
我尝试的目标函数只是最大化线条大小的总和：
maximize: (B - A) + (C - B) + (C - A) + (D - C) + (E - B) + (E - D) + (F - E) + (F - D) + (F - A)
我很清楚这不是一个好的解决方案，因为这些项相互抵消，并且一条线上的增加只会在另一条线上减少相同的数量，因此目标永远不会偏向于在变量之间均匀分布最大化。
我还尝试将每条线与其中间可能范围的距离最小化。对于 line B - A，其范围内的中间值(1,3)是2。这是第一学期的目标：
minimize: |(B - A) - 2| + ...
为了实现绝对值，我将术语替换为U并添加了额外的约束：
minimize: U + ...
with: U <= (B - A - 2)
U <= -(B - A - 2)
这与另一个目标存在相同的问题：差异始终与另一条线差异的变化成正比。我认为如果我可以将差异平方，会起作用，但我无法将其输入到线性求解器中。
是否有一些目标函数可以实现我正在寻找的目标，或者线性求解器不是正确的工具？
如果有帮助，我正在使用 Google OR-Tools。
以下是写出的约束：
1 <= B - A <= 3
0 <= C - B <= 1
1 <= C - A <= 4
9 <= E - B <= 11
7 <= D - C <= 11
0 <= E - D <= 1
3 <= F - E <= 5
3 <= F - D <= 6
15 <= F - A < = 15
请记住，您最大的问题是您不知道它到底是什么，您想要什么。所以我不得不猜测。有时看到一些猜测可以帮助您完善您想要的内容，因此这对您来说还不错，但它确实使您的问题对于本网站的格式更加困难。
首先，我假设弹簧可以建模为有向无环图。也就是说，我可以用指向右侧的箭头替换所有弹簧。永远不会有从右到左的箭头（否则你的弹簧会弯曲成一个圆圈）。
完成此操作后，您可以使用设置逻辑来确定最左侧蓝色条的身份。（我假设只有一个 - 它留作练习以找出如何概括。）然后您可以将此栏固定在合适的位置。所有其他条形都将相对于它定位。这个约束看起来像：
S[leftmost] = 0
现在，我们需要一些约束。
每条边i都有一个源点和终点（因为边是有向的）。调用源点S的位置和终点的位置E。此外，边具有最小长度l和最大长度L。由于我们固定了最左侧 bluebar 的位置，因此连接到它的弹簧定义了它们的端点落入的间隔。这些端点是其他弹簧的源点，等等。因此，每条边在其端点的位置上定义了两个约束。
S[i]+l[i] <= E[i]
E[i] <= S+L[i]
顺便说一句，请注意我们现在可以制定一个简单的线性程序：
min 1
s.t. S[leftmost] = 0
S[i]+l[i] <= E[i]
E[i] <= S+L[i]
如果这个程序可以解决，那么你的问题就有一个可行的解决方案。也就是说，条形长度不会对 bluebars 应该在哪里产生相互不一致的描述。
现在，我们想要“均匀地最大化灰线的大小”，无论这意味着什么。
最小化与平均长度的偏差
这是一个想法。程序为每个条形选择的长度由 给出E[i]-S[i]。让我们指定这个长度应该“接近” bar 的平均长度(L[i]+l[i])/2。因此，我们希望为每个柱最小化的目标数量是：
(E[i]-S[i])-(L[i]+l[i])/2
有问题的是，这个值可以是正值也可以是负值，这取决于 是否为(E[i]-S[i])>(L[i]+l[i])/2。这不好，因为我们希望最小化与 的偏差(L[i]+l[i])/2，该值应始终为正。
为了应对，让我们对值进行平方，然后取平方根，这给出：
sqrt(((E[i]-S[i])-(L[i]+l[i])/2)^2)
这似乎无法解决，但请留在我身边。
请注意，上述与取单元素向量的 L2 范数相同，因此我们可以将其重写为：
|(E[i]-S[i])-(L[i]+l[i])/2|_2
我们现在可以对每个条形的偏差求和：
|(E[0]-S[0])-(L[0]+l[0])/2|_2 + |(E[1]-S[1])-(L[1]+l[1])/2|_2 + ...
这给了我们以下优化问题：
min |(E[0]-S[0])-(L[0]+l[0])/2|_2 + |(E[1]-S[1])-(L[1]+l[1])/2|_2 + ...
s.t. S[leftmost] = 0
S[i]+l[i] <= E[i]
E[i] <= S+L[i]
这个问题在上述形式中并不容易解决，但我们可以通过引入一个变量来执行简单的操作 t
min t[0] + t[1] + ...
s.t. S[leftmost] = 0
S[i]+l[i] <= E[i]
E[i] <= S+L[i]
|(E[i]-S[i])-(L[i]+l[i])/2|_2<=t[i]
这个问题和上一个问题完全一样。那么我们得到了什么？
优化是将问题转化为标准形式的游戏。一旦我们有一个标准形式的问题，我们就可以站在巨人的肩膀上，使用强大的工具来解决我们的问题。
前面的操作已经把问题变成了二阶锥问题（SOCP）。一旦采用这种形式，它几乎可以直接解决。
这样做的代码如下所示：
#!/usr/bin/env python3
import cvxpy as cp
import networkx as nx
import matplotlib.pyplot as plt
def FindTerminalPoints(springs):
starts = set([x[0] for x in springs.edges()])
ends = set([x[1] for x in springs.edges()])
return list(starts-ends), list(ends-starts)
springs = nx.DiGraph()
springs.add_edge('a', 'b', minlen= 1, maxlen= 3)
springs.add_edge('a', 'c', minlen= 1, maxlen= 4)
springs.add_edge('a', 'f', minlen=15, maxlen=15)
springs.add_edge('b', 'c', minlen= 0, maxlen= 1)
springs.add_edge('b', 'e', minlen= 9, maxlen=11)
springs.add_edge('c', 'd', minlen= 7, maxlen=11)
springs.add_edge('d', 'e', minlen= 0, maxlen= 1)
springs.add_edge('d', 'f', minlen= 3, maxlen= 6)
springs.add_edge('e', 'f', minlen= 3, maxlen= 5)
if not nx.is_directed_acyclic_graph(springs):
raise Exception("Springs must be a directed acyclic graph!")
starts, ends = FindTerminalPoints(springs)
if len(starts)!=1:
raise Exception("One unique start is needed!")
if len(ends)!=1:
raise Exception("One unique end is needed!")
start = starts[0]
end = ends[0]
#At this point we have what is essentially a directed acyclic graph beginning at
#`start` and ending at `end`
#Generate a variable for the position of each blue bar
bluevars = {n: cp.Variable(name=n) for n in springs.nodes()}
dvars = {e: cp.Variable() for e in springs.edges()}
#Anchor the leftmost blue bar to prevent pathological solutions
cons = [bluevars[start]==0]
for s,e in springs.edges():
print("Loading edge {0}-{1}".format(s,e))
sv = bluevars[s]
ev = bluevars[e]
edge = springs[s][e]
cons += [sv+edge['minlen']<=ev]
cons += [ev<=sv+edge['maxlen']]
cons += [cp.norm((ev-sv)-(edge['maxlen']-edge['minlen'])/2,2)<=dvars[(s,e)]]
obj = cp.Minimize(cp.sum(list(dvars.values())))
prob = cp.Problem(obj,cons)
val = prob.solve()
fig, ax = plt.subplots()
for var, val in bluevars.items():
print("{:10} = {:10}".format(var,val.value))
plt.plot([val.value,val.value],[0,3])
plt.show()
结果如下所示：
如果您想“手动调整”蓝条，您可以通过添加权重来修改我们构建的优化问题w[i]。
min w[0]*t[0] + w[1]*t[1] + ...
s.t. S[leftmost] = 0
S[i]+l[i] <= E[i]
E[i] <= S+L[i]
|(E[i]-S[i])-(L[i]+l[i])/2|_2<=t[i]
越大w[i]，所讨论的弹簧接近其平均长度就越重要。
最小化有序蓝条之间的平方距离，受约束
使用与上述相同的策略，我们可以假设某种已知顺序来最小化蓝条之间的平方距离。这将导致：
min t[0] + t[1] + ...
s.t. S[leftmost] = 0
S[i]+l[i] <= E[i]
E[i] <= S+L[i]
|(S[i]-S[i+1])/2|_2<=t[i]
在下面的代码中，我首先找到蓝条的可行位置，然后假设这些映射到一个理想的顺序。用更准确的信息替换这种启发式方法将是一个好主意。
#!/usr/bin/env python3
import cvxpy as cp
import networkx as nx
import matplotlib.pyplot as plt
def FindTerminalPoints(springs):
starts = set([x[0] for x in springs.edges()])
ends = set([x[1] for x in springs.edges()])
return list(starts-ends), list(ends-starts)
springs = nx.DiGraph()
springs.add_edge('a', 'b', minlen= 1, maxlen= 3)
springs.add_edge('a', 'c', minlen= 1, maxlen= 4)
springs.add_edge('a', 'f', minlen=15, maxlen=15)
springs.add_edge('b', 'c', minlen= 0, maxlen= 1)
springs.add_edge('b', 'e', minlen= 9, maxlen=11)
springs.add_edge('c', 'd', minlen= 7, maxlen=11)
springs.add_edge('d', 'e', minlen= 0, maxlen= 1)
springs.add_edge('d', 'f', minlen= 3, maxlen= 6)
springs.add_edge('e', 'f', minlen= 3, maxlen= 5)
if not nx.is_directed_acyclic_graph(springs):
raise Exception("Springs must be a directed acyclic graph!")
starts, ends = FindTerminalPoints(springs)
if len(starts)!=1:
raise Exception("One unique start is needed!")
if len(ends)!=1:
raise Exception("One unique end is needed!")
start = starts[0]
end = ends[0]
#At this point we have what is essentially a directed acyclic graph beginning at
#`start` and ending at `end`
#Generate a variable for the position of each blue bar
bluevars = {n: cp.Variable(name=n) for n in springs.nodes()}
#Anchor the leftmost blue bar to prevent pathological solutions
cons = [bluevars[start]==0]
#Constraint each blue bar to its range
for s,e in springs.edges():
print("Loading edge {0}-{1}".format(s,e))
sv = bluevars[s]
ev = bluevars[e]
edge = springs[s][e]
cons += [sv+edge['minlen']<=ev]
cons += [ev<=sv+edge['maxlen']]
#Find feasible locations for the blue bars. This is a heuristic for getting a
#sorted order for the bars
obj = cp.Minimize(1)
prob = cp.Problem(obj,cons)
prob.solve()
#Now that we have a sorted order, we modify the objective to minimize the
#squared distance between the ordered bars
bar_locs = list(bluevars.values())
bar_locs.sort(key=lambda x: x.value)
dvars = [cp.Variable() for n in range(len(springs.nodes())-1)]
for i in range(len(bar_locs)-1):
cons += [cp.norm(bar_locs[i]-bar_locs[i+1],2)<=dvars[i]]
obj = cp.Minimize(cp.sum(dvars))
prob = cp.Problem(obj,cons)
val = prob.solve()
fig, ax = plt.subplots()
for var, val in bluevars.items():
print("{:10} = {:10}".format(var,val.value))
plt.plot([val.value,val.value],[0,3])
plt.show()
看起来像这样：
最小化所有蓝条之间的平方距离，受约束
我们还可以尝试最小化蓝色条之间的所有成对平方距离。在我看来，这似乎给出了最好的结果。
min t[i,j] + ... for all i,j
s.t. S[leftmost] = 0
S[i]+l[i] <= E[i] for all i
E[i] <= S+L[i] for all i
|(S[i]-S[j])/2|_2 <= t[i,j] for all i,j
那看起来像这样：
#!/usr/bin/env python3
import cvxpy as cp
import networkx as nx
import matplotlib.pyplot as plt
import itertools
def FindTerminalPoints(springs):
starts = set([x[0] for x in springs.edges()])
ends = set([x[1] for x in springs.edges()])
return list(starts-ends), list(ends-starts)
springs = nx.DiGraph()
springs.add_edge('a', 'b', minlen= 1, maxlen= 3)
springs.add_edge('a', 'c', minlen= 1, maxlen= 4)
springs.add_edge('a', 'f', minlen=15, maxlen=15)
springs.add_edge('b', 'c', minlen= 0, maxlen= 1)
springs.add_edge('b', 'e', minlen= 9, maxlen=11)
springs.add_edge('c', 'd', minlen= 7, maxlen=11)
springs.add_edge('d', 'e', minlen= 0, maxlen= 1)
springs.add_edge('d', 'f', minlen= 3, maxlen= 6)
springs.add_edge('e', 'f', minlen= 3, maxlen= 5)
if not nx.is_directed_acyclic_graph(springs):
raise Exception("Springs must be a directed acyclic graph!")
starts, ends = FindTerminalPoints(springs)
if len(starts)!=1:
raise Exception("One unique start is needed!")
if len(ends)!=1:
raise Exception("One unique end is needed!")
start = starts[0]
end = ends[0]
#At this point we have what is essentially a directed acyclic graph beginning at
#`start` and ending at `end`
#Generate a variable for the position of each blue bar
bluevars = {n: cp.Variable(name=n) for n in springs.nodes()}
#Anchor the leftmost blue bar to prevent pathological solutions
cons = [bluevars[start]==0]
#Constraint each blue bar to its range
for s,e in springs.edges():
print("Loading edge {0}-{1}".format(s,e))
sv = bluevars[s]
ev = bluevars[e]
edge = springs[s][e]
cons += [sv+edge['minlen']<=ev]
cons += [ev<=sv+edge['maxlen']]
dist_combos = list(itertools.combinations(springs.nodes(), 2))
dvars = {(na,nb):cp.Variable() for na,nb in dist_combos}
distcons = []
for na,nb in dist_combos:
distcons += [cp.norm(bluevars[na]-bluevars[nb],2)<=dvars[(na,nb)]]
cons += distcons
#Find feasible locations for the blue bars. This is a heuristic for getting a
#sorted order for the bars
obj = cp.Minimize(cp.sum(list(dvars.values())))
prob = cp.Problem(obj,cons)
val = prob.solve()
fig, ax = plt.subplots()
for var, val in bluevars.items():
print("{:10} = {:10}".format(var,val.value))
plt.plot([val.value,val.value],[0,3])
plt.show()
看起来像这样：
