Sperimentazione del Package CPLEX per la soluzione di Problemi di Programmazione Lineare Intera

In molte situazioni del mondo reale è spesso impossibile rappresentare certi aspetti di un problema utilizzando solo vincoli lineari e variabili continue. Nel modellare un problema del mondo reale, infatti, talvoltaènecessario rappresentare quantità discrete attraverso variabili che sono obbligate a prendere solo valori interi. Tuttavia, ci sono funzioni a variabili non-lineari che possono essere approssimate attraverso una funzione lineare a tratti. Con la programmazione matematica a questi modelli è dato genericamente il nome di Programmazione Intera Mista (MIP).

L'algoritmo intero misto di CPLEX impiega la tecnica del branch-andbound, potenziata da un'innovativa strategia cutting-edge che fornisce soluzioni veloci e robuste. I problemi di programmazione intera mista che CPLEX può risolvere sono sia di programmazione intera mista lineare sia di programmazione intera mista quadratica. Le impostazioni di default e la selezione di parametri si comportano in modo appropriato con la maggioranza dei problemi; l'utente, comunque, può personalizzare la strategia di ricerca o selezionare tecniche specializzate per le strutture dei problemi specifci. L'algoritmo intero misto include algoritmi di pre-soluzione e sofsticate strategie di cutting-plane quali Gomory, clique and cover, fow cover, GUB cover e implied bound.

La diversità dell'applicazione di modelli MIP consiste nel fatto che in molti problemi pratici, attività svolte e risorse disponibili, come ad esempio macchinari ed operai, sono indivisibili. Molti problemi richiedono la determinazione di decisioni si-no, che possono essere modellate introducendo variabili binarie, ossia variabili costrette a valori zero e uno che rappresentano rispettivamente si e no. Inoltre, molti problemi di ottimizzazione di natura combinatoria possono essere formulati come problemi interi. Lo scenario delle applicazioni include problemi come la distribuzione di beni, la schedatura della produzione ed il sequenziamento delle macchine. Inoltre includono problemi di pianifcazioni come capital bugeting, facility location, schedulazione dell'equipaggio di linee aeree, problemi di design come la comunicazione e il trasferimento del design di reti, circuiti integrati di grande scala (VLSI) e il design del sistema di produzione automatizzato.

Il branch-and-bound è una tecnica per risolvere la maggior parte dei problemi di ottimizzazione vincolati, ed è particolarmente usata nella risoluzione di quei problemi la cui soluzione attraverso un'enumerazione completa sarebbe proibitivamente costosa. Una larga varietà di problemi di questo tipo sorge nella ricerca operativa, nell'ottimizzazione combinatoria e nell'intelligenza artifciale. Tenendo conto di esperienze computazionali pratiche, il branch-and-bound è considerata la tecnica più robusta e largamente usata per risolvere problemi MIP/IP.

L'algoritmo branch-and-bound conduce, progressivamente, una ricerca della soluzione di un dato problema, suddivisa in spazio. Questo processo avviene esplorando un albero di ricerca, e normalmente viene controllata solo una piccola porzione della soluzione di spazio. Il resto dell'albero di ricerca può essere in parte eliminato utilizzando i limiti derivati da una buona soluzione ammissibile discreta o intera. Tale soluzione risulta ottimale quando il resto dell'albero è interamente eliminato.