标签: linear-programming

3天后，我无法将python程序打包成.exe文件。我试过 py2exe（它不断错过模块）和 PyInstaller。

这是复杂的部分。我的程序使用了许多额外安装的模块（coopr、pyomo、openpyxl、glpk、cbc、pyutilib、numpy 等）。这些反过来又导入了各种其他东西，我无法追踪它（PyInstaller 警告日志列出了 676 行丢失或可能不需要的模块。）

但是，我得到了（通过将“缺失”模块的导入添加到我的程序中）一个 .exe 版本，它通过双击或从命令行运行，没有打印任何错误。

问题是，程序什么都不做。我有一个包含在构建中的输入文件，我的程序读入该文件，进行一些（密集）计算，然后在同一目录中创建一个 .csv 输出文件。它作为 .py 文件工作。我的 .exe 什么也不做。

所以，如果你能告诉我出了什么问题，请继续。如果没有，我想知道任何有用的步骤或想法可以尝试。在这一点上，我已经用尽了可以从程序和文档中找到的反馈。

我有一个复杂的问题,我想知道现有的,易于理解的解决方案模型是否存在或适用,例如旅行商问题.

输入:

• N个时间事件的日历,由开始和结束时间以及地点定义.
• 每个会场的容量(可以同时容纳的最大人数)
• 一组对(Ai,Aj),表示服务员Ai希望与出席者见面Aj,并Aj接受该邀请.

输出:

• 对于每个助手A,他将参加的所有活动的计时码表.主要标准是每位服务员应尽可能多地接待接受邀请的服务员,以满足空间限制.

到目前为止,我们考虑使用回溯求解(尝试所有可能的解决方案),并使用线性编程(即定义模型并使用单纯形算法求解)

更新:如果在某些情况下Ai已经满足Aj,他们不再需要见面(他们已经见过面).

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

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

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

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

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

我想用python解决一个线性程序。变量的数量（从现在开始我称之为 N）非常大（~50000），为了以scipy.optimize.linprog需要的方式表述问题，我必须构造两个 N x N 矩阵（A及B以下）。LP 可以写成

minimize: c.x
subject to:
    A.x <= a
    B.x  = b
    x_i >= 0 for all i in {0, ..., n}

其中.表示点积a，而b、 和c是长度为 N 的向量。

我的经验是构建如此大的矩阵（A并且B都有大约 50000x50000 = 25*10^8 个条目）会带来一些问题：如果硬件不是很强大，NumPy 可能根本拒绝构建如此大的矩阵（参见例如使用 Python 和 NumPy 的非常大的矩阵），即使 NumPy 创建矩阵没有问题，也存在巨大的性能问题。对于 NumPy 必须处理的大量数据，这是很自然的。

然而，尽管我的线性程序带有 N 个变量，但我使用的矩阵非常稀疏。其中一个只有第一行的条目，另一个只有前 M 行，其中 M < N/2。当然，我想利用这个事实。

据我所知（例如，尝试使用稀疏矩阵和失败来解决 Scipy 优化问题），scipy.optimize.linprog不适用于稀疏矩阵。因此，我有以下问题： …

这是我在 CPLEX 12.7.0 中解决的小规模混合整数线性优化问题中获得的引擎日志输出的一部分

    Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

      0     0      280.0338    78                    280.0338       72         
      0     0      428.8558    28                    Cuts: 89      137         
      0     0      429.5221    34                     Cuts: 2      142         
      0     0      429.7745    34                  MIRcuts: 2      143         
*     0+    0                          460.9166      429.7745             6.76%
      0     2      429.7745    34      460.9166      429.8666      143    6.74%
Elapsed time = 0.49 sec. (31.07 ticks, tree = 0.01 MB, solutions = 1)
*    35     8      integral     0      438.1448      435.6381      211    0.57% …

考虑具有钢筋和孔的混凝土板元件的以下表示.

我需要一种算法,可以在具有不同孔的任意形状上自动分布线条.

主要限制因素是:

1. 线不能在区域之外或在洞内
2. 两个并排线之间的距离不能超过变量 D
3. 线必须以固定的间隔定位I,即线的Y坐标y mod I = 0在哪里y.
4. 形状内的每个可用点都不能比一条线更远 D/2

我想通过最小化行总数N来优化解决方案.什么样的优化算法适合这个问题？

我假设大多数方法都涉及将形状简化为光栅(像素高度为I)并禁用或启用每个像素.我认为这是一个明显的LP问题,并试图用GLPK设置它,但发现使用这个简化的栅格来描述任意数量的线很难.我也怀疑解决方案空间可能太大了.

我已经在C#中实现了一个算法来完成这项工作,但还没有很好地优化.这是它的工作原理:

1. 创建几何的简化栅格
2. 使用复杂的公式计算每个单元格的分数,该公式考虑了可能的线路长度和与其他杆和障碍物的距离.
3. 确定哪些需要加固(y方向的自由单元数> D)
4. 选择具有需要加固的最高分的单元格,并在-x和+ x方向上尽可能地加强它
5. 重复

根据复杂的公式,这可以很好地工作,但是在放置最后几行时会开始给出不需要的结果,因为它永远不会移动已经放置的行.我还应该看看其他任何优化技术吗？

