标签: mathematical-optimization

我有一个相当数学问题需要解决:

任务是用最少量的废料从固定长度的管子中切割出预定数量的管子.

因此,假设我想从标准长度为6米的管中切出10个1米管和20个2.5米管.

我不确定这种问题的算法是什么样的？

我想创建一个不同尺寸管的变化列表,将它们装入标准尺寸的管中,然后选择具有最小浪费的变化.

首先,我不确定是否没有其他更好的方法来解决问题.

其次我没有找到解决方案我将如何创建这样的变体列表.

非常感谢任何帮助,谢谢!

我试图在C#中实现一个算法,里面有一些数学函数,如:

最小化|| xu(i) - Σjaj(i)bj || 2 +β|| a(i)|| 1

但是我不确定C#中是否有任何直接的方法用于优化,我在论坛中找不到任何东西,或者你可以提供任何建议来解决C#中的这个优化问题!

我是优化的新手,我需要在一个简单的场景中实现它:

有一家汽车制造商可以生产5种型号的汽车/货车.与可以生产的每种型号相关联的是需要的劳动时间和所需的数量的钢,以及通过销售这样的汽车/厢式车获得的利润.制造商目前拥有固定数量的钢材和人工,应该以优化总利润的方式使用.

这是我挂断的部分 - 每辆车也有最低订货量.在生产/销售该模型变得经济可行之前,公司必须制造一定数量的每种型号.optim()如果不是最终条件,这将很容易发送,因为`lower = ...'参数可以给出一个具有最小订单数量的向量,但是它不会将0视为一个选项.有人可以帮我解决这个问题,考虑到最低订单,但仍然允许订单为0？以下是我组织相关信息/约束的方法:

Dorian <- data.frame(Model = c('SmCar', 'MdCar', 'LgCar', 'MdVan', 'LgVan'),
                   SteelReq = c(1.5,3,5,6,8), LabReq=c(30,25,40,45,55),
                   MinProd = c(1000,1000,1000,200,200),
                   Profit = c(2000,2500,3000,5500,7000))

Materials <- data.frame(Steel=6500,Labor=65000)

NetProfit<-function(x) {
  x[1]->SmCar
  x[2]->MdCar
  x[3]->LgCar
  x[4]->MdVan
  x[5]->LgVan
  np<-sum(Dorian$Profit*c(SmCar,MdCar,LgCar,MdVan,LgVan))
  np
}
LowerVec <- Dorian$MinProd #Or 0, how would I add this option?
UpperVec <- apply(rbind(Materials$Labor/Dorian$LabReq, 
                   Materials$Steel/Dorian$SteelReq),2,min)
# Attempt at using optim()
optim(c(0,0,0,0,0),NetProfit,lower=LowerVec, upper=UpperVec)

最后,我想用已知分布的随机变量替换参数,例如Profit和LabReq(需要人工),并将其包装到一个函数中,该函数将Steel和Labor作为输入以及随机变量的参数.我想多次模拟然后找到给出Profit和Labor Required的特定参数的平均解决方案,所以理想情况下这个优化也会很快,以便我可以执行模拟.在此先感谢您的帮助!

当我运行使用 CPLEX 的 .NET 4 应用程序时，我在不同的机器上得到不同的输出。在我的开发机器上，CPLEX 输出一个结果（异常并停留在某个大值），而在所有其他机器上，结果正常。

首先，我认为它与操作系统有关，由于我的开发机器上同时安装了 Windows 7 x64 和 Windows 8 x64，我尝试在两个系统上运行应用程序。结果是一样的 - 有问题。

然后我尝试在两台不同的台式机上运行，​​它工作正常。我什至在虚拟机中尝试过，在我的开发机器上使用 Windows 7 来宾，在所有这些情况下，结果都可以。

如何解决这个问题？我该如何调试正在发生的事情？任何建议都会有所帮助。

附加信息：

• 我的开发机器是 Asus N73N 笔记本电脑，配备 Intel Core i7-2670QM CPU @ 2.20GHz、4 个内核、8 个逻辑处理器和 8GB RAM。
• 使用的 CPLEX：v12.4

这是我的开发机器的错误输出：

IBM ILOG CPLEX Optimization Studio Commercial Edition                         
Tried aggregator 1 time.
MIP Presolve eliminated 125 rows and 0 columns.
MIP Presolve modified 15000 coefficients.
Reduced MIP has 28795 rows, 14520 columns, and 965648 nonzeros.
Reduced MIP has 14520 binaries, 0 …

我有一个单一变量的函数,我想找到最小值,以及变量的值,其中达到最小值.目前我通过以下Python脚本实现此目的:

import numpy as np
from scipy.optimize import fmin
import math

x1=0.
y1=800.
x2=1100.
y2=-800.

v1=2000.
v2=4000.

def T(xi):
    time=sqrt((x1-xi)**2+y1**2)/v1+sqrt((x2-xi)**2+y2**2)/v2
    return time

fmin(T,0)

运行此脚本会生成以下回显:

import numpy as np
from scipy.optimize import fmin
import math

x1=0.
y1=800.
x2=1100.
y2=-800.

v1=2000.
v2=4000.

def T(xi):
    time=sqrt((x1-xi)**2+y1**2)/v1+sqrt((x2-xi)**2+y2**2)/v2
    return time

fmin(T,0)
Optimization terminated successfully.
         Current function value: 0.710042
         Iterations: 41
         Function evaluations: 82
Out[24]: array([ 301.9498125])

所以函数的最小值是~0.71,并且对于~302的参数值可以得到.但是,我想按如下方式分配这些值:

(Tmin,xmin)=fmin(T,0)
Optimization terminated successfully.
         Current function value: 0.710042
         Iterations: 41
         Function evaluations: 82
---------------------------------------------------------------------------
ValueError                                Traceback (most recent …

我用scipy.optimize.root与hybr方法(最好的一个？)找到一个数值函数的根

我在每次迭代时打印残差

delta d 117.960112417 delta d 117.960112417 delta d 117.960112417 delta d 117.960048733 delta d 117.960112427 delta d 117.960112121 delta d 1.46141491664 delta d 0.0322651167588 delta d 0.000363688881595 delta d 4.05494689256e-08

如何通过增加步长,尤其是第一次迭代之间的加速来加速根找到？我不知道算法是如何工作的,但看起来很奇怪3个第一个结果是相同的,3个nexts也完全相同.

阅读文档,我试图修改eps因素,没有成功

编辑:@sasha,这是一个非常基本的功能来说明问题

def f(X1,X2):
    print ' X1 , diff , norm ' , X1 , X2 - X1 , np.linalg.norm(X2 - X1)
    return X2 - X1

Xa = np.array([1000,1000,1000,1000])
Xb = np.array([2000,2000,2000,2000])

SOL = scipy.optimize.root(f,Xa,(Xb,))

结果如下:无论X的长度如何,我们在开始时都有3个相同的迭代

 X1 , diff , …

我想在cvxpy下的优化问题中添加许多约束.在matlab中我可以通过添加一行主语然后使用for循环来生成约束.我怎么能在cvxpy中做同样的工作,因为cvxpy中没有'subject'概念.有什么建议吗？

我正在尝试为给定的字符串找到最佳字符串集.

给定字符串:"FEEJEEDAI"

子串值:

FE - 1
JE - 2
JEE - 3
AI - 4
DAI - 6

可能的组合:

1)[FE-JE-DAI] - 1 + 2 + 6 = 9
2)[FE-JEE-DAI] - 1 + 3 + 6 = 10
3)[FE-JE-AI] - 1 + 3 + 4 = 8

最佳组合 - 2)[FE-JEE-DAI]得分10

我认为它应该是这样的:

1)检查字符串是否包含特定子字符串:

var string = "FEEJEEDAI", substring = "JE"; string.indexOf(substring) !== -1;

2)如果为true则找到它的索引

var subStringIndex = string.indexOf(substring)

3)创建新的tempString以构建组合并substring从中"切断"string

var tempString = string.slice(subStringIndex, substring.length)

4)迭代string并找到最佳tempString

我不知道如何将它构建到循环中并处理情况JE …

使用此代码时,我注意到它收敛速度令人难以置信(一秒的小部分),即使模型和/或数据非常大.我怀疑在某些情况下,我没有得到任何接近最佳解决方案的东西,但这很难证明.对于某种类型的全局优化器(如流域跳跃算法),可以选择,即使这消耗了100到1000倍的CPU.有没有人对这个问题有任何想法？

我有一个n × m网格和一组polyominos.我想知道是否可以将它们打包到网格中:不允许重叠或旋转.

我希望像大多数包装问题一样,这个版本是NP难以近似的,所以我不期待任何疯狂,但是算法可以在25×25左右的网格上找到合理的包装并且相当全面,大约10×10会很好.(我的瓷砖大多是tetrominos - 四个块 - 但它们可能有5-9 +块.)

我会接受任何人提供的任何东西:算法,论文,可以调整的现有程序.