标签: integer-programming

我注意到 R 并没有使用我所有的 CPU，我想极大地增加它（向上到 100%）。我不希望它只是并行化几个函数；我希望 R 使用更多的 CPU 资源。我正在尝试使用 lp() 函数运行纯 IP 集打包程序。目前，我运行 Windows，并且我的计算机上有 4 个内核。

我曾尝试用雪、doParallel 和 foreach 进行试验（虽然我不知道我真的在用它们做什么）。

在我的代码中，我有这个......

library(foreach)
library(doParallel)
library(snowfall)

cl <- makeCluster(4)
registerDoParallel(cl)

sfInit(parallel = TRUE, cpus = 4)


#code that is taking a while to run but does not involve simulations/iterations

lp (......, all.int = TRUE)

sfStop()

R 卡住并运行 lp() 很长时间。我的 CPU 大约是 25%，但我怎样才能增加它？

尝试在 Gurobi/Python 中添加以下约束：

代码

N_SERVERS = 5                             #number of servers
C_SERVER = [1]*N_SERVERS
N_NODES = 3                               #number of nodes
C_NODES = [2]*N_NODES    

#create model
m = Model("mip1")

#declare variables
x = m.addVars(len(C_SERVER), vtype=GRB.BINARY, name = "x")
y = m.addVars(len(C_NODES), vtype=GRB.BINARY, name = "y")
m.update()

m.addConstrs(quicksum(x[i]*C_SERVER[i] for i in range(len(x))) + quicksum(y[j]*C_NODES[j] for j in range(len(y))) == quicksum(C_SERVER)

我收到以下错误：KeyError: '缺少约束索引'。是什么原因？

那是什么

我正在尝试为锦标赛制作一套最佳的方括号(最佳约束条件).

问题

我不知道如何处理这个问题. 该论文是相当高的水平,但讨论解决与约束编程集分割问题的可能性.它还指出大多数集合分区问题都是通过整数编程解决的.我主要是在寻找一个模仿的例子.问题类似于这个问题.我见过的大多数约束示例都定义了特定的分区总数.是否可以建模一个系统,其中分区将由约束和参与者集动态确定？我会链接示例,但由于我的声誉,我仅限于2.

一个更具体的例子

已知值

• 参加人数为N.
• 每个参与者具有与他们相关联的权重W.

约束

• 支架(组)由2,3,4,6,7或8个参与者组成.
• 每个参与者只在一个支架中.
• 最低加权参与者与括号中最高加权参与者之间的差异不得超过15%.
• 倾向于在所有其他支架尺寸上创建尺寸为8和4的支架.

例如,说有8个参与者.

{{1,W = 100},{2,W = 103},{3,W = 105},{4,W = 106},{5,W = 110},{6,W = 114},{ 7,W = 120},{8,W = 125}}

一种可能的解决方案是:{1,2,3},{4,5},{6,7,8}

更优化的解决方案是:{1,2,3,4},{5,6,7,8},因为这有利于先前解决方案中的4,8个大小的集合.

是否可以将集合划分为动态数量的子集？

感谢你的宝贵时间!

我正在使用 CVXOPT 来解决一个非常简单的问题：

min -7890424934354.171875*x1 -7890424934354.274414*x2 -7890424934354.246093*x3
s.t: 
  x1 + x2 + x3 = 1
  x1,x2,x3 are binary

我们可以看到最优解显然应该是：

x1 =0; x2 = 1; x3 = 0

但是我没有从 CVXOPT 使用 ILP 得到正确答案（我知道上面的问题太简单了，无法使用 ILP，但我只是好奇）。关于 CVXOPT 的 ILP 的详细描述在这里。

我的程序是这样的：

from cvxopt.glpk import ilp
from cvxopt import matrix
c = matrix([-7890424934354.171875,-7890424934354.274414,-7890424934354.246093],tc='d')
G = matrix(0.0, (1,3)) #since I do not have a constraint like G*x <= h, I make them zeros here
h = matrix(0.0, (1,1))
A = matrix([1,1,1],tc='d')
b = …

我正在使用cvxpy内python来解决特定类型的分配问题。我想以最小化成本的方式将 M 人分配到 N 个组，对组有以下限制：

1. 组的成员不能超过 J 个
2. 如果一个组被填充，它必须至少有 K 个成员，否则一个组可以有零个成员。

当然，K <= J。我可以忽略上面的#2 来解决问题。在下面的例子中，M = 6，N = 3 和 J = 3。理想情况下，我想设置 K = 2。我生成的偏好使得每个人都喜欢第 1 组（成本函数中的第 1 列），然后大多数人更喜欢第 2 组，但一个人更喜欢第 3 组而不是第 2 组：

import numpy as np import cvxpy as cp

preference = np.array([[1,2,3],
                       [1,2,3],
                       [1,2,3],
                       [1,2,3],
                       [1,2,3],
                       [1,3,2]])

groupmax = np.array([3,3,3])

selection = cp.Variable(shape=preference.shape,boolean=True)

group_constraint_1 = cp.sum(selection,axis=0) <= groupmax

assignment_constraint = cp.sum(selection,axis=1) == 1

cost = cp.sum(cp.multiply(preference,selection))

constraints = [group_constraint_1,assignment_constraint]

assign_prob = …

给定实线上的一组区间和一些参数 d > 0。找到相邻点之间的间隙小于或等于 d 的点序列，使得包含任何点的区间数最小化。为了防止琐碎的解决方案，我们要求序列中的第一个点在第一个间隔之前，而最后一个点在最后一个间隔之后。间隔可以被认为是右开的。

这个问题有名字吗？甚至可能是算法和复杂性界限？

一些背景： 这是由拓扑数据分析中的一个问题引发的，但它似乎很笼统，以至于它可能对其他主题很有趣，例如任务调度（假设工厂每年必须至少关闭一次并希望最小化维护造成的任务数量......）我们正在考虑整数规划和最小削减，但 d 参数不太合适。我们还在 n^2 和 n*logn 时间内实现了近似贪婪解决方案，但它们可能会遇到非常糟糕的局部最优解。

给我看一张图片

我用线画间隔。下图显示了 7 个区间。d 是这样的，您必须至少每四个字符剪切一次。在图表的底部，您会看到图表的两个解决方案（用 x 和 y 标记）。x 穿过顶部的四个区间，而 y 穿过底部的三个区间。y 是最优的。

 ——— ———
 ——— ———
   ———
   ———
   ———
x x   x x
y   y   y

给我看一些代码： 我们应该如何fun在下面的代码片段中定义？

 ——— ———
 ——— ———
   ———
   ———
   ———
x x   x x
y   y   y

在这个小例子中，最优解将削减第一个区间，但不会削减第二个和第三个区间。显然，该算法也应该适用于更复杂的例子。

更严格的测试如下：给定 [0, 100] 上间隔开始时间的均匀分布和 [0, d] 上的长度均匀分布，可以通过规则网格 [0, d, 2d] 计算预期的切割次数, 3d,..] 略低于 0.5*n。最佳解决方案应该更好：