我试图将约3000万点(x和y坐标)聚集成簇 - 这使得它具有挑战性的增加是我试图最小化每个簇的备用容量,同时还确保簇与任何一个簇之间的最大距离点不是很大(> 5km左右).

每个集群由可以提供64点的设备组成,如果集群包含少于65个点,那么我们需要这些设备中的一个.但是,如果一个集群包含65个点,那么我们需要这些设备中的两个,这意味着我们为该集群提供了63个备用容量.我们还需要将每个点连接到群集,因此从每个点到群集的距离也是设备成本的一个因素.

最后我想以尽量减少设备的,这似乎是一个相当的问题,同时也确保对任何一个点从群集中的距离最小化平均备用容量小于5公里(近似的成本,但对于思想实验会做 - 也许有更好的方法来施加这种限制).

我尝试了多种方法:

• K-手段
  • 大多数人应该知道这是如何工作
  • 平均备用容量为32
  • 在O(n ^ 2)中运行
• ab距离的排序列表
  • 我尝试了另一种方法:
    1. 通过从数据中随机选择点来初始化群集点
    2. 确定每个点与每个簇之间的距离矩阵
    3. 将其展平为一个列表
    4. 对列表进行排序
    5. 从最小距离到最长距离将点指向聚类
    6. 分配群集点,直到它们达到64,然后不能再分配
    7. 一旦分配了所有点,就停止遍历列表
    8. 根据分配的点更新群集中心
    9. 重复步骤1 - 7,直到群集位置收敛(如在K-means中)
    10. 将附近的群集位置收集到一个群集中
  • 根据设计,其平均备用容量约为0
  • 这对我的测试数据集很有效,但是一旦我扩展到全套(3000万点),它花了太长时间,可能是因为我们必须对完整列表进行排序O(NlogN)然后迭代它直到所有点都已分配O(NK)然后重复,直到收敛
• 线性规划
  • 使用库实现起来非常简单,但由于复杂性,也花了太长时间

我对可能最适合的算法/语言的建议持开放态度.我有机器学习的经验,但想不出用这种方法做这个的明显方法.

如果我错过任何信息,请告诉我.

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

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'，显示每个时间点有多少员工可用。因此， …

我有两个多边形BP，GP并由-x+y<=1 and x+y<= 5 and x-y<=3 and -y <= 0黑色多边形和-1<=x<=4 and 0 <= y <= 3绿色多边形的不等式约束集描述。

我的目标是使用 LP 来找到分数问题的最佳解决方案：鉴于BGP 中的最大值是多少lambda，使得

B = λ*B_BP + (1-λ)*B_GP

换句话说，我想B在上述意义上找到多边形内部的最大部分。对于我奋力写一个LP计划，我认为，如果我们写BP作为矩阵不等式条件，我们得到每一个B_BP是这样的 M_BP*B_BP <= C人C是一个载体(1,5,3,0)，并M_BP为矩阵((-1,1),(1,1),(1,-1),(0,-1))。所以我认为它应该类似于，给定 B = x_1+x_2

最大化 lambda

服从 M_BP*L_BP <= C_B

并且 B_BP >= 0

我认为（这是我的全部尝试，可能都是非常错误的）那个L_BP = (x,y)vector 以及lambda = (x+y)/normalization它C_B与 vector …

我试图找到可以最大化我的总和值的最佳组合，但它必须在 2 个特定约束下，因此我假设线性规划将是最合适的。

问题是这样的：一些教育世界事件希望聚集世界上最聪明的青少年学生。每个州都对 10 万名学生进行了以下考试：“数学”、“英语”、“计算机”、“历史”、“物理”……并且在每次考试中都获得了 0-100 分。

每个州都被要求从经过测试的 100K 学生中发送他们最好的 10K 参加此次活动。

您作为法国代表，被要求从您所在国家/地区的 10 万名学生中选出前 1 万名学生。为此，您需要优化它们的 MAX VALUE 以获得最佳的 TOTAL SCORE。

但是有两个主要限制：

1- 从总共 10K 选择的学生中，您需要分配特定的学生，这些学生将仅在上述 5 个科目中的 1 个特定科目上进行测试。所需的分配是： ['MATH': 4000, 'ENGLISH':3000,'COMPUTERS':2000, 'HISTORY':750,'PHYSICS':250]

2- 每个“考试科目”的分数必须有不同的权重。对于 exp：97 是数学在历史上的价值超过 97。wheights 是：['数学'：1.9，'英文'：1.7，'计算机'：1.5，'历史'：1.3，'物理'：1.1]

我的解决方案： 我尝试使用 PULP (python) 作为 LP 库并正确解决了它，但运行时间超过 2 小时。 你能找到更好（更快、更简单……）的方法来解决它吗？ 有一些 NUMPY LP 函数可以用来代替，也许会更快？它应该是一个简单的优化问题，因为我让它变得太慢和复杂。 -- 解决方案只需要在 Python 中

例如，让我们小规模地看一下同一问题：有 30 名学生，您只需要选择 15 名学生，这将为我们提供与以下学科分配需求相关的最佳组合。所需的分配是- ['数学'：5，'英文'：4，'计算机'：3，'历史'：2，'物理'：1]

这是所有 30 名学生及其成绩：

运行算法后，输出解决方案将是：

这是我原始问题的完整代码（10 万名学生）：

import pandas as pd
import numpy as …