2
$\begingroup$

I am interested in solving the following problem:

$$ \max c^\top x \qquad\text{s.t.}\\ Ax \le b\\ x \in \{0,1\}^n $$

One can assume that $c$, $A$ and $b$ have integer entries if that simplifies things. We can assume that the problem is feasible.

The problem is indeed NP-hard. Other hardness results also exist. For example, this problem does not have a constant factor approximation since the clique problem can be reduced to a binary program. However, I am looking for approximation algorithms for this general case. What approximation guarantees do we have? For example, is a $\frac{1}{2^n}$-approximation possible? Or anything even wilder?

$\endgroup$
4
  • $\begingroup$ Related: cs.stackexchange.com/questions/9810/… $\endgroup$
    – Lisa E.
    Commented Jun 18 at 11:13
  • $\begingroup$ $1/2^n$ is not a very useful approximation factor. $\endgroup$
    – codeR
    Commented Jun 18 at 11:25
  • $\begingroup$ Not looking for anything useful, but just a theoretical limit. $\endgroup$
    – Lisa E.
    Commented Jun 18 at 12:03
  • $\begingroup$ For example, if you show me, getting an approx. ratio better than $1/2^n$ is NP hard, I am satisfied. $\endgroup$
    – Lisa E.
    Commented Jun 18 at 12:06

2 Answers 2

4
$\begingroup$

As pointed out here (Are there practical methods for solving ILP?), there are some usefullness to form your problem as an ILP and directly give that to a solver.

There are multiple ways to tackle an ILP. One common approach is to relax it to an LP, solve the LP, and then round the solution back. Many approximation results are obtained by this route. The vertex cover and set cover are two very common examples. These approximation results typically exploit some properties of the underlying problem structure to get a tighter bound.

I would recommend that you investigate more on the structure of your specific problem and probably less on its ILP formulation. There is an excellent book on designing approximation algorithms: The Design of Approximation Algorithms by David P. Williamson and David B. Shmoys [ebook also available on their website]. This book also contains some classic examples (vertex cover, set cover, and many others) where approximation algorithms are designed using their ILP.


Update:
TSP can be written as an ILP [ref].

The general case of TSP is NPO-complete. It is hard to provide an $O(2^n)$-approximation algorithm for general TSP [ref] [ref (see Theorem 2.9)].

The following paragraph from wikipedia (though no reference is mentioned there):

There also exist problems that are exp-APX-complete, where the approximation ratio is exponential in the input size. This may occur when the approximation is dependent on the value of numbers within the problem instance; these numbers may be expressed in space logarithmic in their value, hence the exponential factor.

It is safe to conclude that ILP in general is also exp-APX-hard.

$\endgroup$
3
  • $\begingroup$ Yes, I am aware of this book. I am also aware, once I know the type of problem -- set covering/set packing/clique etc -- I can get way better bounds. But I don't want to be problem specific. I want something that works for all binary programs. $\endgroup$
    – Lisa E.
    Commented Jun 18 at 12:04
  • $\begingroup$ @LisaE. Please see if the update makes any sense. $\endgroup$
    – codeR
    Commented Jun 18 at 18:14
  • $\begingroup$ Yes, thank you! $\endgroup$
    – Lisa E.
    Commented Jun 19 at 2:31
-1
$\begingroup$

There’s a simple approach for problems restricted to integer variables: you solve for real values. If your optimal solution contains for example a variable x19 e we it’s an optimal solution x29 = 123.52 you make two copies of the instance, solve with an additional inequality x29 <= 123 or c29 >= 124 added.

You can do the same with a binary system, solve without the x19 == 0 or x29 == 1 added.

$\endgroup$
3
  • 2
    $\begingroup$ But branching takes exponential time. I believe OP wants a poly time algorithm $\endgroup$
    – Sriram
    Commented Jun 18 at 16:04
  • 1
    $\begingroup$ We’d all want a polynomial time algorithm. $\endgroup$
    – gnasher729
    Commented Jun 18 at 19:51
  • $\begingroup$ @gnasher729 please fix the typos. :) $\endgroup$
    – codeR
    Commented Jun 19 at 6:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.