• optimization
• colourful Carathéodory
• CLP
• MILP
• DC
• B&B

[ITA]
Il problema di Colourful Linear Programming nasce da un'estensione "colorata", dovuta a Bárány, del teorema di Carathéodory e può essere formulato come segue. Dati k insiemi non vuoti (che immaginiamo ciscuno contenente punti di un colore diverso) in uno spazio d-dimensionale, stabilire se esiste un insieme T contenente al più un punto di ciascun insieme (in questo senso, colorato), tale che l'origine è nell'inviluppo convesso di T. Se un tale T esiste, occorre esibirlo.

È stato dimostrato che si tratta di un problema NP-completo. Esistono condizioni sufficienti a garantire l'esistenza di una soluzione ed algoritmi efficienti che - in tali condizioni - ne calcolano una, tuttavia il problema CLP nella sua forma più generale è poco trattato in letteratura.

Nell'opera modelliamo il problema in 3 diverse formulazioni MILP e proponiamo un nuovo punto di vista della già nota formulazione QP non-convessa: trattiamo tale modello in termini di programmazione DC (Differenza di funzioni Convesse).
Dapprima abbiamo testato i modelli MIP e QP con CPLEX sia su istanze note che su istanze da noi create (con e senza soluzione).
Successivamente abbiamo studiato la formulazione DC. Traendo spunto da un algoritmo esistente, ne abbiamo esibito uno nuovo di tipo B&B, in cui abbiamo riadattato la procedura di rilassamento e sfruttato le proprietà specifiche del problema nella tecnica di branching. Abbiamo quindi implementato un codice in MATLAB per eseguire tale algoritmo e lo abbiamo testato sulle stesse istanze usate con CPLEX. Facendo un confronto con i risultati è emerso che, in generale, con il nostro algoritmo occorre visitare molti meno nodi per ottenere una soluzione. Su particolari tipi di istanze, anche in termini di tempo riusciamo ad essere più efficienti di CPLEX.
Apriamo quindi un nuovo filone di ricerca, finora mai trattato, riguardante la risoluzione di CLP difficili.

---------------------------------------------------------------
[ENG]
The Colourful Linear Programming arises from a "colourful" extension, due to Bárány, of the classical Carathéodory's theorem. It can be formulated as it follows: they are given k nonempty sets in a d-dimensional space; it is required to extablish whether there exists a subset T containing at most one point for each set, such that the origin is in the convex hull of T. In case such a set T exists, one has to show it.

It was proved its NP-completeness. There exists sufficient conditions which imply the existence of a solution and efficient algorithms were developed, but they work just under these assumptions. Anyway the CLP problem - in its general - form is poorly covered in literature.

We model the CLP problem by showing 3 different MILP formulations and by proposing a new point of view of the already known nonconvex QP formulation: we treat the latter in terms of Difference-of-Convex programming.
First we tested MIP and QP formulations with the solver CPLEX, by using both preexisting instances and new (feasible and infeasible) ones which we generated.
Then we studied the DC formulation. Inspired by a known generic DC algorithm, we proposed a new B&B algorithm in which we adjusted the relaxation procedure and exploited the specific structure of the problem for the branching technique. In order to test the scheme, we implemented a MATLAB code which we run on the same set of instances used with CPLEX for a comparison. Results are promising: with our algorithm it is necessary to visit a much lower number of nodes to find a solution. In particular, for a type of hard infeasible instances, we can find an answer of the problem in a better time than CPLEX one.
With our work we advance a new research branch, not yet studied in literature, facing hard CLP instances.