Inspired by:


[Conjecture on NP-completeness of tesselation of Wang Tile up to finite size](https://mathoverflow.net/questions/157707/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](https://mathoverflow.net/questions/147374/coloring-in-lattice)


[Computational approach deciding whether a set of Wang Tile could tile the space up to some size](https://mathoverflow.net/questions/157239/computational-approach-deciding-whether-a-set-of-wang-tile-could-tile-the-space)


[Reference for Wang Tile](https://mathoverflow.net/questions/149565/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?



practical algorithms for np complete problems
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](http://yetanothermathprogrammingconsultant.blogspot.de/2009/11/assignment-problem.html)).
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!