intervals …

我正在尝试找出如何从 中获取可能解决方案的完整列表ortools.sat.python.cp_model。我知道我可以打印它们，如下例所示，但我不清楚如何获取这些值，例如作为嵌套列表或字典列表。我尝试通过修改 并将解决方案附加到列表属性来编写自己的回调类VarArraySolutionPrinter，但由于某种原因，这始终导致 python 内核崩溃。无论如何，必须有更直接的方法。我不认为解析打印输出是一个选项。

from ortools.sat.python import cp_model

model = cp_model.CpModel()

x00 = model.NewBoolVar('x00')
x01 = model.NewBoolVar('x01')
x02 = model.NewBoolVar('x02')

model.AddBoolOr([x00, x01, x02.Not()])
model.AddBoolOr([x00.Not(), x02.Not()])

# Create a solver and solve.
solver = cp_model.CpSolver()
solution_printer = cp_model.VarArraySolutionPrinter([x00, x01, x02])
solver.SearchForAllSolutions(model, solution_printer)

## Prints:
Solution 0, time = 0.00 s
  x00 = 0   x01 = 1   x02 = 0 
Solution 1, time = 0.01 s
  x00 = 0   x01 = 0   x02 = 0 
Solution 2, …

我在 Python 2.7.8、Windows 32 位上运行 PuLP 编程库。我使用 GLPK 作为混合整数线性规划问题的求解器。求解器收敛到大约。1% 的最优解很快，但是计算精确最优解的时间很长。有没有办法使用 PuLP 为 GLPK 求解器指定百分比容差？我搜索了https://pythonhosted.org/PuLP/solvers.html但它没有为 GLPK 求解器提供任何答案。

我想求解具有以下目标函数的混合整数线性规划：

J = 最大化 (f1(x) + f2(x)) 受约束：成本(x) <= 阈值

其中 x 是选定变量的集合，f1 和 f2 是两个评分函数，cost 是成本函数。

f2 是基于所选变量之间相似性的函数。我不知道如何在纸浆中制定这个功能。

这是我的最小工作示例，其中函数 f2 是两种成分之间的相似度，我想添加similarity[i][j]到目标函数 ifj已经在选定的变量中，但不知道该怎么做。

import numpy as np
import pulp
threshold = 200
model = pulp.LpProblem('selection', pulp.LpMaximize)
similarity = np.array([[1., 0.08333333, 0.1, 0., 0., 0.0625],
                       [0.08333333, 1., 0.33333333,
                           0., 0.11111111, 0.07692308],
                       [0.1, 0.33333333, 1., 0.2, 0., 0.09090909],
                       [0., 0., 0.2, 1., 0., 0.],
                       [0., 0.11111111, 0., 0., 1., 0.27272727],
                       [0.0625, 0.07692308, 0.09090909, 0., 0.27272727, 1.]])
ingredients = …

我有一个很大的MIP问题，我使用GLPK中的GLPSOL来解决它。然而，求解LP松弛问题需要多次迭代，并且每次迭代的obj和infeas值都是相同的。我认为它已经找到了最优解，但它不会停止，并且持续运行了好几个小时。每个大规模 MIP/LP 问题都会发生这种情况吗？遇到这样的情况我该如何处理？有人可以给我任何关于这个的建议吗？谢谢！