标签: mixed-integer-programming

我会尽量让我的问题简短明了。如果您需要任何进一步的信息，请告诉我。

我有一个 MIP，用 Python 包 PuLP 实现。（大约 100 个变量和约束）问题的数学表述来自一篇研究论文。本文还包括一项数值研究。然而，我的结果与作者的结果不同。

我的问题变量叫做prob

prob = LpProblem("Replenishment_Policy", LpMinimize)

prob.solve() LpStatus我通过退货解决问题Optimal

当我添加一些最佳（论文）结果作为约束时，我得到了稍微更好的客观值。将目标函数限制为稍低的值也是如此。LpStatus 保持不变Optimal。

original objective value: total = 1704.20
decision variable: stock[1] = 370

adding constraints: prob += stock[1] == 379
new objective value: 1704.09

adding constraints: prob += prob.objective <= 1704
new objective value: 1702.81

我的假设是 PuLP 的求解器近似解。计算速度很快，但显然不太准确。有没有办法可以提高 PuLP 所使用的求解器的精度？我正在寻找类似的内容：prob.solve(accuracy=100%).我查看了文档，但不知道该怎么做。有什么想法可能是什么问题吗？

任何帮助表示赞赏。谢谢。

我有几个关于 APOPT 如何解决 MINLP 的问题。

• APOPT 使用什么非线性规划方法（内部点、信赖域等）？
• APOPT 如何处理混合整数（B&B、外近似、广义弯曲分解等）？

我有一个程序，我想最小化两个变量的绝对差（绝对误差函数）。说：

e_abs(x, y) = |Ax - By|; where e_abs(x, y) is my objective function that I want to minimize.

该函数受到以下约束：

x and y are integers;
x >= 0; y >= 0
x + y = C, where C is an arbitrary constant (also C >= 0)

我正在使用 mip 库（https://www.python-mip.com/），我在其中定义了目标函数和约束。

问题是 mip 没有“abs”方法。因此，我必须通过将主要问题分为两个优化子问题来克服这个问题：

e(x, y) = Ax - By

Porblem 1: minimize e(x, y); subject to e(x, y) >= 0
Porblem 2: maximize e(x, y); subject to e(x, y) …

我当时正在开发一个示例 MIP 程序，该程序选择了男女混合运动队的首发阵容，并发现了一个在 Google OR 工具中得出非最佳结果的小示例。

基础知识：从 n>5 名玩家组成的团队中选择 5 名首发。至少两名首发必须是女性。被划伤的玩家无法启动。目标函数是初学者技能水平的简单总和。代码是：

import pandas as pd
from ortools.linear_solver import pywraplp

# %% Read the data from an external file
pname   = ["Tom", "Joe", "Bill", "Mike", "Frank", "Mary", "Sue", "JoAnn"]
skill   = [ 11.0,  13.0,   11.0,   12.0,    14.0,   10.0,  10.0,     7.0]
female  = [    0,     0,      0,      0,       0,      1,     1,       1]
scratch = [    0,     0,      0,      0,       1,      0,     0,       0]

# %% Create the mip solver with the SCIP …

我想在线性程序（或必要时使用 MIP）中编写一个非重叠约束（即 2 个矩形不重叠）。我知道如何在约束编程中做到这一点：

对于对象 i 和 j：

x[i]+dx[i]<=x[j] 或 y[i]+dy[i]<=y[j] 或 x[j]+dx[j]<=x[i] 或 y[ j]+dy[j]<=y[i] 其中 x 和 y 是包含对象坐标的数组，dx 和 dy 是对象的维度。

知道在 LP/MIP 中执行此操作的最佳方法吗？谢谢！

我不知道如何设置 MIP 间隙阈值，以便当原始解和对偶解之间的相对差异在某个值内时求解器将终止。我正在使用 PySCIPOpt 与 SCIP 交互。

我确信有一个简单的方法（例如，如果我使用 Gurobi 的 python 接口m.Params.MIPGap = x，它m就是模型实例在哪里）。

任何帮助是极大的赞赏！

我最近一直在使用 Python 进行线性编程，并且我使用 PuLP 创建了我的第一个优化算法。

我正在处理生产过程的调度问题。目标是通过为一天中的每个小时创建一个理想的生产计划，并为一年中的所有天创建这个计划，从而最大限度地降低每天的生产成本。

我遇到的问题是算法的执行需要很长时间（几个小时）并且经常卡住。另外，我感觉随着时间的推移它会变慢。

我希望得到有关如何提高代码性能的建议。

我对这个问题的处理方法：

• 定义我的最小化问题以创建一整天的最佳时间表。
• 循环我的代码以在一年中的所有 365 天运行此优化。
• 在每个循环结束时，我采用当天优化的生产计划并将其附加到数据帧，因此最后我有一个包含一年中所有日子的生产计划的数据帧。

