标签: linear-programming

我有一些不等式{x,y},满足以下等式:

x>=0
y>=0
f(x,y)=x^2+y^2>=100
g(x,y)=x^2+y^2<=200

需要注意的是x和y必须是整数.

在图形上它可以表示如下,蓝色区域是满足上述不等式的区域:

现在的问题是,Matlab中是否有任何函数可以找到每个可接受的对{x,y}？如果有算法来做这种事情,我也很高兴听到它.

当然,我们总能使用的一种方法是强力方法,我们测试每种可能的组合,{x,y}以查看是否满足不等式.但这是最后的手段,因为它耗费时间.我正在寻找一个聪明的算法来做到这一点,或者在最好的情况下,我可以直接使用现有的库.

这x^2+y^2>=100 and x^2+y^2<=200只是例子; 在现实中f,g可以是任何程度的任何多项式函数.

编辑:C#代码也受到欢迎.

我正在使用Gurobi和java来解决ILP问题.我设置了所有,然后启动程序.但是Gurobi甚至没有尝试解决我的问题并且给我一个空解决方案,所有变量都设置为0.

在放松步骤中,Gurobi显示该函数的最小值为-246.这与下一步相反,gurobi表明最优解是0.

Gurobi的产量是:

Optimize a model with 8189 rows, 3970 columns and 15011 nonzeros
Variable types: 0 continuous, 3970 integer (0 binary)
0 0 0 1.0E100 -1.0E100 0 0
**** New solution at node 0, obj 0.0
Found heuristic solution: objective 0.0000000

Root relaxation: objective -2.465000e+02, 4288 iterations, 0.08 seconds

     Nodes    |    Current Node    |     Objective Bounds      |     Work
  Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time


 0     0 -246.50000    0  315    0.00000 -246.50000     - …

我有一组I = {P1,P2,...,Pm}和n个有限的I子集,由R1,R2,...,Rn表示如下:

R1 = {P1,P2}

R2 = {P2,P4}

R3 = {P2,P3,P4}

R4 = {P1,P2,P4}

....

其中Pi表示整数.

对于每个Ri,我想计算其所有元素的乘积.我的目标是通过在Ri(i = 1,2,...,n)之间共享一些公共部分来尽可能少地使用复用和除法.

例如,如果我可以先计算P2*P4,那么这个结果可用于计算R3和R4的所有元素的乘积.

请注意,也允许分割.例如,我可以首先计算A = P1*P2*P3*P4,然后使用A/P1计算R3的所有元素的乘积,并使用A/P3作为R4.

如果我想使用最小乘法和除法来计算I的每个子集的所有乘积,它是否是一个集合覆盖问题？NP完成？顺便说一句,你能给出一个整数线性程序公式来描述它就像这里一样.

任何建议将受到高度赞赏!

社区编辑:增加假设:

• 允许划分,与乘法相同的成本
• 给定集合中没有重复的元素.例如R5 = {P1, P1, P1, P2}是不允许的

假设我想构建一个函数,该函数可以在一周内正确安排三个总线驱动程序,并具有以下约束条件:

• 每位驾驶员每周驾驶的次数不得超过五次
• 每天必须有两名司机开车
• 他们每周休息一天(不会与其他司机的休息日发生冲突)

会用什么样的算法来解决这样的问题？

我浏览了几个网站,发现了这些:

1) Backtracking algorithm (brute force)
2) Genetic algorithm
3) Constraint programming

坦率地说,这些对我来说都是"文化冲击",因为我过去从未学过任何类型的线性编程.我想知道两件事:

1)哪种算法最适合上述情况？

2)解决这个问题最简单的算法是什么？

3)请建议我可以研究的任何其他算法来解决上述问题.

我正在尝试做一些逻辑应该可行的事情.但是,我不确定如何在线性编程领域内做到这一点.我使用的是ZMPL/SCIP,但这对大多数人来说应该是可读的.

set I := {1,2,3,4,5};
param u[I] := <1> 10, <2> 20, <3> 30, <4> 40, <5> 50;

var a;
var b;

subto bval:
  b == 2;

subto works:
  a == u[2];

#subto does_not_work:
#  a == u[b];

我试图确保变量a等于索引b中的值u.因此,例如,我确保b == 2然后我尝试设置约束a == u[b],但这不起作用.它抱怨我试图用变量索引.a == u[2]然而,我能够做到,这a等于20.

有没有办法轻松访问u变量指定的索引？感谢您的帮助/指导.

