标签: linear-programming

当然,这本身并不是一个编程问题......但我想不出一个更好的地方来问这一切.

我正在编写一个应用程序,最终将帮助购物者确定如何在特定网站上实现最大的节省.该网站提供几乎所有产品的两种价格 - 正常价格和折扣价格.任何人都可以享受折扣价,但只有一个折扣商品可以添加到任何给定的订单中.只有这些信息,激励是最小化您的订单siz,而是放置多个订单.另一方面,总运输成本由订单大小(按重量)决定,因此激励是最大化订单大小并仅放置一个订单.

我正在寻找一种模型,以确定最有效的方式来平衡订单,因为一个项目的可用折扣和重量影响订单的运输成本.

我记得回到学校的时候我认为这是一个线性编程问题......但我记得那个课程是多么令人困惑.

任何人都有关于如何计算这个程序的数学技巧？

我一直在编写软件来解决业务问题.我在浏览其中一篇SO帖子时遇到了LIP.我用谷歌搜索,但我无法解释如何使用它来解决业务问题.感谢是否有人可以帮助我理解外行.

有什么好的工具可以解决Linux上的整数程序吗？

我有一个小问题,我想计算以节省时间:D.它是一种子集和问题.我有一个大约20个整数值的列表,我想计算满足一定最小值的最小和的子集.你可以用整数程序来表达这个......就像这样

\sum_{i=1}^{n} w*x -> min

同

\sum_{i=1}^{n} w*x >= c with x \in \{0,1\}

或者还有其他好办法吗？

我需要找到多个点到表格曲线的距离: f(x) = a^(k^(bx))

我的第一个选择是使用它的导数,使用带有导数倒数的形式的线,给出它的坐标Point并与原始曲线相交.最后,我们用简单几何计算点之间的距离.

那是我经常遵循的数学过程.我需要节省时间(因为我正在进行遗传算法程序)所以我需要一种有效的方法来做到这一点.想法？

向量k似乎满足所有约束.这里有什么我想念的吗？谢谢.

import numpy as np
from scipy.optimize import linprog
A_ub=[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, …

这可能是一个更注重数学的问题,但是想在这里问一下,因为它是在CS环境中.我想在另一个(任意)四边形内刻一个矩形,内切四边形可能具有最大的高度和宽度.由于我认为算法类似,我想看看我是否也可以用圆圈做到这一点.

更清楚地听到我的意思是边界四边形作为一个例子.

以下是我试图实现的内容最大化的两个例子:

我做了一些初步的搜索,但没有发现任何确定的东西.似乎某种形式的动态编程可能是解决方案.看来这应该是一个线性优化问题,应该比我发现的更常见,也许我正在寻找错误的术语.

注意: 对于铭刻的正方形,假设我们知道我们正在寻找的目标w/h比(例如4:3).对于四边形,假设边不会交叉并且它将是凹的(如果这简化了计算).

我正在研究调度优化问题，其中我们有一组需要在特定时间范围内完成的任务。

每个任务都有一个时间表，指定可以执行该任务的时间段列表。每个任务的时间表可能因工作日而异。

这是小样本（减少了任务和时间段的数量）：

task_availability_map = {
    "T1" : [0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    "T2" : [0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    "T3" : [0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    "T4" : [0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, …

我有一个带有整数约束的 LP，我想使用 Python 以精确算术求解它。其实我只需要一个可行点。

编辑：“精确算术”这里指的是无界枚举数和分母的有理数。

之前的尝试：

• 查找线性程序的精确解决方案提到了 qsoptex，但是当我尝试导入它时，我得到了ImportError: libqsopt_ex.so.2: cannot open shared object file: No such file or directory，尽管据我所知，我给出了该库的路径。
• SoPlex 可在控制台上运行，但我找不到 Python 界面。
• PySCIPOpt ( https://github.com/SCIP-Interfaces/PySCIPOpt ) 是 SCIP 的 Python 接口，包括 SoPlex，但我不知道如何调用特定的求解器（具有特定的选项）。
• cdd（https://pycddlib.readthedocs.io/en/latest/linprog.html）做了一些事情，称之为 LP，但我不知道他们实际解决的是哪个问题。

速度只是一个中等问题。我的较大实例有大约 500 个带有框约束的变量和 40 个等式，但涉及的数量可能很大。

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

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

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

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

我想知道如何使用 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, …