Operations Research Techniques in Constraint Programming

A combinatorial problem is the problem of finding an object with some desired property among a finite set of possible alternatives. Many problems from industry exhibit a combinatorial nature. An example is the optimal routing of trucks to deliver goods from a depot to customers. There are many alternatives to distribute the goods among the trucks, and for each such distribution there are many alternative routes for each individual truck. Moreover, often we are restricted to deliver goods only within a certain time frame for each customer. This makes the search for an optimal solution even harder, because there may only be a few optimal solutions, respecting the time frames, among a huge set of possible alternatives. To solve combinatorial problems, we cannot simply consider all exponentially many possible alternatives. Some combinatorial problems are solvable by an algorithm whose running time is bounded by a polynomial in the size of the representation of the problem. These problems are considered to be efficiently solvable, and are said to belong to the class P. For other problems such method is not known to exist and they are classified as follows. If we can determine in polynomialtime whether or not a particular alternative is a solution to a certain problem, the problem is said to be in the class NP. Note that all problems in P are also in NP. If a problem is in NP and moreover every other problem in NP can be transformed to this problem in polynomial time, the problem is said to be NP-complete. NP-complete problems are the hardest problems in NP. In this thesis we focus on solution methods for NP-complete combinatorial problems. Several solution methods have been proposed to solve combinatorial problems faster. However, many real-life problems are still (yet) unsolvable, even when such techniques are applied, so further research is necessary. In this thesis we consider techniques from operations research and constraint programming to model and solve combinatorial problems