Operations Research

25 de Novembro, 17h00, sala 6.4.30

Michele Barbato (Université Paris 13)

Polyhedral Results and a Branch-and-Cut Algorithm for the Double Traveling Salesman Problem with Multiple Stacks


In the double TSP with multiple stacks, one performs a Hamiltonian circuit to pick up n items, storing them in a vehicle with s stacks of finite capacity q satisfying last-in-first-out constraints, and then delivers every item to a corresponding customer by performing a Hamiltonian circuit.  For this problem we introduce an integer linear programming formulation with arc and precedence variables. We prove that a polytope arising from a relaxation of our formulation inherits all the facets of a polytope describing the Asymmetric TSP. We also explain how the underlying polytope of our formulation relates to a specific set covering polytope. These theoretical results let us obtain strengthening inequalities for our formulation.  Such inequalities are embedded into a branch-and-cut algorithm for the double TSP with two stacks, outperforming the existing exact methods to tackle this version of the problem and solving instances that were previously unsolved.

This is a joint work with Roland Grappe, Mathieu Lacroix et Roberto Wolfler Calvo.


1 de julho, 16:00, sala 6.4.35

Hossein Mostafaei (Department of Applied Mathematics, Azarbaijan Shahid Madani University, Tabriz, Iran)

Mathematical Programming Models for Pipeline Scheduling

Abstract: Pipeline systems connecting oil fields to distribution centers play a key role in the oil supply chain. They are usually multiproduct system conveying a variety of oil derivatives such as heating oil, motor gasoline, jet fuel, and liquefied gas one after the other into the same pipeline. In recent years, scheduling problem related to the pipeline input and operations has receive growing attention, with most of them including a rigorous mathematical model and a common objective function. It consists of sequencing/sizing product batches inside the pipeline and timing batch removals at depots so as to meet product demands at minimum total operational costs. Operating costs usually include, pumping, backorder and finally transition costs between different products inside the pipeline. In this presentation we intent to have an overview on some previous works addressing the operational scheduling of pipeline networks. Of the pipeline networks, straight and tree-like structures are the most common used in the oil industry.


17 de Maio, 15h00, sala 6.4.35, (Piso 4).

Ana Sofia Carvalho (Widescope)

Produto Routyn

Abstract: O Routyn é um produto de optimização de rotas de veículos desenvolvido pela Wide Scope, a empresa portuguesa de Investigação Operacional que foi fundada no seio da Faculdade de Ciências de Lisboa. Ao longo de vários anos a empresa obteve vários reconhecimentos internacionais pelo seu crescimento ao nível europeu, bem como viu o seu produto ser reconhecido por uma das principais consultoras analistas norte-americanas como um produto único e inovador no panorama internacional, fruto da tecnologia e algoritmos que emprega.


30 de Novembro, 17h00, sala 6.4.34

Mario Ruthmair

AIT – Austrian Institute of Technology

Mixed Integer Linear Programming Models for the Interdependent Lock Scheduling Problem

We consider the Interdependent Lock Scheduling Problem which arises in ship traffic on rivers with multiple watergates. Each ship starts at a fixed time and follows a given path (upstream or downstream) along which it has to pass a series of watergates. The aim of the problem is to find a lock schedule resulting in minimal total ship travel times. In a weighted objective we also consider the minimization of the number of lockages. We present several mixed integer linear programming models and use CPLEX to solve them.



16 de Novembro 17h00sala 6.4.34


Markus Leitner

Faculty of Business, Economics and Statistics, University of Vienna)

On Optimal Design of Charging Stations for Electric Vehicles


Abstract: We consider the Network Design Problem with Relays (NDPR) which gives answers to some important strategic design questions in context of e-mobility. Given a family of origin-destination pairs electric vehicles need to travel, and given the existing links that can be traversed, these questions are: (1) What are the optimal locations for placing the charging stations and how many of them are needed? (2) Could the available infrastructure be enhanced by including additional links (shortcuts), to reduce the travel distances? In contrast to previous work on the NDPR which mainly focused on heuristic approaches, we discuss exact methods based on different mixed integer linear programming formulations for the problem. We develop Branch-and-Price and Branch-Price-and-Cut algorithms that build upon models with an exponential number of variables (and constraints).  In an extensive computational study, we analyze the performance of these approaches for instances that reflect different real-world settings.


Joint work with I. Ljubic, M. Riedler, M. Ruthmair



25 de Setembro (sexta-feira), pelas 15h30, na sala 6.4.31

Li Ting (Visiting PhD student from University of Science and Technology, Beijing)

Global optimization of nonlinear problems with piecewise relaxation techniques


In this talk we address the solution of bilinear problems, a class of non-convex, nonlinear programming problems NLPs. Problems of this type are quite common in engineering and their global optimization can be quite challenging. A key aspect concerns the generation of tight relaxations for the NLP, which can be of the linear (LP) or mixed-integer linear programming (MILP) type. The former are simpler to generate but can be rather loose, whereas the latter can be as tight as desired at the expense of augmenting the size, eventually leading to intractable problems. We will discuss piecewise relaxation techniques and apply them to two problems involving: (i) optimal design of industrial wastewater treatment networks; (ii) pooling problems in the petroleum industry. The results show that it is possible to obtain orders of magnitude improvements in performance compared to state-of-the-art, commercial, global optimization solvers.