Red Eléctrica de España uses integer programming for annual salary revisions

In this paper, we present a mixed-integer linear programming model for determining salary-revision matrices for an organization based on that organization?s general strategies. The solution obtained from this model consists of salary increases for each employee; these increases consider the employee?s professional performance, salary level relative to peers within the organization, and professional group. In addition to budget constraints, we modeled other elements typical of compensation systems, such as equity and justice. Red Eléctrica de España (REE), the transmission agent and operator of the Spanish electricity system, used the model to revise its 2010 and 2011 salary policies, and achieved results that were aligned with the company strategy. REE incorporated the model into the salary management module within its information system, and plans to continue to use the model in revisions of the module.

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.

An integer programming framework for sequencing cutting patterns based on interval graph completion

We derived a framework in integer programming, based on the properties of a linear ordering of the vertices in interval graphs, that acts as an edge completion model for obtaining interval graphs. This model can be applied to problems of sequencing cutting patterns, namely the minimization of open stacks problem (MOSP). By making small modifications in the objective function and using only some of the inequalities, the MOSP model is applied to another pattern sequencing problem that aims to minimize, not only the number of stacks, but also the order spread (the minimization of the stack occupation problem), and the model is tested.

An integer programming model for the minimum interval graph completion problem

The minimum interval graph completion problem consists of, given a graph G = ( V, E ), finding a supergraph H = ( V, E ∪ F ) that is an interval graph, while adding the least number of edges |F| . We present an integer programming formulation for solving the minimum interval graph completion problem recurring to a characteri- zation of interval graphs that produces a linear ordering of the maximal cliques of the solution graph.

Synthesis of plantwide control strategies using mixed integer optimization

Magdeburg, Univ., Fak. für Elektrotechnik und Informationstechnik, Diss., 2012

Nondictatorial Arrovian Social Welfare Functions: An Integer Programming Approach

In the line opened by Kalai and Muller (1997), we explore new conditions on prefernce domains which make it possible to avoid Arrow's impossibility result. In our main theorem, we provide a complete characterization of the domains admitting nondictorial Arrovian social welfare functions with ties (i.e. including indifference in the range) by introducing a notion of strict decomposability. In the proof, we use integer programming tools, following an approach first applied to social choice theory by Sethuraman, Teo and Vohra ((2003), (2006)). In order to obtain a representation of Arrovian social welfare functions whose range can include indifference, we generalize Sethuraman et al.'s work and specify integer programs in which variables are allowed to assume values in the set {0, 1/2, 1}: indeed, we show that, there exists a one-to-one correspondence between solutions of an integer program defined on this set and the set of all Arrovian social welfare functions - without restrictions on the range.

Integer Programming on Domains Containing Inseparable Ordered Paris

Using the integer programming approach introduced by Sethuraman, Teo, and Vohra (2003), we extend the analysis of the preference domains containing an inseparable ordered pair, initiated by Kalai and Ritz (1978). We show that these domains admit not only Arrovian social welfare functions \without ties," but also Arrovian social welfare functions \with ties," since they satisfy the strictly decomposability condition introduced by Busetto, Codognato, and Tonin (2012). Moreover, we go further in the comparison between Kalai and Ritz (1978)'s inseparability and Arrow (1963)'s single-peak restrictions, showing that the former condition is more \respectable," in the sense of Muller and Satterthwaite (1985).

Dynamic Facility Location with Modular Capacities : Models, Algorithms and Applications in Forestry

Les décisions de localisation sont souvent soumises à des aspects dynamiques comme des changements dans la demande des clients. Pour y répondre, la solution consiste à considérer une flexibilité accrue concernant l’emplacement et la capacité des installations. Même lorsque la demande est prévisible, trouver le planning optimal pour le déploiement et l'ajustement dynamique des capacités reste un défi. Dans cette thèse, nous nous concentrons sur des problèmes de localisation avec périodes multiples, et permettant l'ajustement dynamique des capacités, en particulier ceux avec des structures de coûts complexes. Nous étudions ces problèmes sous différents points de vue de recherche opérationnelle, en présentant et en comparant plusieurs modèles de programmation linéaire en nombres entiers (PLNE), l'évaluation de leur utilisation dans la pratique et en développant des algorithmes de résolution efficaces. Cette thèse est divisée en quatre parties. Tout d’abord, nous présentons le contexte industriel à l’origine de nos travaux: une compagnie forestière qui a besoin de localiser des campements pour accueillir les travailleurs forestiers. Nous présentons un modèle PLNE permettant la construction de nouveaux campements, l’extension, le déplacement et la fermeture temporaire partielle des campements existants. Ce modèle utilise des contraintes de capacité particulières, ainsi qu’une structure de coût à économie d’échelle sur plusieurs niveaux. L'utilité du modèle est évaluée par deux études de cas. La deuxième partie introduit le problème dynamique de localisation avec des capacités modulaires généralisées. Le modèle généralise plusieurs problèmes dynamiques de localisation et fournit de meilleures bornes de la relaxation linéaire que leurs formulations spécialisées. Le modèle peut résoudre des problèmes de localisation où les coûts pour les changements de capacité sont définis pour toutes les paires de niveaux de capacité, comme c'est le cas dans le problème industriel mentionnée ci-dessus. Il est appliqué à trois cas particuliers: l'expansion et la réduction des capacités, la fermeture temporaire des installations, et la combinaison des deux. Nous démontrons des relations de dominance entre notre formulation et les modèles existants pour les cas particuliers. Des expériences de calcul sur un grand nombre d’instances générées aléatoirement jusqu’à 100 installations et 1000 clients, montrent que notre modèle peut obtenir des solutions optimales plus rapidement que les formulations spécialisées existantes. Compte tenu de la complexité des modèles précédents pour les grandes instances, la troisième partie de la thèse propose des heuristiques lagrangiennes. Basées sur les méthodes du sous-gradient et des faisceaux, elles trouvent des solutions de bonne qualité même pour les instances de grande taille comportant jusqu’à 250 installations et 1000 clients. Nous améliorons ensuite la qualité de la solution obtenue en résolvent un modèle PLNE restreint qui tire parti des informations recueillies lors de la résolution du dual lagrangien. Les résultats des calculs montrent que les heuristiques donnent rapidement des solutions de bonne qualité, même pour les instances où les solveurs génériques ne trouvent pas de solutions réalisables. Finalement, nous adaptons les heuristiques précédentes pour résoudre le problème industriel. Deux relaxations différentes sont proposées et comparées. Des extensions des concepts précédents sont présentées afin d'assurer une résolution fiable en un temps raisonnable.