编辑:我认为共识是不可能的,因为它不再成为LP.在这种情况下,任何人都可以想到另一种方式来写这个,以便,根据价值b,我可以从集合中获得一个相关的值u？这必须避免直接索引它.

解决方案:根据Ram的反应,我能够尝试一下,发现它绝对是一个可行的线性解决方案.谢谢,拉姆!以下是ZMPL中的示例解决方案代码:

set I := {1,2,3,4,5};
param u[I] := <1> …

我必须找到一些微小的线性编程问题的所有基本解决方案。

这是一个示例（采用lp_solve格式）：

max: x1 + x2;
x1 + x2 <= 1;
x1 <= 0.8;
x2 <= 0.8;

所有2种基本解决方案：

• x1 = 0.2，x2 = 0.8
• x1 = 0.8，x2 = 0.2

当然，有一种寻找替代解决方案的方法，但是我真的更喜欢使用现有的库，而不是精心设计自己的单纯形代码。

我使用Python作为编程语言，希望lp_solve或GLPK的C API中有某种方法可以做到这一点。

谢谢。

有没有办法让lpSolve返回多个解决方案？在下面的情况下,我想要(5,0)和(0,5)两者.

如果lpSolve无法做到这一点,那么是否有任何其他R包将返回整体线性优化程序的所有可能解决方案？

 library("lpSolve")
  A=matrix (c(1, 1), nrow=1, byrow=TRUE)

  b=(5)
  signs='=='
  c_=c(1,1)
  res = lpSolve::lp('max', c_, A, signs, b,  all.int = TRUE)
  res$solution

================================================== =====================

我还想知道为什么lpSolve包提供了所有可能的解决方案,如果所有决策变量都是二进制的.当所有变量都是整数时,为什么不能重复相同的...

我正在尝试解决一个具有超过 45.000 个二进制变量和约 350.000 个约束的大规模线性整数优化问题 (MILP)。

我正在使用Pulp来解决问题，但我无法在合理的时间内找到解决方案。

有什么方法可以大大加快优化过程吗？例如：

• Pulp 可以以某种方式并行化吗？
• 还有其他可以使用的软件包/求解器吗？
• 还有其他建议吗？

我正在一个项目中，我需要根据百分比值数组细分整数值。我的最终数组必须包含整数值，并且数组的总和必须等于初始整数。

下面是一个伪造的例子。我们列出了带有某些“潜力”的汽车，我们需要将此潜力分配给特定的邮政编码。邮政编码分配由一些售罄信息决定。

SELLOUTS_PER_P_CODE规定要分配给每个邮政编码的权重。例如，对于第一个轿厢（car 1），存在很多的重量为p_code_3和少p_code_2，甚至更少用于p_code_1这样的分配应该分别为轿厢1 p_code_1=1，p_code_2=2，p_code_3=4。

贝娄是问题的数学形式。

在这里，我正在使用pyomo来实现此公式，但是不会产生预期的结果。该模型未考虑来自SELLOUTS_PER_P_CODE

from pyomo.environ import *
from pprint import pprint


def distribute(total, weights):
    scale = float(sum(weights.values())) / total
    return {k: v / scale for k, v in weights.items()}


Cars = ["car 1", "car 2", "car 3"]
Locations = ["p_code_1", "p_code_2", "p_code_3"]
POTENTIALS = {"car 1": 7, "car 2": 2, "car 3": 14}
SELLOUTS = {"p_code_1": 0.2, "p_code_2": 0.3, "p_code_3": 0.5} …

我想知道如何使用 or-tools 定义复杂的目标函数（如果可能的话）。

下面的基本示例展示了如何使用 python 中的 Or-tools 解决基本线性问题：

solver = pywraplp.Solver('lp_pricing_problem', pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)

# Define variables with a range from 0 to 1000.
x = solver.NumVar(0, 1000, 'Variable_x')
y = solver.NumVar(0, 1000, 'Variable_y')

# Define some constraints.
solver.Add(x >= 17)
solver.Add(x <= 147)
solver.Add(y >= 61)
solver.Add(y <= 93)

# Minimize 0.5*x + 2*y
objective = solver.Objective()
objective.SetCoefficient(x, 0.5)
objective.SetCoefficient(y, 2)
objective.SetMinimization()

status = solver.Solve()

# Print the solution
if status == solver.OPTIMAL:
    print("x: {}, y: {}".format(x.solution_value(), y.solution_value())) # x: 17.0, …