线性组合优化 [英] linear combinatorial optimization

问题描述

我试图比蛮力更好地找出算法来解决这个组合最优化。

Am trying to figure out algorithms better than brute force to solve this combinatorial optimization.

样的问题： 为了达到2A + B的最小/最大成本可线性方程相结合 1.式2a + B = 4 2. a = 1时 3. A + B = 2 （RHS是成本）

Sample problem: To achieve 2a+b at the minimum/maximum cost combining available linear equations 1. 2a+b =4 2. a =1 3. a+b =2 (RHS is cost)

答案：联合2和3获得图2a + B = 3

Answer: Combine 2 and 3 to get 2a+b =3

发现部分线性方程的幂（所有组合），很明显的蛮力方法是不是最佳的时候目标等式是更长的幂增长巨大。

The brute force method of finding the powerset (all combinations) of component linear equation, obviously is not optimal when target equation is lengthier and the powerset grows gigantic.

是问题的背包问题的变种？ 对谁这任何指针可以优化办？

Is the problem a variant of Knapsack problem? Any pointers on who this could be done optimally?

推荐答案

这个问题可以用线性规划制定。您可以使用GNU线性编程工具包（GLPK）及其Ruby包装rglpk来解决这个问题。

This problem can be formulated using linear programming. You can use the Gnu Linear Programming Kit (GLPK) and its Ruby wrapper 'rglpk' to solve it.

下载GLPK 4.44从 http://www.gnu.org/software/glpk/为您的操作系统。解压缩包并使用以下命令安装应用程序。

Download GLPK 4.44 from http://www.gnu.org/software/glpk/ for your operating system. Unzip the package and install the application using the following command.

./configure && sudo make clean && sudo make && sudo make install

与下面的命令，打开命令行并安装rglpk。

Open the command line and install 'rglpk' with the command below.

gem install rglpk

运行此code。

Run this code.

require 'rglpk'

#min/max 2a+b
#1. 2a+b=4 
#2. a=1 
#3. a+b=2

p = Rglpk::Problem.new
p.name = "sample"
p.obj.dir = Rglpk::GLP_MAX

rows = p.add_rows(3)
rows[0].name = "2a+b=4"
rows[0].set_bounds(Rglpk::GLP_UP, 0, 4)
rows[1].name = "a=1"
rows[1].set_bounds(Rglpk::GLP_UP, 0, 1)
rows[2].name = "a+b=2"
rows[2].set_bounds(Rglpk::GLP_UP, 0, 2)

cols = p.add_cols(2)
cols[0].name = "a"
cols[0].set_bounds(Rglpk::GLP_LO, 0.0, 0.0)
cols[1].name = "b"
cols[1].set_bounds(Rglpk::GLP_LO, 0.0, 0.0)

p.obj.coefs = [2, 1]

p.set_matrix([
2, 1,
1, 0,
1, 1
])

p.simplex
z = p.obj.get
x1 = cols[0].get_prim
x2 = cols[1].get_prim

printf("z = %g; x1 = %g; x2 = %g\n", z, x1, x2)
#=> z = 3; x1 = 1; x2 = 1

这篇关于线性组合优化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！