In its general form, partitioning problems in graphs can be defined in the following way. Given a graph G with a weight function defined in its edges, find a partition of the vertex set of G - that satisfies certain restrictions - and minimizes the sum of the weights of the edges with both ends in different sets of the partition. This general form includes several problems known in the literature, such as the Max Cut Problem, Equicut Problem, the Clique Partitioning Problem, etc.
Some of the participants of this Project have been working in the problem, in its general form, using a polyhedral approach ([25, 9, 10]), and have obtained promising results concerning solutions of instances arising from different practical applications. Many interesting questions have appeared and are still to be solved, as planned by the participants of this Project.
Partitioning problems in hypergraphs can be defined analogously. Some preliminary results have been obtained in [7]. The computational results so far obtained indicate that there is still much to be done for this problem, both from theoretical as well as algorithmic point of view. In this Project we plan to attack this problem in order to improve the results obtained in [7].
The tridimensional packing problem consists in packing a list of
boxes 
in a box 
, so as to minimize
the height of the packing. Two strategies will be used in the treatment of
this problem: a more combinatorial approach to develop polynomial approximation
algorithms with good asymptotic performance, and an integer linear programming approach that uses column generation techniques. Some preliminary results
have been obtained with the first approach ([20, 21]).
We plan to improve these results and investigate new strategies more in the
line of the second approach.