标签: linear-programming

这个问题来自我在这里发布的相关问题.@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)都是可以接受的.

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

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

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

同

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

或者还有其他好办法吗？

我不确定这是否真的是一个"着色"问题,因为它是一个赋值/线性编程问题.我对其中任何一方都没有专业知识,所以请原谅任何可能跟随的任何新闻.但是我觉得这个问题几乎肯定已经解决/研究过了,在查看了http://en.wikipedia.org/wiki/Category:Graph_algorithms上的许多图算法之后我才发现任何事情.我希望能在正确的方向上得到一些指示.

"问题陈述"有效归结为:

1. 图中有两种类型的顶点:路由器和核心.

2. 核心仅连接到路由器.每个核心仅连接到SINGLE路由器.每个都有一个用户输入/定义的"颜色".(在我的具体问题中,颜色仅限于4/5种颜色之一).它们的颜色不能改变,它是一个输入参数.(核心是下图中的方块)

3. 路由器连接到核心以及其他路由器.他们没有分配"颜色".分配颜色是程序/算法目标的一部分.(路由器是下图中的圆形顶点.)

4. 该程序的目的是为图中的每个路由器分配颜色,使得不同颜色的顶点之间的"交叉点"/边缘的数量最小化.

(另一种观点:实质上,您会得到一个图形,其中某些顶点是彩色的,而其他顶点则不是.目标是将那些不是这样的颜色着色,使得不同颜色的顶点之间的边缘数量最小化.)

我能够将这个(我很确定)很好地表达为Integer-Linear-Program并使用LP-Solve设置解决方案/方法.我也有自己的启发式.我想知道解决这个问题的"正确"/已知/其他方法？!

非常感谢!

我遇到了AMPL的问题.我使用的是32位版本的Linux操作系统.我正在尝试解决一个简单的线性programmin问题,但我无法理解有什么问题......这里也是模型,数据文件和会话脚本.命令"解决"的答案是:找不到"minos".但解算器目前在我的文件夹中!更改解算器没有帮助.有什么建议？

问题模型:

param n;
param t;
param p{i in 1..n};
param r{i in 1..n};
param m{i in 1..n};
#Declaration of variables
var x {i in 1..n} >=0;
#Objective Function
maximize revenues: sum {i in 1..n} p[i]*x[i] ;
#Constraints
subject to Aval_Time: sum{i in 1..n} x[i]/r[i]<=t;
subject to Max_Flavor {i in 1..n}: x[i]<=m[i];

问题数据:

param n := 4;# No of Flavors
param t := 40; # Total labor hour in a week
param p := 1 1 2 1.5 3 1 …

我目前有一个有效的解决方案.我想知道是否有更优雅的方法？

首先是设置:

set.seed(315)
mat <- matrix(sample(1:5, 20, replace = TRUE), nrow = 4, ncol = 5)
> mat
     [,1] [,2] [,3] [,4] [,5]
[1,]    3    4    1    3    3
[2,]    5    3    5    1    4
[3,]    4    1    1    4    3
[4,]    3    3    1    1    1

从这个矩阵,我想创建一个5x5输出矩阵,其中i,j中的条目是列 j中的元素数量大于输入矩阵的列 i.

编辑:最初我描述了一个解决方案,其中输出解决方案的条目i,j是列 i中的元素数量大于列 j,但在输出中提供了相反的关系.我更改了描述以匹配输出,并且提供的答案中的任何差异都可能是由此产生的.

该解决方案提供了所需的输出:

mat.pm <- apply(mat, MARGIN = 2,
                function(x) {
                  return(apply(mat, MARGIN = 2, function(y) …

我在网上看到,人们可以将旅行商问题写成线性表达式,并使用CPLEX for java等软件进行计算.

我有1000个城镇,需要找一小段距离.我计划将这1000个城镇划分为约100个城镇的集群,并在这些单独的集群上执行一些线性规划算法.

我的问题是,我究竟如何将其表示为线性表达式.

所以我有100个城镇,我相信每个人都知道TSP是如何工作的.

我完全不知道如何编写满足TSP的线性约束,目标和变量.

有人可以向我解释这是如何完成的,或者给我一个清楚解释它的链接,因为我一直在研究很多,似乎找不到任何东西.

编辑:

我找到了一些额外的信息:

我们用数字0到n标记城市并定义矩阵:

这会为5个城镇产生以下矩阵吗？

限制是:

i)每个城市都来自其他城市

ii)从每个城市出发前往另一个城市

iii)该路线不会分成不同的岛屿.

同样,这对我来说是完全合理的,但我仍然无法将这些约束写为线性表达式.显然它是一个简单的矩阵.

谢谢你的帮助 !

向量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, …

我一直在玩单一车辆段调度问题(SDVSP)的算法和ILP,现在想把我的知识扩展到多车辆段调度问题(MDVSP),因为我想在我的项目中使用这些知识.

至于这个问题,我发现并实现了几种MDSVP算法.但是,我非常好奇的一个问题是如何确定所需的仓库数量(以及位置).遗憾的是,我还没有找到任何真正没有假设/要求设置软件仓库的资源.因此,我的问题是:我如何能够接近MDVSP,我可以在其中确定仓库的数量和位置？

(编辑)澄清:假设我们通常在SDVSP或MDVSP 中给出一组行程T ₁,T ₂ ... T _n.在返回仓库之前,可以连续多次行驶.离开和返回仓库通常只发生在一天的开始和结束.但作为正常问题的延伸,我们现在可以确定我们的仓库的数量和位置,而不是设置仓库.

目标是找到一种解决方案,以最小的成本驱动所有行程.成本包括死角量(汽车在行程之间以及从停车场到行驶的距离),每辆车的固定成本K,以及每个仓库的固定成本C.

我希望这会在某种程度上解决这个问题.

我有一个线性编程问题,我试图从一些二进制资源中选择优化值,基本上是一个背包问题.我遇到的问题是不同的资源具有共同的特征,我想确保我的最终解决方案具有0或2个具有特定特征的资源.有没有办法实现这个目标？尽管进行了广泛的搜索,我仍然无法想到一个或找到一个.在我的数据中,决策变量是资源,约束是这些资源的特征.请考虑以下代码:

library(lpSolve)
const_mat_so<-matrix(c(
  c(0,  0,  1,  0,  0,  0,  0,  0,  0,  0,  0,1,0,0,1,0,1)
     ,c(0,  0,  0,  0,  0,  0,  0,  1,  0,  1,  0,1,1,0,0,1,1)
     ,c(0,  0,  0,  0,  0,  1,  1,  0,  0,  0,  1,0,1,0,1,0,0)
     ,c(1,  1,  0,  1,  1,  0,  0,  0,  1,  0,  0,0,0,0,0,0,0)
     ,c(8800,   8500,   7600,   8600,   8400,   7500, 7000, 8500,   8800,   7700,   6700,5500,1200,6700,9500,8700,6500)
     ,c(0,  0,  0,  0,  0,  0,  1,  0,  0,  0,  0,0,0,0,0,0,0)
     ,c(0,  0,  0,  0,  0,  1,  0,  0,  0,  0,  0,0,0,0,0,0,0) …

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