Heuristics for the solution of Mixed-Integer Linear Programming problems

Many discrete optimization problems can be reframed as Integer Linear Programming (ILP) problems, whose complexity class is NP-Hard. Due to its NP-hardness, solving a ILP problem to optimality often requires a huge computational effort. Therefore it’s necessary to adopt greedy algorithms and heuristics that are capable of finding satisfying solutions at a lower cost. The most common heuristics don’t require a mathematical model and they are based on local search, e.g. tabu search, or population search, like genetic algorithms or particle swarm optimization. Those heuristics are not easy to apply in case of complicated constraints and/or when dealing with optimization problems that contain both continuous and discrete decision variables, known as Mixed-Integer Linear Programming (MILP) problems, hence the need of more adaptable and general heuristics. Thus, different algorithms have been proposed, like fix-and-relax, iterated local search and kernel search, based on mathematical models which impose proper forms of restriction on decision variables. This work aims to investigate and apply the kernel search framework on a specific case of study, in order to propose a reliable and well-performing problem-specific variation of the heuristic. The chosen case study is a stochastic version of the classical multi-item Capacitated Lot-Sizing Problem (CLSP), in which demand uncertainty is modelled through a scenario tree, resulting in a multi-stage mixed-integer stochastic programming model.