我正在处理 3 个生产资产（'a'、'l' 和 'o'），每个资产都有几种生产模式。我将每个资产模式组合定义为一个“选项”，总共产生 14 个选项。每个选项每小时都在变化，并且有一个整数值（生产量）和一个二进制值（开/关），产生大约 14 x 2 x 24 = 672 个变量。该问题包含大约 1250 个约束。

我的代码有 200 多行，所以我有点犹豫要不要在这里分享所有内容，但我将在下面分享最重要的部分。

定义供应选项：

def set_supplyoptions():
cols = ['option', 'min_capacity', 'max_capacity']
options_list = [{'option':'o', 'min_capacity': 0, 'max_capacity':146},
                {'option':'l30', 'min_capacity': 0, 'max_capacity':30},
                {'option':'l50', 'min_capacity': 31, 'max_capacity':50},
                {'option':'l90', 'min_capacity': 51, 'max_capacity':90},
                {'option':'l150', 'min_capacity': 91, 'max_capacity':150},
                {'option':'l230', 'min_capacity': 151, 'max_capacity':230},
                {'option':'a15', 'min_capacity': 0, 'max_capacity':15},
                {'option':'a30', 'min_capacity': 0, 'max_capacity':30},
                {'option':'a45', 'min_capacity': 0, 'max_capacity':45}, …

It is known that exact mathematical strategies such MILP are not efficient for large instances of the flexible job shop problem.

It is common to see in the literature MILP formulations for the FJS problem. I read that it is interesting to use the MILP model for experiments involving non-exact methods as metaheuristics (GA, FA, TS, etc) since it provides lower and upper bounds.

我还读到，当找到可行的解决方案比最优解决方案更重要时，应该选择CP。这是真实的说法吗？

我想使用 SCIP 解决具有 267 个变量 [1] 的混合整数二次规划问题。

CPLEX 可以在大约 30 秒内解决该问题，并且在不到一秒的时间内就已经找到了非常接近最优解的解决方案 [2, 3]。

不幸的是，SCIP 确实在解决这个问题上遇到了困难，即使运行了 20 多分钟也无法找到接近最佳的解决方案 [4]。

为什么是这样？CPLEX 在 MIQP 方面真的比SCIP 好得多吗？我是否没有正确配置 SCIP？如何使用 SCIP 解决这个问题？

在我看来，SCIP 找到的解决方案与松弛的解决方案相去甚远。我的印象是 SCIP 首先解决松弛问题，然后尝试在此基础上找到整数解。这不正确吗？如果是的话，为什么解决方案还那么遥远？

• [1] https://gist.github.com/julmb/e425ef372b110825d49fee8649d88a49#file-267p-lp
• [2] https://gist.github.com/julmb/e425ef372b110825d49fee8649d88a49#file-cplex-log
• [3] https://gist.github.com/julmb/e425ef372b110825d49fee8649d88a49#file-cplex-sol
• [4] https://gist.github.com/julmb/e425ef372b110825d49fee8649d88a49#file-scip-log

我需要从这个 if-else 语句构建一个 MILP（混合整数线性规划）约束：其中 beta 是一个常量。

if (a > b) then c = beta else c = 0

如何构建 MILP 约束的语句。有没有什么技术可以解决这个问题。谢谢。

前段时间我正在写一篇与 OR 相关的文章以供发表。在这篇文章中，展示了使用 MiniZinc 解决某个优化问题的 MILP 模型。我在 10 个实例中以最佳方式解析了 10 个实例。

顾问对其进行审查并提到以下 2 条评论：

1. 您如何将 MiniZinc 与其他最新一代 MILP 求解器（如 CPLEX 或 Gurobi）在性能方面进行比较？

我一直在使用 MiniZinc，它对我很有效。我如何展示 MiniZinc 的多功能性？是否有参考书目或证明其合理性的方法？

2. 由于 MiniZinc 不是最著名的 MILP 求解器之一，因此您应该避免在摘要中提及它的名称。

出于什么原因，您不建议在摘要中提及它？

使用 MiniZinc 的有效理由是什么？

我是优化问题的新手，正在研究一个简单的最大化问题，我可以在 Excel 中非常简单地解决这个问题。但是，我需要在 Python 中扩展它并需要一些帮助。

我有一份不同食物的菜单，我需要最大限度地提高我的能量输出。例子：

鉴于以下限制，我需要最大化能量（e）：

1. 每个 Macros(m) 只能消耗 1 个食物项目 (i)。所以我需要一个指示变量 (0/1) 来从 m - 蛋白质、脂肪和碳水化合物中的每一个中只选择 1 个。
2. 卡路里总数 (c) 不应超过一个恒定值假设每个项目有 1 份（对此没有限制）

问题表述：

变量： X (m,i) ? 二元变量 = {1 ，如果宏 m 和项目 i 被选择，0 否则}

最大化 …