0-1 optimization with absolute value (equiv., with two inequalities)

Question

The bintprog command from the Optimization Toolbox solves 0-1 programming problems with an inequality constraint and an optional equality constraint: Ax <= b where A is a matrix and b a column vector.

I have a problem of the form |Ax| <= b, or equivalently, -b <= Ax <= b. Is there a way to solve this sort of problem with Matlab?

Answer 1

This is very easy:

You have |Ax| <= b. This is equivalent to (as you yourself noted) to -b <= Ax <= b.
So, you have additional inequality constraints: Ax <= b and -Ax <= b.
Thus you have over all AA = [ A ; -A ] and bb = [b;b] defining your abs-value constraints:

x = bintprog( f, AA, bb );   

Answer 2

With size(A) = [n,m], your constraints are of the form

for each {i in 1..m}
  -b <= sum {j in 1..n} a_{ij} * x_{ij} <= b

this is the same as two sets of constraints

for each {i in 1..m}
  sum {j in 1..n} a_{ij} * x_{ij} <= b
  sum {j in 1..n} a_{ij} * x_{ij} >= -b

Since you have to write it in the form Ax <= b, it would look like

for each {i in 1..m}
  sum {j in 1..n} a_{ij} * x_{ij} <= b
  sum {j in 1..n} -a_{ij} * x_{ij} <= b

In MATLAB, given your original A and b, you can make these "doubled" constraint matrices with

A = [A; -A];
b = [b; b];

and solve your integer program with these new (A,b).