Inference in Credal Networks Through Integer Programming

A credal network associates a directed acyclic graph with a collection of sets of probability measures; it offers a compact representation for sets of multivariate distributions. In this paper we present a new algorithm for inference in credal networks based on an integer programming reformulation. We are concerned with computation of lower/upper probabilities for a variable in a given credal network. Experiments reported in this paper indicate that this new algorithm has better performance than existing ones for some important classes of networks.

Multilinear and Integer Programming for Markov Decision Processes with Imprecise Probabilities

Markov Decision Processes (MDPs) are extensively used to encode sequences of decisions with probabilistic effects. Markov Decision Processes with Imprecise Probabilities (MDPIPs) encode sequences of decisions whose effects are modeled using sets of probability distributions. In this paper we examine the computation of Γ-maximin policies for MDPIPs using multilinear and integer programming. We discuss the application of our algorithms to “factored” models and to a recent proposal, Markov Decision Processes with Set-valued Transitions (MDPSTs), that unifies the fields of probabilistic and “nondeterministic” planning in artificial intelligence research. 

New insights on integer-programming models for the kidney exchange problem

In recent years several countries have set up policies that allow exchange of kidneys between two or more incompatible patient–donor pairs. These policies lead to what is commonly known as kidney exchange programs. The underlying optimization problems can be formulated as integer programming models. Previously proposed models for kidney exchange programs have exponential numbers of constraints or variables, which makes them fairly difficult to solve when the problem size is large. In this work we propose two compact formulations for the problem, explain how these formulations can be adapted to address some problem variants, and provide results on the dominance of some models over others. Finally we present a systematic comparison between our models and two previously proposed ones via thorough computational analysis. Results show that compact formulations have advantages over non-compact ones when the problem size is large.

Binary integer programming formulations for scheduling in market-driven foundries

This paper describes the development and solution of binary integer formulations for production scheduling problems in market-driven foundries. This industrial sector is comprised of small and mid-sized companies with little or no automation, working with diversified production, involving several different metal alloy specifications in small tailor-made product lots. The characteristics and constraints involved in a typical production environment at these industries challenge the formulation of mathematical programming models that can be computationally solved when considering real applications. However, despite the interest on the part of these industries in counting on effective methods for production scheduling, there are few studies available on the subject. The computational tests prove the robustness and feasibility of proposed models in situations analogous to those found in production scheduling at the analyzed industrial sector. (C) 2010 Elsevier Ltd. All rights reserved.

Multiobjective 0-1 integer programming for the use of sugarcane residual biomass in energy cogeneration

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

A genetic algorithm/mathematical programming approach to solve a two-level soft drink production problem

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Mixed-integer convex model for VAr expansion planning

This paper presents a mixed-integer convex-optimization-based approach for optimum investment reactive power sources in transmission systems. Unlike some convex-optimization techniques for the reactive power planning solution, in the proposed approach the taps settings of under-load tap-changing of transformers are modeled as a mixed-integer linear set equations. Are also considered the continuous and discrete variables for the existing and new capacitive and reactive power sources. The problem is solved for three significant demand scenarios (low demand, average demand and peak demand). Numerical results are presented for the CIGRE-32 electric power system.

An integer linear programming approach for bilinear integer programming

We introduce a new Integer Linear Programming (ILP) approach for solving Integer Programming (IP) problems with bilinear objectives and linear constraints. The approach relies on a series of ILP approximations of the bilinear P. We compare this approach with standard linearization techniques on random instances and a set of real-world product bundling problems. (C) 2011 Elsevier B.V. All rights reserved.

Hybrid constraint programming and metaheuristic methods for large scale optimization problems

This work presents hybrid Constraint Programming (CP) and metaheuristic methods for the solution of Large Scale Optimization Problems; it aims at integrating concepts and mechanisms from the metaheuristic methods to a CP-based tree search environment in order to exploit the advantages of both approaches. The modeling and solution of large scale combinatorial optimization problem is a topic which has arisen the interest of many researcherers in the Operations Research field; combinatorial optimization problems are widely spread in everyday life and the need of solving difficult problems is more and more urgent. Metaheuristic techniques have been developed in the last decades to effectively handle the approximate solution of combinatorial optimization problems; we will examine metaheuristics in detail, focusing on the common aspects of different techniques. Each metaheuristic approach possesses its own peculiarities in designing and guiding the solution process; our work aims at recognizing components which can be extracted from metaheuristic methods and re-used in different contexts. In particular we focus on the possibility of porting metaheuristic elements to constraint programming based environments, as constraint programming is able to deal with feasibility issues of optimization problems in a very effective manner. Moreover, CP offers a general paradigm which allows to easily model any type of problem and solve it with a problem-independent framework, differently from local search and metaheuristic methods which are highly problem specific. In this work we describe the implementation of the Local Branching framework, originally developed for Mixed Integer Programming, in a CP-based environment. Constraint programming specific features are used to ease the search process, still mantaining an absolute generality of the approach. We also propose a search strategy called Sliced Neighborhood Search, SNS, that iteratively explores slices of large neighborhoods of an incumbent solution by performing CP-based tree search and encloses concepts from metaheuristic techniques. SNS can be used as a stand alone search strategy, but it can alternatively be embedded in existing strategies as intensification and diversification mechanism. In particular we show its integration within the CP-based local branching. We provide an extensive experimental evaluation of the proposed approaches on instances of the Asymmetric Traveling Salesman Problem and of the Asymmetric Traveling Salesman Problem with Time Windows. The proposed approaches achieve good results on practical size problem, thus demonstrating the benefit of integrating metaheuristic concepts in CP-based frameworks.

New integer programming models for balanced multi-country kep

Le persone che soffrono di insufficienza renale terminale hanno due possibili trattamenti da affrontare: la dialisi oppure il trapianto di organo. Nel caso volessero seguire la seconda strada, oltre che essere inseriti nella lista d'attesa dei donatori deceduti, possono trovare una persona, come il coniuge, un parente o un amico, disposta a donare il proprio rene. Tuttavia, non sempre il trapianto è fattibile: donatore e ricevente possono, infatti, presentare delle incompatibilità a livello di gruppo sanguigno o di tessuto organico. Come risposta a questo tipo di problema nasce il KEP (Kidney Exchange Program), un programma, ampiamente avviato in diverse realtà europee e mondiali, che si occupa di raggruppare in un unico insieme le coppie donatore/ricevente in questa stessa situazione al fine di operare e massimizzare scambi incrociati di reni fra coppie compatibili. Questa tesi approffondisce tale questione andando a valutare la possibilità di unire in un unico insieme internazionale coppie donatore/ricevente provenienti da più paesi. Lo scopo, naturalmente, è quello di poter ottenere un numero sempre maggiore di trapianti effettuati. Lo studio affronta dal punto di vista matematico problematiche legate a tale collaborazione: i paesi che eventualmente accettassero di partecipare a un simile programma, infatti, devono avere la garanzia non solo di ricavarne un vantaggio, ma anche che tale vantaggio sia equamente distribuito fra tutti i paesi partecipanti.