A first technique is based on the formulation of the original problem as a linear programme with integral variable. As we will see many combinatory optimisation problems can be formulated as linear programming problems with integral variables. This is very hard to solve.
A second technique that we will use is the following. A very effective way to write good lower bounds is that of using the dual problem of a relaxation of the original problem. We first consider a linear problem formulation of the original problem, then we relax the integrality constraints, then we write the dual problem of this formulation.
A third method that we will consider is based on the use of relaxations that are not linear. In particular, we will see that in some cases we can get much better bounds on the optimal solution by using the semi-definitive programming relaxation. Here the relaxation will be pretty peculiar. What we do is to relax the problem by projecting this problem in a different space with a number of dimension equal to the number of variables.
