Integer Linear Programming special case

Question

I am trying to solve a special case of Integer Linear Programming Problem, but I seem to be stuck on the algorithm.

Specifically, suppose you have some binary variable x_{1}, ... x_{n} and some inequalities of the form:

i.e. x_{2} + x_{3} + x_{10} <= 2

Note, that the coefficients of the inequalities are all unity and the right hand side is always the number of variables in the left hand side minus 1.

Also, remember that the variables x_{1}, ..., x_{n} can take the values of 0 or 1.

This is a homework (to write a program) but I cannot find an algorithm to start.

I tried with DP and Network Flow, but nothing came out.

The objective function (got lost in the edit) is to maximize the sum:

x_{1} + ... + x_{n}

So basically, your solution set would be all possible values of the variables where at least one of them is zero - or, put another way, all possible replacements except the one single one where all variables are 1? Doesn't seem like you'd need linear or dynamic programming for that one... — twalberg
– twalberg, Commented Apr 23, 2015 at 20:20
Indeed. Well, network flow might work, but i cannot model the fact that a variable appears in many equations. — ZebraMan
– ZebraMan, Commented Apr 23, 2015 at 20:27
Ah... missed the bit about having multiple simultaneous equations/inequalities to solve... That does restrict the problem space a bit more... — twalberg
– twalberg, Commented Apr 23, 2015 at 20:29
Perhaps I'm being obtuse, but why is this not solvable using ordinary linear programming? Does LP stop working when the coefficients in the constraint matrix are all 0 or 1? And what are you trying to minimize? In other words, what is wrong with the trivial solution where x_n = 0 for all n? — r3mainer
– r3mainer, Commented Apr 23, 2015 at 22:11
@squeamishossifrage You can solve the LP, but the solution won't be integer unless there's a good reason like total unimodularity, which does not apply here. — David Eisenstat
– David Eisenstat, Commented Apr 23, 2015 at 22:17

Edward Doolittle · Accepted Answer · 2015-04-24 04:36:51Z

1

The problem is equivalent to Set Cover: http://en.wikipedia.org/wiki/Set_cover_problem#Integer_linear_program_formulation. One way to see this easily is to replace x_{i} with 1-y{i}, which gives an equivalent 0-1 linear programming problem, namely

maximize (1-y_{1}) + (1-y_{2}) + ... + (1-y_{n}) = n - (y_{1} + ... + y_{n}),
which is equivalent to minimizing y_{1} + ... + y_{n},

subject to the following family of inequalities indexed by j: 
  (1-y_{i_{1j}}) + (1-y_{i_{2j}}) + ... + (1-y_{i_{kj}) <= k-1,
which are equivalent to:
  y_{i_{1j}} + y_{i_{2j}} + ... + y_{i_kj} >= 1

The equivalent formulation of the problem is the 0-1 integer linear programming formulation of Set Cover.

A greedy algorithm will provide a reasonable approximation in this situation. Determine which of the x_{i} appear most often in constraints, and set it equal to 0. All of the constraints in which x_{i0} appears are now satisfied, so they can be removed from consideration, and the variable x_{i0} can be removed from objective. Repeat with the variable x_{i1} which appears most often in the remaining constraints, etc.

Alternatively, real linear programming will also provide an approximation.

Since Set Cover is NP-hard, the best exact solution you will be able to find will be exponential in time. A simple algorithm would just try all possibilities (run through all binary numbers from x_{n}x_{n-1}...x_{1}x_{0} = 00...00 to x_{n}x_{n-1}...x_{1}x_{0} = 11...11 = 2^(n+1)-1. There are surely faster (but still exponential time) algorithms if you search.

edited Apr 24, 2015 at 4:36

answered Apr 24, 2015 at 0:23

Edward Doolittle

4,1102 gold badges18 silver badges27 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

user3386109 Over a year ago

In general, greedy algorithms are fast, but sub-optimal. Here's an easy counter example consisting of six equations (showing the coefficients) 0010 0011 1011 0101 1101 0100. Given that the order of the variables is x3 x2 x1 x0, then it's clear that x0 covers 4 equations, yet the solution is x2 and x1 which each cover 3 equations.

Edward Doolittle Over a year ago

Yup, thanks for that ... now the next question to ask: is there a dynamic programming algorithm?

Ben Voigt Over a year ago

@EdwardDoolittle: Have you ever studied "Branch and Bound"?

Edward Doolittle Over a year ago

Yes, branch and bound would work but since the problem is NP-hard it will take exponential time. Exact 0-1 Integer Linear Programming solvers use branch and bound internally.

Paul Hankin Over a year ago

To show the problem's NP hard, don't you need to show that you can reduce set cover to the problem and not vice-versa?

|

Collectives™ on Stack Overflow

Integer Linear Programming special case

1 Answer 1

6 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related