标签: linear-programming

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

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 = …

我正在尝试使用 CVXOPT 解决线性程序。有 2n 个变量，x_1,...,x_2n。LP的形式为

最小 x_{n+1}+...+x_{2n}

st Ax \leq b

这里，A 和 b 是固定的。从这里看起来很简单。由于我正在优化后半部分变量的总和，因此我创建了一个包含 n 个零和 n 个 1 的向量：c = (0,...,0,1,...,1) 并具有以下代码 (假设 A 和 b 已经计算）：

c = [1]*(2*k + 2)
for i in range(k + 1):
    c[i] = 0
c = matrix(c)
sol=solvers.lp(c,A,b)
print(sol['x'])

此代码直接来自 CVXOPT 文档。但是，我收到一条错误消息：

TypeError: 'c' must be a dense column matrix

我查了一下，但在我看来，调用 matrix() 应该已将 c 转换为适当的类型。有谁知道如何解决这一问题？

我使用 PuLP 库编写了以下 Python 代码，用于使用整数规划公式解决背包问题。我使用字符串生成 LpVariable 命令并添加约束，然后使用 eval 执行它们。有没有办法在不使用 eval 的情况下做到这一点？

from pulp import *

#Knapsack problem

items = input ('Enter the number of items :')

items = int(items)

#print('Enter %d items one by one')

print ('Enter {0} items profit one by one'.format(items))

obj = []
weight = []
knapweight = 0


for i in range(0,items):
    print('Enter {0} item profit : '.format(i+1))
    obj.append(input())

for i in range(0, items):
    print('The profit at {0} is {1}'.format(i, obj[i]))

print ('\nEnter {0} items weights …

我在 Python 上使用 Gurobi，我的代码需要一个 Model.optimize() 函数循环。有没有办法让这个功能静音，这样它就不会输出段落？

谢谢。

当有N个变量和R个约束时，整数线性规划(ILP) 问题的运行时间复杂度是多少？出于编码目的，我使用了 Matlab 的intlinprog函数。任何参考都会有所帮助。