Operations Research Techniques in Constraint Programming.pdf.pdf' (1.91 MB)

Download file# 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