标签: linear-programming

我想看一下IPM的几个实现.最好的语言是C/C++,Java或任何脚本语言,如python,perl.其他人也很好.

我正在寻找一个可以帮助我的好资源,

1. 优化技术的基础知识,
2. 内点法的基础知识及其与其他技术的基本差异,
3. IPM的类型,
4. 算法细节,和
5. 示例实现.

作为我的项目的一部分,我对此感兴趣,我将使用这些想法/逻辑来解决线性或二次方程组.

如果您有关于上述资源的任何信息,请与我们联系.

我在课堂上一直在做线性编程问题,但是我想知道如何编写一个特定问题的程序来解决它.如果有太多的变量或约束,我永远无法通过绘图来做到这一点.

示例问题,使用约束最大化5x + 3y:

• 5x - 2y> = 0
• x + y <= 7
• x <= 5
• x> = 0
• y> = 0

我画了这个,得到了一个有3个角的可见区域.x = 5 y = 2是最佳点.

如何将其转换为代码？我知道单纯形法.而且非常重要的是,所有LP问题都会被编码在同一个结构中吗？蛮力工作吗？

我应该使用什么算法来查找有向下限但不是上限的有向图上的最小流量？比如这个简单的例子:

在文献中,这是最小的成本流问题.然而,在我的情况下,成本与每个边缘所需流量的非零下限相同,所以我在上面提出问题.在文献中,问题是:找到单源/单宿有向无环图的最小成本流的最佳算法是什么,其中每个边具有无限容量,流上的非零下界,以及成本等于流量的下限.

根据我的研究,似乎人们处理任何类型网络的任何类型的最低成本的主要方式是将问题设置为LP类型问题并以此方式解决.然而,我的直觉是没有流动的上限,即具有无限容量的边缘,使问题更容易,所以我想知道是否有一种算法专门针对这种情况使用比单纯形法等更多的"图形"技术. .人.

我的意思是,如果所有的成本和下限都是1,如上所述...我们正在寻找一个涵盖所有边缘的流程,遵守流程规则,并且不会在从s到t的任何路径上推动太多流量.这只是感觉它不应该要求LP求解器,事实上维基百科关于最小成本流的文章指出"如果容量约束被移除,问题就会减少到最短路径问题"但我认为他们正在讨论下限全部为零的情况.

还有开源C/C++代码,可以在任何地方实现最低成本流量吗？从谷歌搜索可用的东西,我发现我可以自己设置问题作为LP问题,并用开源LP解算器解决,或者我可以使用LEMON,它为最低成本流提供了几种算法.据我所知,boost图库不包含实现.

还有别的事吗？

我在二维网格上有很多点.我想将点分组成对,同时最小化对之间的欧几里德距离的总和.

例:

Given the points: 

p1: (1,1)
p2: (5,5)
p3: (1,3)
p4: (6,6)

Best solution: 
pair1 = (p1,p3), distance = 2
pair2 = (p2,p4), distance = 1
Minimized total distance: 1+2 = 3

我怀疑这个问题可以通过匈牙利算法的变体解决吗？

解决问题的最快方法是什么？

(小评论:我总是应该少于12分.)

我想知道是否有一种很好的方法(最好使用JuMP)来获得线性程序的所有最优解(如果有多个最优解).

一个例子

最小化两个概率分布之间的统计距离(Kolmogorov距离).

min sum_{i=1}^{4} |P[i] - Q[i]| over free variable Q
P = [0.25,0.25,0.25,0.25]
sum_i P[i] = 1
Q[1] + Q[4] = 1
sum_i Q[i] = 1 -> Q[2],Q[3] = 0

注意我们可以将优化表示为线性程序,目标就变成了

min S >= sum_i S[i]
S[i] >= P[i]-Q[i]
S[i] >= Q[i]-P[i]

这个问题没有唯一的解决方案,而是跨越最优解的子空间

Q1 = [0.75,0,0,0.25]
Q2 = [0.25,0,0,0.75]

两者都具有0.5的最小距离,这两种解决方案的任何凸组合都是最佳的.

我想知道是否有一种很好的方法可以找到所有这些最佳极值点(跨越最佳子空间的点)？

为什么我对此感兴趣; 给出最大Bhattacharyya系数(凹函数)的点位于静态距离的最佳子空间的中间.

