5
$\begingroup$

Inspired by:

Conjecture on NP-completeness of tesselation of Wang Tile up to finite size

And the practicality of this topic (solving tessellation on a lattice):

coloring in lattice

Computational approach deciding whether a set of Wang Tile could tile the space up to some size

Reference for Wang Tile

I want to ask for practitioner what kind of software/programmes/algorithms that are usually used to tackle NP complete problems?

Improve this question
$\endgroup$
3
  • 4
    $\begingroup$ This is a whole field of study. Take any common NP-complete problem and search for it, combined with "solver," "algorithm," or "heuristic." $\endgroup$
    – Douglas Zare
    Commented Mar 28, 2014 at 18:58
  • $\begingroup$ examples/refs of recent/notable math/TCS research in the area via SAT $\endgroup$
    – vzn
    Commented Mar 29, 2014 at 20:01
  • $\begingroup$ Related question on Computer Science. $\endgroup$
    – Raphael
    Commented Mar 29, 2014 at 21:13

6 Answers 6

Reset to default
9
$\begingroup$

This is a very general question and difficult to answer. The kind of approach people will use is dependent on a lot of factors like the following:

  • how much work can i spend on building my solver?
  • what do i expect from my solutions (e.g. proven guarantees)?
  • what kind of problem do i have (e.g. discrete search-space vs. continuous search-space and much more factors)

If i tackle a new problem, i'm a huge fan of the common techniques used in AI and OR community, at least for a prototype-solver which will be my first step. Most of the time one will be able to implement a solver in a very short amount of time (see above: factor one) which will perform not that bad (interesting example: link). These (nearly) problem-independent solving-approaches include the following:

  • SAT-solvers (mostly open-source-development-driven; famous example: minisat)
  • SMT-solvers (basically sat with some extra-theories like real numbers)
  • Mathematical Programming (the best solvers are the commercial ones like Gurobi and CPLEX, but there are open-source solvers too like GLPK):
    • Linear Programming
    • (Mixed) Integer Programming
    • Quadratic Programming
    • ...
  • Constraint Programming (also many open-source solvers available: gecode, google or-tools))

Some comments about using these solvers:

  • they are heavily used in practice (Scheduling, Vehicle routing...)
  • you only need to model your problem (which is kind of abstract/declarative) and can trust the solver (especially the commercial ones)
  • with more work to spend, there are numerous tunings to apply: especially the field of mathematical programming offers a lot regarding problem-dependent tunings (famous example: the concorde tsp solver is based on LP)

In theory, these approaches can handle any kind of np-complete problem, but of course there will be some differences dependent on the problem. Some hazardous simplified general statements:

  • decision-problem vs. optimization-problem:

    • SAT/CP are really good at decision-problems
    • Mathematical Programming is really good at optimization problems

  • discrete vs. continuous search-space:

    • SAT is really good searching a discrete search-space
    • Mathematical Programming favours a continuous one

  • solution characteristics:

    • Mathematical Programming is good at bounding optimization-problems (in contrast to CP and particularly SAT)

Alternatively one can try to implement a problem-dependent algorithm with many common approaches like:

  • Heuristics (highly problem-dependent) + Metaheuristics (more general, but need some problem-dependent heuristics internally ;in general these combinations are incomplete in contrast to the solvers above -> they may not find a solution even if there is one; additionally there are no guarantees)
  • Approximation Algorithms
  • ...

While tackling these problems one will learn that often these different approaches are somehow connected to each other (Mathematical Programming and Approximation Algorithms) or combined (MIP + CP; CP+Heuristics).

All in all: a difficult question!

Improve this answer
$\endgroup$
6
$\begingroup$

I've been told that SAT-solvers have gotten good enough that the known reductions of other NP problems to SAT are often a reasonable approach to solving those other problems.

Improve this answer
$\endgroup$
3
$\begingroup$

Often heuristic approaches, and often rather complicated ones. So the programming languages used tend to be high-level (ML, Prolog) and it doesn't really matter that they are "inefficient" languages since rewriting in C or Fortran would only let you treat $n=7$ rather than $n=6$.

Hromkovič's book, Algorithmics for hard problems, is a good overview.

Improve this answer
$\endgroup$
3
$\begingroup$

Here is a very recent example (released just a few weeks ago):

Lenté, Christophe, Mathieu Liedloff, Ameur Soukhal, and Vincent T'Kindt. "Exponential Algorithms for Scheduling Problems." (2014). (Abstract link)

Compare the 2nd and 3rd columns of their table below. E.g., several problems whose naive enumeration algorithm has complexity $2^n$ can be solved in $\sqrt{2}\,^n$.

Table1

Improve this answer
$\endgroup$
2
$\begingroup$

I want to add to the other good answers the following interesting article explaining the successful use of SAT solvers in the work of Konev and Lisitsa on the Erdos Discrepancy problem. http://rjlipton.wordpress.com/2014/02/28/practically-pnp/

Improve this answer
$\endgroup$
1
$\begingroup$

With the often quoted definition in literature, graph clustering / partitioning is NP-hard. Various methods such as spectral partitioning, k-means etc. have been developed to find sub-optimal solutions.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .