algorithm - 线性规划:我可以制定一个目标来一次最大化多个变量吗？

Question

假设我有一些变量和约束，如下系统所示：

灰线可以拉伸和收缩一定量，由其上的范围给定蓝线只是端点，显示了灰线是如何相互作用的。
我的目标是：我想用线性编程来均匀地最大化灰度线的大小，就像图片中的一样。你可以想象那些灰色的线条，上面有弹簧，全都向外推。一个糟糕的解决方案是将所有的蓝线尽可能地推到一边。请注意，在这个描述中有一点回旋余地，而且有多种解决方案是可能的——我所需要的只是使它们合理地均匀，而不是让一个值最大化，从而挤压其他所有值。
我尝试的目标函数简单地使线的大小之和最大化：

maximize: (B - A) + (C - B) + (C - A) + (D - C) + (E - B) + (E - D) + (F - E) + (F - D) + (F - A) 

对我来说，这显然不是一个好的解决方案，因为术语被抵消了，一条线上的增加正好减少了另一条线的数量，因此目标永远不会被加权到均匀地分配变量之间的最大化。
我也试着把每条线与中间可能的距离减到最小对于线 B - A，其 (1,3)范围内的中间值为 2。第一学期的目标是：

minimize: |(B - A) - 2| + ...

为了实现绝对值，我将术语替换为 U，并添加了其他约束：

minimize: U + ...
with: U <= (B - A - 2)
      U <= -(B - A - 2)

这与另一个目标有同样的问题：差异总是与另一条线的差异的变化成正比我想如果我能把差平方就行了，但我不能把它输入到线性解算器中。
是否有一些目标函数可以实现我所追求的目标，或者线性解算器并不是这个目标的正确工具？
如果有帮助的话，我正在使用谷歌或工具。
以下是列出的限制条件：

 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

Answer 1

记住，你最大的问题是你不知道你到底想要什么所以我不得不猜测。有时看到一些猜测会帮助你完善你想要的内容，所以这对你来说并不算太糟，但它确实会使你的问题对于这个网站的格式来说更加困难。
首先，我假设弹簧可以建模为有向无环图也就是说，我可以用指向右边的箭头替换所有弹簧。永远不会有从右向左的箭头（否则弹簧会弯成圆圈）。
完成此操作后，可以使用set logic计算最左边蓝色条的标识。（我假设只有一个——这是一个练习，以找出如何概括）然后你可以锚定这个酒吧在一个合适的位置所有其他杆都将相对定位。此约束看起来像：

S[leftmost] = 0

现在，我们需要一些约束。
每个边都有一个源和端点（因为边是定向的）。调用源点 i的位置和终点 S的位置。此外，边的最小长度为cc，最大长度为cc。由于我们锁定了最左边的蓝斑羚的位置，连接到蓝斑羚上的弹簧定义了它们的端点落下的间隔。这些端点是其他弹簧和C的源点。因此，每条边定义了其端点位置的两个约束。

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]

如果这个程序可以解决，那么你的问题就有一个可行的解决方案也就是说，酒吧的长度不会产生相互矛盾的描述蓝莓应该在哪里。
现在，我们想要“均匀地最大化灰色线的大小”，不管这意味着什么。
最小平均长度偏差
有一个主意。程序为每个条选择的长度由 E给出。让我们指定这个长度应该“接近”条的平均长度 l。因此，我们希望每根钢筋的目标数量最小化为：

(E[i]-S[i])-(L[i]+l[i])/2

问题是，这个值可以是正的，也可以是负的，这取决于是否 L。这是不好的，因为我们想要最小化对 E[i]-S[i]的偏差，这个值应该总是正的。
为了解决这个问题，让我们把这个值平方，然后取平方根，这样可以得到：

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]

这个问题不容易以上述形式解决，但是我们可以通过引入一个变量来执行一个简单的操作 (L[i]+l[i])/2

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]

这个问题和上一个问题完全一样。我们得到了什么？
优化是一个将问题转化为标准形式的游戏。一旦我们有了一个标准形式的问题，我们就可以站在巨人的肩膀上，使用强大的工具来解决我们的问题。
上述操作已将问题转化为 second-order cone problem (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()

结果如下：

如果您想“手动调整”蓝色条，可以通过添加权重 (E[i]-S[i])>(L[i]+l[i])/2来修改我们构建的优化问题。

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]

(L[i]+l[i])/2越大，弹簧接近其平均长度就越重要。
受约束，最小化有序蓝条之间的平方距离
使用与上面相同的策略，我们可以最小化蓝条之间的平方距离，假设某种已知的顺序。这将导致：

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()

看起来是这样的：