到目前为止,我试图找到最佳的P,Q对(参考我给出的例子),使算法有利于通过在该项中增加1.001的权重来缩小P [i],Q [i]之间的距离.和.它似乎在某种程度上起作用,尽管我几乎无法确定.

我有一张客户表(coper)和资产分配(资产)

A = [[1,2],[3,4],[5,6]]
idx = ['coper1','coper2','coper3']
cols = ['asset1','asset2']

df = pd.DataFrame(A,index = idx, columns = cols)

所以我的数据看起来像

        asset1  asset2
coper1       1       2
coper2       3       4
coper3       5       6

我想通过一个线性优化运行它们(我有constraints- somtehing像sum of all of asset_i <= amount_on_hand_i和sum of coper_j = price_j)

所以我必须把这个2D矩阵变成一维矢量.融化容易

df2 = pd.melt(df,value_vars=['asset1','asset2'])

但是现在,当我尝试解开它时,我得到一个带有大量空白的6排数组!

df2.pivot(columns = 'variable', values = 'value')


variable  asset1  asset2
0            1.0     NaN
1            3.0     NaN
2            5.0     NaN
3            NaN     2.0
4            NaN     4.0
5            NaN     6.0

有没有办法在使用熔化时保留索引的'coper'部分？

我正在尝试创建最佳轮班时间表，在该时间表中将员工分配到轮班时间。输出应旨在花费最少的钱。棘手的部分是我需要考虑特定的约束。这些是：

1) At any given time period, you must meet the minimum staffing requirements
2) A person has a minimum and maximum amount of hours they can do
3) An employee can only be scheduled to work within their available hours
4) A person can only work one shift per day

在staff_availability df包含了员工的选择['Person']，可用最小-最大小时他们能够工作['MinHours']- ['MaxHours']，他们得到了多少钱['HourlyWage']，和可用性，表示小时['Availability_Hr']和15分钟片段['Availability_15min_Seg']。

注意：如果不需要，可以不必分配可用的员工轮班。他们只是可以这样做。

该staffing_requirements df包含一天中的时间['Time']和所需的工作人员['People']在这些时期。

该脚本返回df 'availability_per_member'，显示每个时间点有多少员工可用。因此， …

这个问题来自我在这里发布的相关问题.@mhum建议我的问题属于覆盖问题领域.我尝试将我的问题编码为最小集合覆盖问题,目前我有一个这种形式的数据集:

Set        Cost
(1,2)        1
(1)          1
(1,2,3)      2
(1)          2
(3,4)        2
(4)          3
(1,2)        3
(3,4)        4
(1,2,3,4)    4

目标是找到一个覆盖所有数字的好套装,并试图将总成本降至最低.我的数据集很大,至少有30000套(大小从5-40个元素不等),就像这样.是否有任何好的贪婪实现来解决这个问题,还是我自己实现这个？我不是LP的专家,但任何可以解决这个问题的LP解算器(来自numpy/scipy)都是可以接受的.

约束编程(CP)和线性规划(LP)或混合整数规划(MIP)之间有什么区别？我知道什么是LP和MIP,但不明白与CP的区别 - 或者CP与MIP和LP相同？我对此很困惑......

目标：计算两个凸多面体的交集。

我正在使用scipy.spatial.HalfspaceIntersection它。下图显示了生成的交叉点：

我的问题：确定一个初始可行点。

您会看到，当前的Python实现scipy.spatial.HalfspaceIntersection需要将 aninterior_point作为参数传递。

interior_point : ndarray of floats, shape (ndim,)
清楚地指向由半空间定义的区域内。也称为可行点，可以通过线性规划获得。

现在，目前，我正在手动提供可行点，因为我只是在起草一个原型来试验HalfspaceIntersection. 但是现在我已经到了不想手动指定它的地步。

SciPy的优化模块scipy.optimize.linprog实现了两个通用线性规划 (LP)求解器：simplex和internal-point。但是，它们似乎需要成本函数。[ 1 ]

由于我想花费尽可能少的处理时间来计算这个可行点，我想知道如何在没有成本函数的情况下运行这些 LP 方法中的任何一个，即只运行直到解决方案达到可行状态。

问题：

1. scipy.optimize.linprog计算这个可行的内点是正确的方法吗？

2. 如果是，我如何在没有成本函数的情况下使用单纯形或内点 ？

3. 为什么首先scipy.spatial.HalfspaceIntersection 需要将aninterior point作为参数传递？据我所知，半空间的交集是去除给定不等式集合的冗余不等式。为什么需要一个可行点？