Cutting and Packing problems have been tackled along the two main alternatives available in optimization: mathematical programming optimization and algorithmic optimization. The former supposes the development of usually rather complex mathematical programming models and their resolution with solvers (e.g. CPLEX, GUROBI, etc.) and the latter builds on heuristics and metaheuristics search algorithms to find optimal or sub-optimal solutions (e.g. genetic algorithms, simulated annealing, tabu search, variable neighbourhood search, etc.). A recent trend in optimization is the hybridization of these two categories of methods, under a framework known as matheuristics. The scientific community, including this project’s research team, has achieved very promising results applying matheuristics to other problems and we believe on the success of this approach when dealing with Cutting and Packing problems, even in their version without uncertainty.
In a rather simple way, in stochastic programming decisions are decomposed in two sets: the set of decisions that may be made later, when uncertainty vanishes, and a set of decisions that has to be made right now. The set of decisions that is taken later is organised in scenarios and a given probability is assigned to each scenario. The first set of decisions is then made so that the excepted value of the overall problem is maximized. When applying stochastic programming to a concrete problem, even when a solution approach for the non-stochastic problem is already available, the main difficulty and subject of hard research is the scenario definition and probability assignment. The alternative robust optimization approach does not depend on scenarios or probability distributions, as leads to decisions that optimize the worst-case situation. Considered a very pessimistic approach, it can lead to too conservative decisions and is usually applied in a mild version where a probability of solutions not holding in the worst scenario is accepted.