balas
balas solves binary linear programming problems using the Balas Additive Algorithm.
[xopt, fopt, node] = balas(c, A, b)
Outputs:
min c'*x
such that A*x >= b
x ∈ {0,1}
where c, x, b are vectors, and A is a matrix.[xopt, fopt, node] = balas(c, A, b)
Outputs:
- xopt: optimal solution
- fopt: function value at xopt
- node: selected node
Examples
>> c = [-9 -5 -6 -4] A = [6 3 5 2;0 0 1 1;-1 0 1 0;0 -1 0 1] b = [10 1 0 0] [xopt,fopt,node] = balas(c, -A, -b)% max 9x1 + 5x2 + 6x3 + 4x4 % s.t. 6x1 + 3x2 + 5x3 + 2x4 <= 10 % x3 + x4 <= 1 % -x1 + x3 <= 0 % -x2 + x4 <= 0
[c:1x4 double] [A:4x4 double] [b:1x4 double] [xopt:4x1 double] [fopt:-14] [node:19] >> xopt# 1 1 0 0 >> node# 19
>> c = [1 1 1 1 1 1]
A = [1 1 0 0 0 0
1 1 0 0 0 1
0 0 1 1 0 0
0 0 1 1 1 0
0 0 0 1 1 1
0 1 0 0 1 1]
b = [1 1 1 1 1 1]
[xopt, fopt, node] = balas(c, A, b)
[c:1x6 double]
[A:6x6 double]
[b:1x6 double]
[xopt:6x1 double]
[fopt:2]
[node:15]
>> fopt#
2
>> xopt#
0
1
0
1
0
0
>> node#
15
References
[1] E. Balas. "An Additive Algorithm for Solving Linear Programs with ZeroOne Variables", Operations Research, 1965.