混合整数规划问题是运筹优化中经常遇到的一类问题。在这类问题中自变量的类型可能是整数也可能不是整数。相比于连续优化，混合整数规划很多时候会更难求解。在学术界混合整数规划一直是一个活跃的研究领域。
分支定界法是求解整数规划和混合整数规划类问题的一种经典算法。其中包含了分支（branch）和定界（bound）两个部分。分支部分作用是将问题分解为子问题，定界部分作用是寻找一个松弛过后的最优解，进而判断能否将某分支进行修剪。
我们以一个简单的背包问题为例：
我们需要在给定背包容量的约束下最大化背包里装的物品的价值。上面这个问题中有三种物品可以选择。对于物品而言，只有0和1两种选择。但假如我们要放入的是巧克力呢，那么我们就可以将大巧克力分成小巧克力使得背包恰好被装满。在这种情况下，我们需要将单位价值更高的巧克力先放到背包里，这样才能够保证包里装的东西价值最高。当物品是巧克力时，我们相当于将原本的整数变量进行了松弛，以达到最优。
我们也可以在混合整数规划中参照上面的思路，我们可以在定界的时候对原本限制为整数的变量松弛，得到松弛过后的最优解。实际的最优解是没有松弛过后的最优解好的，即松弛过后的最优解是实际的最优解的上界（在背包问题中，目标函数需要最大化）。假如在某一分支松弛过后的最优解仍然没有当前的最优好，代表这一分支可以被舍弃。经过松弛，我们可以更好地进行剪枝，加速分支定界法的算法执行。
割平面法也是在混合整数规划中经常会用到的方法，其中怎么割平面有很多种方法，在这里主要介绍Gomory cuts。在割平面法中，线性规划起到了很大的作用
假设有上述问题，我们首先对整数变量进行松弛。松弛过后原本的整数规划问题可以看作是一个线性规划问题。对于线性规划问题我们可以使用单纯形法这个经典的算法进行多项式时间内的求解（大部分情况）。对原问题进行松弛过后进行线性规划求解得到的解不一定为原问题的解，因为求出来的解可能不是整数。
这时我们需要对解空间进行切割，切割需要满足两个条件
切割过后的解空间中不包含上一次线性规划求出来的解
切割没有将可行解切割掉
切割过后继续使用线性松弛，重复上面的步骤，最终得出最优解。
初看割平面法可能有些懵，在这里介绍一下Gomory Cut。还是以上面的这个问题为例子。
我们首先使用单纯形法，求得线性规划的最优解。我们可以求得以下的结果
从图中我们可以看出，求出来的解x2为分整数，我们需要进行第一次Gomory cut。分别将等式两边的小数部分取出来，我们可得到
1 4 x 3 + 1 4 x 4 ≥ 1 2 \frac{1}{4}x_3+\frac{1}{4}x_4 \geq \frac{1}{2} 41x3+41x4≥21
可能有人会对这个不等式的由来有些疑问，其实是这样的。
当我们切了之后相当于原本的优化问题又添加了一个不等式。接着我们需要使用对偶单纯型法进行求解。注意，s1是新引入的松弛变量。
反复重复上面的过程，最终我们能够求出问题的最优解。
参考资料：
- coursera discrete optimization
我有一个包含模块的模型。我想在模块中覆盖模型的访问器方法。例如:classBlah这显然行不通。有什么想法可以实现吗？ 最佳答案 您的代码看起来是正确的。我们正在毫无困难地使用这个确切的模式。如果我没记错的话，Rails使用#method_missing作为属性setter，因此您的模块将优先，阻止ActiveRecord的setter。如果您正在使用ActiveSupport::Concern(参见thisblogpost)，那么您的实例方法需要进入一个特殊的模块:classBlah
有没有一种简单的方法可以将给定的整数格式化为具有固定长度和前导零的字符串？#convertnumberstostringsoffixedlength3[1,12,123,1234].map{|e|???}=>["001","012","123","234"]我找到了解决方案，但也许还有更聪明的方法。format('%03d',e)[-3..-1] 最佳答案 如何使用%1000而不是进行字符串操作来获取最后三位数字？[1,12,123,1234].map{|e|format('%03d',e%1000)}更新:根据theTinMan的
我有很多这样的文档:foo_1foo_2foo_3bar_1foo_4...我想通过获取foo_[X]的所有实例并将它们中的每一个替换为foo_[X+1]来转换它们。在这个例子中:foo_2foo_3foo_4bar_1foo_5...我可以用gsub和一个block来做到这一点吗？如果不是，最干净的方法是什么？我真的在寻找一个优雅的解决方案，因为我总是可以暴力破解它，但我觉得有一些正则表达式技巧值得学习。 最佳答案 我(完全)不懂Ruby，但类似这样的东西应该可以工作:"foo_1foo_2".gsub(/(foo_)(\d+)/
问题1:我无法通过以下方式找到将负整数转换为二进制的方法。我应该像这样转换它。-3=>"11111111111111111111111111111101"我在下面试过:sprintf('%b',-3)=>"..101"#..appearsanddoesnotshow111111bit.-3.to_s(2)=>"-11"#Thisjustadds-tothebinaryofthepositiveinteger3.问题2:有趣的是，如果我使用在线转换器，它告诉我-3的二进制是“0010110100110011”。"11111111111111111111111111111101"和"001
我有一个随机大小的散列，它可能有类似"100"的值，我想将其转换为整数。我知道我可以使用value.to_iifvalue.to_i.to_s==value来做到这一点，但我不确定我将如何在我的散列中递归地做到这一点，考虑到一个值可以是一个字符串，或一个数组(哈希或字符串)，或另一个哈希。 最佳答案 这是一个非常简单的递归实现(尽管必须同时处理数组和散列会增加一些技巧)。deffixnumifyobjifobj.respond_to?:to_i#IfwecancastittoaFixnum,doit.obj.to_ielsifobj
我有一个模块:moduleMyModuledefdo_something#...endend由类使用如下:classMyCommandextendMyModuledefself.execute#...do_somethingendend如何验证MyCommand.execute调用了do_something？我已经尝试使用mocha进行部分模拟，但是当未调用do_something时它不会失败:it"callsdo_something"doMyCommand.stubs(:do_something)MyCommand.executeend 最佳答案
我想在ruby中生成一个64位整数。我知道在Java中你有很多渴望，但我不确定你会如何在Ruby中做到这一点。另外，64位数字中有多少个字符？这是我正在谈论的示例......123456789999。@num=Random.rand(9000)+Random.rand(9000)+Random.rand(9000)但我认为这是非常低效的，必须有一种更简单、更简洁的方法来做到这一点。谢谢! 最佳答案 rand可以将范围作为参数:pa=rand(2**32..2**64-1)#=>11093913376345012184putsa.
所以我只是对此感到好奇:DataMapper为其模型使用混合classPostincludeDataMapper::Resource虽然active-record使用继承classPost有谁知道为什么DataMapper选择这样做(或者为什么AR选择不这样做)？ 最佳答案 它允许您从另一个不是DM类的类继承。它还允许动态地将DM功能添加到类中。这是我正在处理的模块中的类方法:defdatamapper_classklass=self.dupklass.send(:include,DataMapper::Resource)klass
如果我想要“00001”而不是“1”，除了我自己写填零方法之外，有没有内置的方法可以帮助我为整数填零？ 最佳答案 puts"%05d"%1#00001参见:String::%,Kernel::sprintf这是正在发生的事情。%左侧的"%05d"是C风格的格式说明符。%右边的变量就是要格式化的东西。格式说明符可以像这样解码:%-格式说明符的开头0-用前导零填充5-长度为5个字符d-被格式化的是一个整数如果你要格式化多个东西，你会把它们放在一个数组中:"%d-%s"%[1,"One"]#=>1-one
如何用HAML编写这个ERB:#OR我可以:=some_ruby_code+":"#and=some_ruby_code%br但我不想在这里连接，我想将它写成内联:(=some_ruby_code):#and(=some_ruby_code)%br 最佳答案 =some_ruby_code+":"-#and=some_ruby_code+""编辑1:我不确定您在寻找什么。你想要其中之一吗？==#{some_ruby_code}:-#and==#{some_ruby_code}或==#{some_ruby_code}:-#and=so