The berth allocation problem at port terminals : a column generation framework

Le problème d'allocation de postes d'amarrage (PAPA) est l'un des principaux problèmes de décision aux terminaux portuaires qui a été largement étudié. Dans des recherches antérieures, le PAPA a été reformulé comme étant un problème de partitionnement généralisé (PPG) et résolu en utilisant un solveur standard. Les affectations (colonnes) ont été générées a priori de manière statique et fournies comme entrée au modèle %d'optimisation. Cette méthode est capable de fournir une solution optimale au problème pour des instances de tailles moyennes. Cependant, son inconvénient principal est l'explosion du nombre d'affectations avec l'augmentation de la taille du problème, qui fait en sorte que le solveur d'optimisation se trouve à court de mémoire. Dans ce mémoire, nous nous intéressons aux limites de la reformulation PPG. Nous présentons un cadre de génération de colonnes où les affectations sont générées de manière dynamique pour résoudre les grandes instances du PAPA. Nous proposons un algorithme de génération de colonnes qui peut être facilement adapté pour résoudre toutes les variantes du PAPA en se basant sur différents attributs spatiaux et temporels. Nous avons testé notre méthode sur un modèle d'allocation dans lequel les postes d'amarrage sont considérés discrets, l'arrivée des navires est dynamique et finalement les temps de manutention dépendent des postes d'amarrage où les bateaux vont être amarrés. Les résultats expérimentaux des tests sur un ensemble d'instances artificielles indiquent que la méthode proposée permet de fournir une solution optimale ou proche de l'optimalité même pour des problème de très grandes tailles en seulement quelques minutes.

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)

A Modified Branch and Bound Algorithm to Solve the Transmission Expansion Planning Problem

In this paper a novel Branch and Bound (B&B) algorithm to solve the transmission expansion planning which is a non-convex mixed integer nonlinear programming problem (MINLP) is presented. Based on defining the options of the separating variables and makes a search in breadth, we call this algorithm a B&BML algorithm. The proposed algorithm is implemented in AMPL and an open source Ipopt solver is used to solve the nonlinear programming (NLP) problems of all candidates in the B&B tree. Strategies have been developed to address the problem of non-linearity and non-convexity of the search region. The proposed algorithm is applied to the problem of long-term transmission expansion planning modeled as an MINLP problem. The proposed algorithm has carried out on five commonly used test systems such as Garver 6-Bus, IEEE 24-Bus, 46-Bus South Brazilian test systems, Bolivian 57-Bus, and Colombian 93-Bus. Results show that the proposed methodology not only can find the best known solution but it also yields a large reduction between 24% to 77.6% in the number of NLP problems regarding to the size of the systems.

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.

Integrated pulp and paper mill planning and scheduling

This article describes a real-world production planning and scheduling problem occurring at an integrated pulp and paper mill (P&P) which manufactures paper for cardboard out of produced pulp. During the cooking of wood chips in the digester, two by-products are produced: the pulp itself (virgin fibers) and the waste stream known as black liquor. The former is then mixed with recycled fibers and processed in a paper machine. Here, due to significant sequence-dependent setups in paper type changeovers, sizing and sequencing of lots have to be made simultaneously in order to efficiently use capacity. The latter is converted into electrical energy using a set of evaporators, recovery boilers and counter-pressure turbines. The planning challenge is then to synchronize the material flow as it moves through the pulp and paper mills, and energy plant, maximizing customer demand (as backlogging is allowed), and minimizing operation costs. Due to the intensive capital feature of P&P, the output of the digester must be maximized. As the production bottleneck is not fixed, to tackle this problem we propose a new model that integrates the critical production units associated to the pulp and paper mills, and energy plant for the first time. Simple stochastic mixed integer programming based local search heuristics are developed to obtain good feasible solutions for the problem. The benefits of integrating the three stages are discussed. The proposed approaches are tested on real-world data. Our work may help P&P companies to increase their competitiveness and reactiveness in dealing with demand pattern oscillations. (C) 2012 Elsevier Ltd. All rights reserved.