–Wednesday February 8, 2017, 11:00 noon, room: Solvay room, NO5
On the Closest String Problem
Claudio Arbib (Università degli Studi dell’Aquila, Department of Information Engineering, Science and Mathematics)
Abstract: The Closest String Problem (CSP) calls for finding an n-string that minimizes its maximum Hamming distance from m given n-strings. This problem, originated in Code Theory, has recently be considered for applications in Bioinformatics. In the last years, integer linear programs have been successfully applied within heuristics to improve efficiency and effectiveness. We consider an ILP for the binary case (0-1 CSP) that updates the previous formulations and solve it by branch-and-cut. The method separates in polynomial time the first closure of {0,1/2}-Chvatal-Gomory cuts and can either be used stand-alone to find optimal solutions, or as a plug-in to improve heuristics based on the exact solution of reduced problems. Due to the parity structure of the right-hand side, the impressive performances obtained with this method in the binary case cannot be replicated in the general case. The problem is also formulated under different metrics, the Rank distance and the Levenshtein distance, that appear more suitable for genomic applications. Coauthored by Giovanni Felici, Mara Servilio and Paolo Ventura (IASI-CNR)
Thursday October 13th, 2016, 12:00 noon, room: P.2NO9.06
The DOMP revisited: new formulations, properties and algorithms
Diego Ponce (Université Libre de Bruxelles, Belgium, Universidad de Sevilla, Spain)
Abstract: The Discrete Ordered Median Problem (DOMP) is a modelling tool that provides flexible representations of a large variety of problems, which include most of the classical discrete location problems. In this talk we present new formulations for the DOMP and a novel embedding based on set packing constraints on a column generation approach built over a set formulation which leads to a Branch & Price method. These new formulations, allow us to gain some insights on the polyhedral structure of the DOMP that advance the knowledge of this problem over what was known previously.
– Friday September 23, 2016, 11:30AM, room: Rotule NO8
Approximation methods for a class of robust optimization problems
Marcio Costa Santos (Université de Technologie de Compiègne, France)Abstract: Multistage optimization problems under uncertainty have attracted interest from both the theoretical and the practical level and robust optimization stands among the most established methodologies for dealing with such problems. In robust optimization, we look for a solution that optimizes the objective function for the worst possible scenario. We address this problem through the lens of decomposition methods. These methods are based on the decomposition of the robust problem into a master problem (MP) and several adversarial separation problems (APs). The master problem contains the original robust constraints, however, written only for finite numbers of scenarios. Additional scenarios are generated on the fly by solving the APs. In this context, we propose new dynamic programming algorithms to solve the APs for robust problems involving budgeted uncertainty, which are based on the maximum number of deviations allowed and on the size of the deviations. These algorithms can be applied to lot-sizing problems and vehicle routing problems among others.
– Tuesday June 21st, 2016, 11:30AM, room: Rotule NO8
Zero-price Energy Offering by Multiband Robust Optimization.
Fabio D’Andreagiovanni (Zuse Institute Berlin, Germany)
Abstract: We consider the problem of a price-taker generating company that wants to select energy offering strategies for its generation units, to maximize the profit while considering the uncertainty of market price. First, we review central references available in literature about the use of Robust Optimization (RO) for price-uncertain energy offering, pointing out how they can expose to the risk of suboptimal and even infeasible offering. We then propose a new RO-based offering method, which is characterized by making offers at zero price and overcomes all the limits of other methods. We show the effectiveness of the new method on realistic instances provided by our industrial partners, getting very high increases in profit. Our method is based on Multiband Robustness (MR – Büsing, D’Andreagiovanni, 2012), an RO model that refines the classical Bertsimas-Sim model, while maintaining its computational tractability and accessibility. MR is essentially based on the use of histogram-like uncertainty sets, which result particularly suitable to represent empirical distributions commonly available in uncertain real-world optimization problems.
Essential References:
– C. Büsing, F. D’Andreagiovanni, New Results about Multi-band Uncertainty in Robust Optimization, Experimental Algorithms, Springer LNCS 7276, doi: 10.1007/978-3-642-30850-5_7
– F. D’Andreagiovanni, G. Felici, F. Lacalandra, Revisiting the use of Robust Optimization for optimal energy offering under price uncertainty, Submitted, http://arxiv.org/abs/1601.01728
– Tuesday June 28th, 2016, 11:30AM, room: Rotule NO8
Complexity, approximability ans solving strategies for the multidimensional binary vector assignment problem.
Guillerme Duvilié (LIRMM, Montpellier, France)
Abstract: Let us consider some variants of the multidimensional assignement problem, where weight of the hyperedges are locally encoded via node labels. In these problems, we are given an m-partite complete hypergraph H = (V^1, V^2, …, V^m). Each set V^i contains exactly n nodes labeled by a p-dimensional binary vector. To each hyperedge we associate a representative pp-dimensional binary vector obtained by performing the bitwise-and between every label of the nodes in the hyperedge. The weight of the hyperedge is given by the number of zeros or the number of ones in the representative vector. The objective is then to select n disjoint hyperedges while maximizing the overall number of ones (max sum 1) or minimizing the overall number of zeros (min sum 0) in the representative vectors of the selected hyperedges.
In a first time I provide negative results for both of the variants. In a second time, we present ILP formulations that can be used to solve in practice these problems and provide experimentations results based on these formulations.
– Friday, June 17th,2016, 2:00PM : room : IRIDIA’s seminar room, ULB Solbosch Campus, building C, fifth floor, room C.5.130.
“Subset Selection in Evolutionary Multiobjective Optimization” which touches topics in Multi-objective Optimization, Decision Making, and Multi-objective Evolutionary Algorithms
Prof. Carlos Fonseca (University of Coimbra, Portugal)
The potential of evolutionary algorithms in multiobjective optimization was identified early in their history. That potential has been realized over the years with the development of increasingly elaborate Evolutionary Multiobjective Optimization (EMO) algorithms that have found many important applications in the real world, and have contributed significantly to the growth in popularity of multiobjective optimization in general. Although EMO has traditionally emphasized the approximation of the whole Pareto-optimal front in an a posteriori articulation of preferences setting, preference-driven EMO algorithms capable of handling interaction with a Decision Maker (DM) were proposed early in their development. While the identification of a most preferred solution is usually seen as the ultimate goal in practice, recognizing that the search for diverse sets of alternative solutions to be presented to the DM (whether in a progressive or an a posteriori articulation of preferences scenario) implies some sort of set -oriented preference for diversity has been a turning point in EMO algorithm development. State-of-the-art algorithms such as IBEA, SMS-EMOA, MO-CMA-ES and HyPE, for example, implement multiobjective selection based on a notion of set quality that is then used to infer the quality of the individuals in the population and to introduce bias towards the better ones at the parental and/or environmental selection stages. However, the issue of how to combine such set oriented preferences with the more traditional search for a single most-preferred solution remains largely open. This talk focuses on the problem of selecting a diverse subset of non-dominated solutions from a larger set of candidate solutions according to DM preference information. The expression of set oriented preferences by the DM, their incorporation in EMO algorithms, and computational aspects of the resulting subset selection problems are considered. Existing quality-indicator and decompositi on approaches are reviewed and discussed, and an alternative perspective is introduced where set quality is not specified by the DM as such, but is inferred from the uncertainty associated with DM solution-oriented preferences instead. Recent results obtained by instantiating this idea in the form of a portfolio optimization problem are presented and discussed, and opportunities for further work are outlined at the end.
– Monday June 6th, 2016, 11:30AM, room: Solvay room
On a class of stochastic programs with exponentially many scenarios.
Gustavo Angulo Olivares (Pontificia Universidad Católica de Chile)
Abstract: In stochastic programming, it is usually assumed that the random data of the problem follows a known distribution P. When P is either continuous or finite with a large number of atoms, sampling methods can be used to approximate the true problem with a model involving a reasonable number of scenarios. But what hap- pens when P is “easy” to describe and still involves an enormous number of possible outcomes? A natural question to ask is whether we can solve the true problem without relying on sampling.
In this work, we propose a model where scenarios are affinely parametrized by the vertices or integral vectors within a given polytope Q. For instance, with Q being the n-dimensional unit cube, a vertex is a binary vector that might represent the availability of a set of resources in a particular scenario. Given that in general the number of vertices is exponential with respect to the size of the description of Q, a natural integer programming formulation that includes binary variables to choose which scenarios are satisfied is simply impractical. For this reason, we present a for- mulation that implicitly discards the k worst scenarios for a given vector x without including variables for each scenario, leading to a mixed-binary program of mod- erate size. We also study a model where the average cost of the k worst scenarios is considered, for which we present a compact linear formulation. These models can be interpreted in the context of VaR- and CVaR-constrained problems, respec- tively, exhibiting similar relationships. A key tool we exploit is a dynamic program to optimize a linear function over a set of integral matrices with lexicographically ordered rows, which might be of independent interest.
This is joint work with Mathieu Van Vyve.
– Monday May 9th, 2016, 11:30AM, room: P.OF2070
k-Delete Recoverable Robustness.
Christina Büsing (RWTH Aachen University)
Abstract: We consider 0-1 optimization problems and their k-Delete recoverable robust (k-del RR) version. K-del RR is a two stage process to deal with cost-uncertainties. In the first stage, a solution of the underlying problem is fixed. In the second stage, depending on the revealed cost, at most k elements of this solution are deleted to reduce the cost. We prove in the first part of the talk that the k-del RR shortest path and minimum matching problem are strongly NP-hard and provide on the other hand polynomial solvable cases. In the second part of the talk we focus on exact algorithms to solve these problems. We will therefore derive several different IP-formulations and provide preliminary computational results on the run-time.
– Monday May 2nd, 2016, 11:00AM, room: TBA
Modeling convex subsets of points.
Maurice Queyranne (CORE, UCL)
Abstract: Many planning and location problems in forestry, mining, political districting, farmland consolidation, as well as in data mining, entail the selection of a subset, or a partition into subsets, that should satisfy some, often ill-specified, shape constraints. A typical such shape constraint is that the subsets be convex, or “approximately convex”. Thus we consider associated optimization (sub)problems (finding a “best” convex subset) and modeling problems (representing such subsets using moderate numbers of variables and linear constraints) for convex subsets of given points. In general terms, a subset S of a given (finite) set of points in a convexity structure is convex if every given point that is in the convex hull ofS is itself in S. In the associated optimization problem, each point has a given weight (of arbitrary sign) and we seek a convex subset with maximum (or minimum) total weight. We also seek polyhedral descriptions of the characteristic vectors of convex subsets, and extended formulations that are compact (i.e., polynomial-sized), and if possible ideal (i.e., with integer extreme solutions).
We first review known results for the well-studied and well-understood one-dimensional case. In contrast, we also describe hardness results for dimensions three and higher. We then consider the two-dimensional (planar) case. Convexity can be enforced by a polynomial (quartic) number of linear inequalities in the natural binary variables, but the resulting formulation is very weak. We review existing optimization algorithms and derive compact ideal extended formulations.
We also consider related notions of convexity in partially ordered sets and in networks and metric spaces.
Friday April 29th, 2016, 11:30AM, room: Rotule NO8
Network disconnection games.
Mourad Baiou (CNRS, France)
Abstract: We study combinatorial games arising from removing arcs from a network, to disconnect two distinguished nodes s and t. First we study a two-person zero-sum game where one player, the attacker, chooses every few minutes a set of arcs that intercepts every path from s to t, then a second player, the inspector, chooses every few minutes an arc to inspect trying to find the attacker. We give polynomial algorithms to find optimal strategies for both players.
Then we study a cooperative game where a coalitions corresponds to sets of arcs, and the value of a coalition S is the maximum number of disjoint st-cuts included in S. This is the number of independent ways that a coalition can use to disconnect s and t. We give polynomial algorithms for testing membership to the core and for computing the nucleolus. And if we have time, we study disruption games, where a coalition wins if it disconnects s and t. We give a polynomial combinato- rial algorithms for finding the least-core and for computing the nucleolus of the least-core.
– Date: Friday 4th of March, 2016 11:30
Location: U.L.B., Campus La Plaine, room P.2NO8.08
Title: Scheduling a soccer league
Speaker: Frits Spieksma, KU Leuven
Abstract: Soccer has become a major business involving many stakeholders, such as teams, police, fans, sponsors, and broadcasting companies. Huge amounts of money are being paid for the broadcasting rights, illustrating the economic value of soccer competitions. It also emphasizes the relevance of finding a good schedule. Each involved party has numerous (possibly conflicting) constraints and wishes, and a schedule that satisfies all constraints and wishes simply doesn’t exist. Hence, developing a schedule that is considered fair, and that is acceptable to all parties, is a challenge.
We describe our experience in scheduling the ProLeague over the last seasons. We outline some of the different models we used, and we emphasize the advantages of using model-based schedules: transparency, perceived fairness, or simply said: the quality of the schedule.
– Tuesday February 23rd, 2016, 11:30AM, room: Rotule NO8, (ULB)
The N+-Perfect Graph Conjecture for Claw-Free Graphs.
Annegret Wagler (Université Blaise Pascal, Clermont-Ferrand, France)
Abstract: The subject of this talk is the study of the Lovasz-Schrijver PSD-operator N+ applied to the edge relaxation ESTAB(G) of the stable set polytope STAB(G) of a graph. We are particularly interested in the problem of characterizing the graphs G for which N+(G) := N+(ESTAB(G)) equals STAB(G), called N+-perfect graphs, and to find an appropriate polyhedral relaxation that coincides with N+(G) and STAB(G) if and only if G is N+-perfect. An according conjecture has been recently formulated (N+-Perfect Graph Conjecture); here we verify it for the well-studied class of claw-free graphs.
This is a brand-new result (we plan to submit the paper to IPCO 2016).
___2015________________________________________________________________________________
– Wednesday December 9th, 2015, 11:30AM, room: TBA (ULB)
A scalable resilient routing scheme.
Dritan Nace (Université de Technologie Compiègne, France)
Abstract: The context of this study is the total or partial replacement of a network by switches or new generation routers. Networks based on these equipments may represent an interesting alternative to conventional router networks. Our aim is to propose a fully distributed resilient routing strategy which ensures that wherever a link or node fails the traffic can always be (re)routed to the destination by an alternative route which is embedded in a preplanned tree. Hence, the routing will be transparent to occurring failures and the routing decision in each node will be done on basis of the couple (destination, entry node). We show that under mild conditions a routing scheme that ensures routing on this basis and it is resilient to single link failures exists. We generalize this to single node failures and provide numerical results showing the link dimensioning cost of this routing scheme. Exact formulation and heuristic approaches are proposed and numerical results will be presented.
(Joint work with: S.T. Pham, J. Carlier, J-L. Lutton and J. Lattmann)
The speaker is hosted by GOM.
– Thursday, December 03rd, 2015 | N1 – 11.00am, (HEC Ulg) HEC Ulg | Rue Louvrex 14, 4000 LIEGE (N1) Room 034
An exact algorithm for parallel machine scheduling with conflicts
Pieter Vansteenwegen (KU Leuven) / Roel Leus
We consider an extension of classic parallel machine scheduling, where an undirected conflict graph is part of the input. Each node in the graph represents a job and an edge implies that its two jobs cannot be scheduled on the same machine. The goal is to find an assignment of the jobs to the machines such that the maximum completion time is minimized. We present an exact algorithm based on branch and price.
– Friday September 4th at 11.00. (ULB)
Framework for fast algorithm development and scheduling with additional resources
Pedro Alfaro Fernandez (Universitat Politecnica de Valencia and Technological Institute of Informatics)
Abstract: FACOP (Framework for Applied Combinatorial OPtimization) is a software developed by the SOA (Applied Optimization Systems) group where the goal is to integrate in a framework the need to solve many problems of different nature, in a standardized form, easily and fast. We will highlight the need for this framework, along with its main goals and its basic behaviour. We will finish the talk with the topic of scheduling with additional resources, specially flowshop, and the problems that have arisen when trying to approach them with traditional metaheuristics.
Thursday October 29th, 2015, 11:30AM, room: Rotule NO8, (ULB)
Revealed preference tests of collectively rational consumption behavior.
Yves Crama (HEC Management School, University of Liege, Belgium)
Abstract: To verify the empirical adequacy of a particular household consumption model, it is important to develop efficient tests that can be applied to real-world data. These tests check whether the observed household behavior is “rational”, in the sense that it is consistent with the predictions of the model. In this talk, we present different approaches based on revealed preferences to test collective models of household consumption. Testing collective rationality is computationally difficult (NP-hard). In order to overcome this negative result, we introduce mixed-integer programming formulations which can be used for medium-sized data sets. Next, we propose simulated annealing heuristics, which allow for efficient testing of the collective model on large data sets. We present the results of computational experiments with our approaches.
(joint work with Fabrice Talla Nobibon, Laurens Cherchye, Thomas Demuynck, Bram De Rock and Frits C.R. Spieksma)
The speaker is hosted by GOM.
– Monday October 26th, 2015, 11:00PM, (ULB)
AutoGraphiX-III : A new system for computer aided graph theory.
Gilles Caporossi (HEC Montréal, Canada)
Abstract: More than fifteen years after the beginning of the development of AutoGraphiX (AGX), a third version of the software is made available. In these days when increasing research is applied to complex networks (such as social networks), the use of quantities related to vertices, indicating the centrality (the importance of an actor in the network measured as a topological indicator) naturally leads researchers toward the mathematical study of these quantities. This new paradigm implies a complete change in the optimization algorithm that now natively handles multiobjective problems involving vertex-related measures.
The speaker is hosted by GOM.
– Monday October 19th, 2015, 11:30AM, room: NO5, Solvay Room, (ULB)
k-Delete Recoverable Robustness.
Christina Büsing (RWTH Aachen University)
Abstract: We consider 0-1 optimization problems and their k-Delete recoverable robust (k-del RR) version. K-del RR is a two stage process to deal with cost-uncertainties. In the first stage, a solution of the underlying problem is fixed. In the second stage, depending on the revealed cost, at most k elements of this solution are deleted to reduce the cost. We prove in the first part of the talk that the k-del RR shortest path and minimum matching problem are strongly NP-hard and provide on the other hand polynomial solvable cases. In the second part of the talk we focus on exact algorithms to solve these problems. We will therefore derive several different IP-formulations and provide preliminary computational results on the run-time.
The speaker is hosted by GOM.
– Monday October 19th, 2015, 10:30AM, room: NO5, Solvay Room, (ULB)
Redesigning Benders Decomposition for Large Scale Facility Location.
Ivana Ljubic (Essec Business School, Paris, France)
Abstract: The Uncapacitated Facility Location (UFL) problem is one of the most famous and most studied problems in the Operations Research literature. Given a set of potential facility locations, and a set of customers, the goal is to find a subset of facility locations to open, and to allocate each customer to open facilities, so that the facility opening plus customer allocation costs are minimized. In our setting, for each customer the allocation cost is assumed to be a linear or separable convex quadratic function.
Motivated by recent UFL applications in business analytics, we revise approaches that work on a projected decision space and hence are intrinsically more scalable for large scale input data. Our working hypothesis is that many of the exact (decomposition) approaches that have been proposed decades ago and discarded soon after, need to be reinvented and redesigned to draw the advantage of the new technologies. To this end, we “thin out” the classical models from the literature, and use (generalized) Benders cuts to replace a huge number of allocation variables by a small number of continuous variables that model the customer allocation cost directly.
Obtained results show that Benders decomposition allows for a significant boost in the performance of a Mixed-Integer Programming solver. We report the optimal solution of a large set of previously unsolved benchmark instances widely used in the available literature. In particular, dramatic speedups are achieved for UFL’s with separable quadratic allocation costs — which turn out to be much easier than their linear counterpart when our approach is used.
Joint work with: Matteo Fischetti, Markus Sinnl
The speaker is hosted by GOM.
– Monday June 22nd, 2015, 11:00AM, room: Solbosch, C.5.130 (ULB)
On Solving Hard Quadratic 3-Dimensional Assignment Problems from Wireless Comminications
Hans Mittelmann (Arizona State University, USA)
Abstract: We address the exact solution of a very challenging (and previously unsolved) instance of the quadratic 3-dimensional assignment problem, arising in digital wireless communications. The paper describes the techniques developed to solve this instance to proven optimality, from the choice of an appropriate mixed integer programming formulation, to cutting planes and symmetry handling. Using these techniques we were able to solve the target instance with moderate computational effort (2.5 million nodes and one week of computations on a standard PC). Further such problems with different modulations and thus reduced symmetry are near optimally solved using metaheuristic and engineering ad hoc approaches.
The speaker is hosted by Martine Labbé. This is a joint seminar between the CS department and IRIDIA.
– Tuesday May 5th, 2015, 12:00PM, room: Rotule NO8 (ULB)
Modeling and Solving the One-to-One Multi-Commodity Pickup and Delivery Traveling Salesman Problem
Mario Ruthmair (AIT, Austria)
Abstract: We address the one-to-one multi-commodity pickup and delivery traveling salesman problem (m-PDTSP) which is a generalization of the TSP and arises in several transportation and logistics applications. The objective is to find a minimum-cost directed Hamiltonian path which starts and ends at given depot nodes, the demand of each given commodity is transported from the associated source to its destination, and the vehicle capacity is never exceeded. In contrast, the many-to-many one-commodity pickup and delivery traveling salesman problem (1-PDTSP), just considers a single commodity and each node can be a source or target for units of this commodity. We show that the m-PDTSP is equivalent to the 1-PDTSP with additional precedence constraints defined by the source-destination pairs for each commodity and explore several models based on this equivalence. In particular, we consider a formulation based on a 3-dimensional layered graph that combines time and load together and achieves tight LP bounds, at the cost of a large model size. Especially for tightly capacitated instances with a large number of commodities our branch-and-cut algorithms outperform the existing approaches. For the uncapacitated m-PDTSP (sequential ordering problem) we are able to solve to optimality several open instances from the TSPLIB.
The speaker is hosted by GOM.
– Tuesday April 21st, 2015, 12:00PM, room: Rotule NO8, (ULB)
A multi-stage stochastic supply network design problem with financial decisions and risk management: modeling aspects and an exact algorithm
Francisco Saldanha da Gama (University of Lisbon, Portugal)
Abstract: Structuring a global supply chain is a complex decision making process. The complexity arises from the need to integrate several decisions each of which with a relevant contribution to the performance of the whole system. In such problems, the typical input includes a set of markets, a set of products to be manufactured and/or distributed, demand forecasts for the different markets and some information about future conditions (e.g., production and transportation costs). Making use of the this information, companies must decide where facilities (e.g., plants or distribution centers) should be set operating, how to allocate procurement/production activities to the different facilities, and how to plan the transportation of products through the supply chain network in order to satisfy customer demands. Often, the objective consists of minimizing the costs for building and operating the system. Historically, researchers have focused relatively early on the design of production/distribution systems. However, in the last decade, much research has been done to progressively develop more comprehensive (but tractable) models that can better capture the essence of many supply chain network design (SCND) problems and obtain useful tools for helping decision making processes. However, many aspects of practical relevance in supply chain management are still far from being fully integrated in the models existing in the literature. Financial decisions and risk measures are among them. In corporate planning, financial decisions may strongly interact with the supply chain planning. The evaluation of the investments made in a supply chain is usually based on their return rate. This fact calls for the inclusion of revenues in SCND models, which also gives the possibility of setting a target for the return on investment. Additionally, the multi-period nature of some decisions has often to be accommodated in the models. Finally, the uncertainty associated with future conditions that may influence the input of the problem can hardly be neglected. In this talk, a modeling framework is discussed for supply network design problems capturing the above features. For the resulting multi-stage mixed-integer stochastic programming formulation an exact procedure is described which turns out to be a general algorithm for multi-stage stochastic problems involving integer variables. Computational tests performed using randomly generated instances are reported.
The speaker is hosted by GOM.
– Thursday April 16th, 2015, 10:00AM, Place : (KULeuven) Campus KULAK, E. Sabbelaan 53, BE8500, Kortrijk ( http://www.kuleuven-kulak.be/nl/over-kulak/contact/route_nl)
Clarisse Dhaenens, Laetitia Jourdan and Marie-El?onore Marmion
“Synergy of knowledge and optimization”
Abstract: In our previous works, we have proposed several kinds of approaches that combine knowledge and combinatorial optimization. In this talk, we will first focus on how knowledge discovery tasks can be modelized as combinatorial optimization problems and then, solved thanks to metaheuristics. We will give some successful applications in health and biology. Secondly, we will present how knowledge can help to improve the search by understanding what makes a solution good/interesting or not for one problem. Finally, we will discuss about how knowledge on fitness landscape can help to design new metaheuristics.
– Thursday February 12th, 2015, 12:00PM, room: Rotule NO8, (ULB)
Railway Timetabling for Passengers
Peter Sels (Logically Yours/Infrabel/KU Leuven)
Abstract: The practice of railway timetabling is still mainly a manual one and takes more than hundred man-months for Belgium. Infrabel, the Belgian Railway Infrastructure Manager company, explores more automated ways to tackle this problem. A Mixed Integer Linear (MILP) Optimisation model of which the constraints are based on the Periodic Event Scheduling Problem (PESP) approach was constructed. The innovative stochastic objective is to minimize expected passenger time in practice. Cyclic timetables that withstand comparison with the manually constructed ones are computed in about two hours.
The speaker is hosted by GOM.
_____________________________________________________________________________________
2 0 1 4
– Thursday December 18th, 2014, 11:00AM, room: 2NO7.07, (ULB)
GCG: A Generic Branch-Price-and-Cut Solver
Marco Lübbecke (Aachen University, Germany)
Abstract: We implemented GCG, a branch-price-and-cut solver based on the branch-price-and-cut framework SCIP. Given a MIP, the solver performs a Dantzig-Wolfe reformulation (based on user input, or in some cases the solver suggests a reformulation), does column generation and full branch-price-and-cut. GCG inherits advanced MIP solving features from SCIP, like presolving, propagation, (combinatorial) cutting planes, pseudo-costs etc. A number of additional plugins are implemented which are specific to exploiting the availability of having an original compact and an extended column generation formulation, like primal heuristics or branching rules. We report on computational experiments on a number of applications, recent development and future plans for the code, and discuss what can be learned from a generic solver.
The speaker is hosted by GOM.
– Wednesday December 3rd, 2014, 12:30PM, room: 2NO7.08, (ULB)
Virtual Network Embedding: Models, Complexity, and Computations
Arie Koster (Aachen University, Germany)
Abstract: Virtualization techniques allow for the coexistence of many virtual networks jointly sharing the resources of an underlying physical network. We focus on the service provider’s point of view of deciding not only which virtual network requests to accept, but also which quantity of resources to reserve from the physical network owner so to maximize the revenue. We present Mixed-Integer Linear Programming formulations for the problem, discuss its complexity for special cases, and investigate them computationally.
The speaker is hosted by GOM.
– Wednesday November 26th, 2014, 11:00AM, room: OF.2072, (ULB)
Extensions and limitations of a simple approach to revenue management
Patrice Marcotte (Université de Montréal, Canada)
Abstract: In the airline industry, and others as well, firms apply a set of “revenue management” techniques in order to maximize their profits. One of them consists in dynamically controlling the supply of available products, in order to match these products with demand. For instance, economy fares will be unavailable at dates close to departure, in order not to turn down customers with high willingness-to-pay. This problem can be fairly easily formulated as a stochastic and dynamic mixed integer program where, at each time period, one has to decide the set of products that are available. Unfortunately, the curse of dimensionality makes this approach infeasible. An alternative is to consider a static and deterministic approximation, which performs surprisingly well. In this presentation, we present variants of this approach that embed rules that are typically encountered in the airline industry, and show how the resulting mixed integer programs can be tackled within a column generation framework, either exact or heuristic. The efficiency of this approach is demonstrated on standard benchmarks from the literature, and as well as a real application.
The speaker is hosted by GOM.
– Thursday November 13th, 2014, 12:30PM, room: 2NO7.08, (ULB)
Exact solution of quadratic programs through quadratic convex reformulation
Souror Elloumi (ENSIIE and CEDRIC, France)
Abstract: We consider problem (QP) of minimizing a quadratic function subject to linear or quadratic constraints. Variables are bounded integers. This very general problem can model many classical problems. A major difference between (QP) and integer linear programs lies in the fact that, in general, its continuous relaxation is an NP-hard optimization problem. To overcome this difficulty, the Convex Quadratic Reformulation approach transforms (QP) into a problem (QP’), equivalent to (QP), but whose continuous relaxation is a convex problem. To compute a global optimal solution to (QP) it becomes possible to solve (QP’) by an implicit enumeration algorithm based on continuous quadratic convex optimization. We make an overview of recent developments in this approach. We show in particular how positive semidefinite relaxations can be used to build the most interesting equivalent problems (QP’). We also give a vision of classical linearization as a special case of Quadratic Convex Reformulation.
The speaker is hosted by GOM.
– Monday September 8th, 2014, 12:30PM, room: 2NO7.08, (ULB)
Gas network operation and optimization under uncertainty
Jonas Schweiger (Zuse Institute Berlin, Germany)
Abstract: With the deregulations in the gas markets, the requirements on the network change rapidly and demand more flexibility from the network operators. Gas network operators therefore have to invest into their network infrastructure. As these investments are very cost-intensive and long-living, network extensions should not only focus on one bottleneck scenario, but should increase the flexibility to fulfill different demand scenarios. First, we formulate a model for network extension, that is we search cost-optimal network extensions such that an infeasible demand scenarios can be realized in the extended network. Nonlinear gas physics and discrete operation decisions make already this deterministic planning model a challenging mixed-integer non-convex optimization problem. Second, we extend this model to several scenarios and propose a decomposition. A Branch&Bound-algorithm which uses the single-scenario problem as subproblem is proposed to solve the problem. Since the single-scenario problems itself are challenging problems, we solve them to global optimality only in the leaf nodes of our Branch&Bound-Tree, but still use valid bounds and solutions in every node of the tree. Furthermore, we present conditions under which previously found solutions for the scenario problems can be reused to avoid recomputations.
The speaker is hosted by GOM.
– Thursday June 12th, 2014, 12:30PM, room: 2NO6.07, (ULB)
Service start time optimization in elementary shortest path problems with resource constraints
Yasemin Arda (Université de Liège)
Abstract: Besides their real-life applications, elementary shortest path problems with resource constraints are faced as the pricing sub-problem when more complex problems are solved through column generation and branch-and-price. We consider an elementary shortest path problem with resource constraints, where there is a capacitated single vehicle at the depot for serving a set of customers by respecting their associated time windows. The vehicle can start serving the customers at any desired time and can be used for a fixed amount of time. The total transportation cost is defined as a function of the total distance traveled and the total amount of time that the vehicle spends by performing the assigned trip. Every time the vehicle visits a customer, it delivers the required load and collects a revenue in return for the delivery. The objective is to determine the trip to be performed and the service start time from the depot so as to minimize the total loss, which is calculated as the total transportation cost minus the collected revenues. In this study, we develop two exact dynamic programming algorithms which can deal with an infinite number of Pareto-optimal states arising from the fact that the vehicle can depart from the depot at any point in time and charges depending on the amount of time it spends for serving customers. Apart from reporting computational results for our elementary shortest path problem, we also embed it into a column generation framework for the corresponding capacitated vehicle routing problem with time windows. Recent results for the developed branch-and-price algorithm are also reported.
The speaker is hosted by GOM.
– Thursday June 5th, 2014, 12:30PM, room: 2NO7.07 (ULB)
Approaches to bilevel programs with interval coefficients
Carmen Galé (Universidad de Zaragoza)
Abstract: Bilevel problems have been proposed for dealing with hierarchical processes involving two levels of decision making. Bilevel programs involve two optimization problems where the constraint region of one of the problems is implicitly determined by the other. In this talk, linear bilevel programs whose both objective functions coefficients are interval numbers are addressed. Interval coefficients have been used in the literature to deal with decision problems which coefficients are only approximately known. First, we focus on the optimal value range problem which consists of computing the best and worst optimal objective function values and determining the settings of the interval coefficients which provide these values. In a published paper with H.I. Calvete, we prove by examples that, in general, there is no precise way of systematizing the specific values of the interval coefficients that can be used to compute the best and worst possible optimal solutions. Taking into account the properties of linear bilevel problems, we prove that these two optimal solutions occur at extreme points of the polyhedron defined by the common constraints. Moreover, we develop two algorithms based on ranking extreme points that allow us to compute them as well as determining settings of the interval coefficients which provide the optimal value range. In a recent work, the focus is on the order relations between interval numbers that represent the decision makers’ preference. Taking into account them, we show that the bilevel problem with interval coefficients can be solved by transforming it into a bicriteria bilevel problem properly defined. We are currently working on some algorithms for solving this problem.
The speaker is hosted by Martine Labbé.
– Thursday March 27th, 2014, 12:30PM, room: 2NO6.07, (ULB)
Nurse rostering models and algorithms
Greet Vanden Berghe (KUL)
Abstract: Health care is under high pressure to improve efficiency, given increasing requirements and decreasing resources. Among the activities to optimise, nurse rostering is one of the most relevant to address. The problem is computationally complex and has potential for improvement through automated decision support. Personnel rosters also have a considerable socio-economic impact. This optimisation problem has yielded ample practice-oriented operational research approaches. Despite the vast amount of academic research results, it remains hard for novice developers to profit from general insights or re-usable approaches. This `cold start’ issue can be partially explained by complicated regulations typical for personnel environments with 24/7 duties and different in almost every organisation. The very same issue also persists due to the lack of a theoretical framework for nurse rostering. From an academic point of view, interesting models have been developed for varying nurse rostering problems. The approaches range from self-rostering and manual problem decompositions to different levels of automated decision support. The seminar will focus on the relevance of academic results and on the interplay between practical and theoretical nurse rostering contributions.
The speaker is hosted by GOM.
– Thursday March 13th, 2014, 3:00PM, room: 2NO8.08, (ULB)
Refinement heuristics for capacitated extended-ring network design
Alessandro Hill (Universiteit Antwerpen)
Abstract: We present two heuristic approaches to solve capacitated network design problems based on re finement techniques. The main idea is to improve a given solution iteratively by solving subproblems defined on structural neighbourhoods to optimality. In our generic approaches we use the exact solution techniques in the most efficient way. This means that we build subproblems of largest possible size for complexity that still can be solved with low computational e ffort in our framework. Especially for networks with capacity constraints and extended topologies these approaches turn out to be quite powerful. Although we focus on the minimization of the total edge costs in our work, related problem features such as prize collecting or locational installation costs could be integrated. We first consider the multi-depot ring star problem (MDRSP) which generalizes the ring star problem and therefore the classical travelling salesman problem. Several depots may serve a restricted number of rings by optional usage of Steiner vertices. Customers are either directly connected by such rings or assigned to them leading to ring stars. Each ring star obeys a depot-dependent customer limit. Various structural local neighbourhoods are introduced and explored as subproblems of type MDRSP themselves. We propose a branch & cut method for the MDRSP which is used to carry out the re finements. For the optimization on a global level, multiple contraction techniques are proposed leading to known vehicle routing problem variants that we solved exactly, too. The effi ciency is shown by computational results improving known upper bounds for instance classes from the literature containing up to 1000 vertices. 91% of the known best objective values are improved up to 13% in competitive computational time. Secondly, we address the capacitated ring tree problem (CRTP), a recent capacitated single-depot network design model that combines the ring topology from classical capacitated vehicle routing problems with the tree structure considered in Steiner tree problem variants. In contrast to the ring star problems a prespecifi ed subset of customers is allowed to be assigned to rings by tree structures instead of simple links. Again, we use an exact branch & cut algorithm to carry out refi nements. To increase the spectrum of neighbourhoods that can be modelled we refi ne in a local branching fashion: for several structural neighbourhood ideas, a suitable set of restricting inequalities is provided to a master model representing the overall problem. This corresponds to a strategy for the partial exploration of multiple branch & bound trees on an integer programming formulation. Preliminary results are presented and compared to bounds obtained by the exact method and a local search based heuristic approach.
The speaker is hosted by GOM.
_____________________________________________________________________________________
2 0 1 3
– Thursday November 21st, 2013, 12:30PM, room: 2NO7.07, (ULB)
Global Liner Shipping Network Design
Shahin Gelareh (University of Artois, France)
Abstract: All shipping liner companies divide their service regions into several rotations (strings) in order to operate their container vessels. A string is the ordered set of ports at which a container vessel will call. Each port is usually called at no more than twice along one string, although a single port may be called at several times on different strings. The size of string dictates the number of vessels required to offer a given frequency of service. In order to better use their shipping capacity, groups of Liner Service Providers sometimes make a short term agreement to merge some of their service routes (in a certain region) into one main ocean going rotation and p feeder rotations. In order to minimize the weighted sum of transit time, and fixed deployment costs, we develop a mixed integer linear programming model of the network design, and an allocation of proper capacity size and frequency setting for every rotation. Given that none of the existing general-purpose MIP solvers is able to solve even very small problem instances in a reasonable time, we apply a Lagrangian decomposition approach which uses a heuristic procedure and is capable of obtaining practical and high quality solutions in reasonable times. The model has been applied on a real example, and we shall present some of the results obtained by our model which show how it facilitates a better use of assets and a significant reduction in the use of fuel, therefore allowing a more environmentally friendly service.
The speaker is hosted by Bernard Fortz.
– Thursday November 14th, 2013, 12:30PM, room: 2NO7.07, (ULB)
Some Math Programming and Game Theoretic approaches for the design of Robust Railway Networks
Justo Puerto (University of Seville, Spain)
Abstract: This talk discusses and extends competitive aspects of some games proposed in the literature, where a robust railway network design problem is formulated as a non-cooperative zero-sum game in normal form between a designer/operator and an attacker. Due to the importance of the order of play and the information available to the players at the moment of their decisions, we here extend those previous models by proposing formulations of this situation as dynamic games. Besides, we propose a new mathematical programming model that optimizes both the network design and the allocation of security resources over the network. This approach also proposes a model to distribute security resources over an already existing railway network in order to minimize the negative effects of an intentional attack. The models will be illustrated with examples.
The speaker is hosted by Martine Labbé.
– Thursday November 7th, 2013, 12:30PM, room: 2NO7.07, (ULB)
Large-Scale Reformulations of Combinatorial Problems: Not All Master Problems are Created Equal
Antonio Frangioni (Università di Pisa, Italy)
Abstract: Development of a “good” mixed-integer formulation is most often a fundamental step for being able to solve hard combinatorial problems. Unfortunately, “good quality” formulations, i.e., those with low continuous relaxation gaps, are most often exceedingly large. This requires techniques for incrementally generating them, like polyhedral methods (row generation), Lagrangian relaxations (column generation), and their combinations. We will review some recently proposed ideas to improve the performances of incremental generation techniques, based on different ways to modify and reformulate the standard “model” (master problem). In particular we will concentrate on stabilization techniques, describing some ways, different but related, in which specific structures of the problem can be algorithmically exploited. Computational results will be shown to demonstrate the potential benefits of these approaches, and for pointing out the issues that still limit the widespread applicability of these techniques.
The speaker is hosted by Martine Labbé.
– Thursday October 24th, 2013, 12:30PM, room: 2NO9.06, (ULB)
Integer programming models for open stack problems
Luigi De Giovanni (University of Padova, Italy)
Abstract: In many applications, a suitable permutation of patterns (product orders, cutting patterns, electronic circuit nodes etc.) has to be found in order to optimize over some given objective function (minimization of the work-in-process, of the open stacks, of the circuit area etc.), so giving rise to the so-called Open Stack problems. Literature presents different Integer Programming models based on different representations, among which interval graphs and binary matrices. We will focus on a formulation that exploits the structural properties of consecutive ones matrices, presenting different families of valid inequalities derived from the facets of the Consecutive Ones polytope, and discussing the related separation procedures. The model is solved by a branch-and-cut method, initialized by a heuristic solution provided by a genetic algorithm. The procedure has been applied to literature benchmarks, as well as to real instances from the industry of Very Large Scale Integrated (VLSI) circuits, showing improvements with respect to previous approaches.
The speaker is hosted by Martine Labbé.
– Thursday June 6th, 2013, 12:30PM, room: Forum H, (ULB)
Column generation approachs for two combinatorial problems of a telecommunication company
Murat Firat (France Telecom, Sophia Antipolis. Orange Labs.)
Abstract: Problems that are encountered in a telecommunication company are highly complex problems, hence most of them are NP-hard. In this talk two of these problems will be mentioned: the two-level FTTH network design problem and the stable workforce assignment problem. Compact formulations of both problems that are convenient for the Column Generation (CG) method will be presented. In the formulation of the former problem, the complexity of two pricing problems are analyzed. It turns out that both pricing problems are NP-hard to approximate. The pricing problem of the latter problem is finding a team of technicians for a job that is NP-Hard as well. Our CG method is embedded into the Branch-and-Bound search for real-life instances, and we find the optimal solutions in reasonable times compared to solution times by using an LP-solver like CPLEX.
The speaker is hosted by Bernard Fortz.
– Thursday February 28th, 2013, 12:30PM, room: 2NO.506, (ULB)
Differentiating Defaulters in Credit Scoring using Data Mining and Game Theory.
Richard Weber (U. de Chile)
Abstract: In Credit Scoring we usually try to differentiate between defaulters and non-defaulters. In this work, we present a methodology for improving credit scoring models by differentiating between two forms of rational behaviour of the defaulters of loans. According to practitioners’ knowledge there are two types of defaulters, those who do not pay because of cash flow problems (“Can’t Pay”), and those that do not pay because of lack of willingness to pay (“Won’t Pay”). Within our approach the results of several supervised models are benchmarked, where the models deliver the probability of belonging to one of these three new classes (good payers, “Can’t Pays”, and “Won’t Pays”). The process brings significant improvement in classification accuracy, delivers strong insights about the nature of defaulters, and could lead to improved credit scoring systems.
The speaker is hosted by Martine Labbé.