Workshop on large scale optimization 2012

Tentative schedule

Wednesday Nov 21

Thursday Nov 22

Presentations

Click here to download the material about the column generation lecture.

(For the presentations below, click on the title to have access to the slides, when available)

• Solution methods for an integrated airline schedule planning and revenue management model, by Bilge Atasoy
• Planning of a continuous production process in the printing, by Philipp Baumann
• Cut-First Branch-and-Price-Second for the Capacitated Arc-Routing Problem, by Claudia Bode
• MILP-based approach for wilderness search and rescue mission planning, by Eduardo Feo Flushing
• Dynamic Dual Optimal Inequalities for Cutting Stock and Bin Packing, by Timo Gschwind
• Modeling and Planning with Highly non-Markovian Influence Diagrams, by Denis Maua
• A complex multi-objective production problem: from exact methods to advanced metaheuristics, by Jean Respen
• A branch-and-price algorithm to solve the integrated berth allocation and yard assignment problem in bulk ports, by Tomas Robenek
• Reactive methods to solve the berth allocation problem with stochastic arrival and handling times, by Nitish Umang

Abstracts

Atasoy Bilge, TRANSP-OR, EPFL

Solution methods for an integrated airline schedule planning and revenue management model

The sustainability of future transportation systems is closely related to the responsiveness of the supply capacity to the demand. However the majority of the models consider supply and demand models independently. We work on an integrated airline schedule planning and revenue management model where we explicitly model supply-demand interactions. An itinerary choice model is estimated based on a real data in order to represent these interactions. The resulting model is a mixed integer non-convex problem. As a first attempt to understand the added value of the integrated model, a heuristic method is developed based on two simplified versions of the problem. The results support that the integration of the demand model enables to utilize the transportation capacity more efficiently. Furthermore, to deal with the non-convexity of the problem, we work on a logarithmic transformation of the demand model and make use of decomposition methods. Therefore we obtain a mixed integer convex problem which enables us to have valid bounds on the solution of the problem.

Baumann Philipp, University of Bern

Planning of a continuous production process in the printing

Offset printing is a common method to produce large amounts of printing matter. We consider a real-world offset printing process that is used to imprint customer-specific designs on napkin pouches. The planning problem consists in the allocation of printing plate slots to designs such that a given customer demand is fulfilled, all technological requirements are met and the total printing costs are minimized. We formulate this planning problem as an MILP. For large-scale instances, we propose a constructive heuristic. In an experimental analysis, we apply both methods to real-world problem instances.

Bode Claudia, Johannes Gutenberg University Mainz

Cut-First Branch-and-Price-Second for the Capacitated Arc-Routing Problem

The capacitated arc-routing problem (CARP) is the basic multiple-vehicle arc-routing problem and has applications in waste collection, postal delivery, winter services and more. We will present a branch-and-price algorithm for the CARP, where the master program is initialized with strong cuts identified by the one-index formulation of the CARP, tours are iteratively generated by a pricing procedure, and branching is required to produce integer solutions. The focus of this presentation is twofold: First, we will show how branching decisions can be handled in the pricing problem. Second, pricing problems in routing applications are typically elementary shortest-path problems. Therefore, we empirically analyze the trade-off that different pricing problems relaxations offer in the CARP case, including the construction of new labeling algorithm for their solution and computational test on standard benchmark problems.

Feo Flushing Eduardo, IDSIA

MILP-based approach for wilderness search and rescue mission planning

Coordinating and managing search and rescue (SAR) scenarios in wilderness areas is a complex task. When the SAR team includes the presence of a large number of heterogeneous agents, in terms of sensory-motor and cognitive skills, it is inherently difficult to manually allocate predefined sectors to each agent and at the same time exploiting at the best their capabilities and mutual synergies. We present a MILP for SAR mission planning in which the model simultaneously allocates sectors to be explored and specifies the schedule of actions that each agent should follow. The formulation is a variant of the Team Orienteering Problem in which vertices correspond to sectors and the score is the reward of the exploration activities inside the corresponding area. Resulting plans guarantee a maximum reward for the search activities. A number of constraints are also included to model cooperation, proximity, and network connectivity relationships among agents. In this talk, we discuss modeling aspects, solution strategies, and computational results. We also introduce a practical application, in which the MILP is used to iteratively recompute plans (both in a centralized and decentralized manner) in order to adapt to dynamic and uncertain environments.

Gschwind Timo, Johannes Gutenberg University Mainz

Dynamic Dual Optimal Inequalities for Cutting Stock and Bin Packing

One successful method for solving the cutting stock (CS) and bin packing problem (BP) is branch-and-price. The column generation master program is a set covering problem where columns correspond to feasibly filled bins that cover a subset of the items. It is known that standard column generation suffers from slow convergence (tailing off). For CS, valid inequalities on the dual prices of the covering constraints, so-called dual optimal inequalities, were identified to be helpful to mitigate the tailing off effect. Our presentation addresses three issues: First, the standard approach is the a priori construction of dual optimal inequalities before solving the master program. We show that the most violated inequalities can be easily identified in the column generation process and so be added dynamically. For standard benchmark problems, computation times were approximately halved. Second, for BP not all CS inequalities are dual optimal, i.e., fulfilled by at least one optimal solution of the LP-relaxation of the master program. We present a way to handle these cases and to reconstruct primal feasible solutions needed in the branch-and-bound process. Third, we generalize our results to the BP with conflicts.

Maua Denis, IDSIA

Modeling and Planning with Highly non-Markovian Influence Diagrams

Influence diagrams (IDs) bring together graph theory and decision theory to provide an intuitive and concise representation of structured decision-making problems. From the modeling viewpoint, IDs provide a rich language that allows the specification of uncertainty, preferences, and sequential and parallel decision-making. From the algorithmic viewpoint, the main challenge is to devise efficient methods for optimal planning with such models, that is, to prescribe a combination of rules mapping states of the world into actions that maximizes expected utility. When the problem is highly non-Markovian, standard approaches based on dynamic programming often perform poorly. An alternative is to cast the planning problem as a mixed-integer linear program. Such an alternative, however, scales poorly even for simple models. Yet another alternative is the use of greedy methods that scale well to large problems but provide no quality guarantees. An interesting balance is obtained by anytime algorithms that allow for a trade-off between efficiency and accuracy. In this talk, we give a short introduction to influence diagrams, discuss the (theoretical and practical) complexity of planning with such models, and review state-of-the-art methods for planning in the highly non-Markovian case.

Respen Jean, University of Geneva

A complex multi-objective production problem: from exact methods to advanced metaheuristics

Multi-objective scheduling problems are commonly faced by decision-makers, who need to take a decision at the right moment considering multiple objectives. In this context, we propose a multi-objective scheduling problem based on non-identical parallel-machines. Makespan, setup costs and times, as well as smoothing issues are considered, and eligibility constraints have to be fulfilled. To tackle this complex problem, we propose an exact method for small instances, as well as different metaheuristics (e.g., GRASP, tabu search, adaptive memory techniques) for large instances. We show that our algorithms are fast, efficient, and robust, even for big instances where exact methods cannot be considered. Current results for the considered problems are presented and future works conclude the presentation.

Robenek Tomas, TRANSP-OR, EPFL

A branch-and-price algorithm to solve the integrated berth allocation and yard assignment problem in bulk ports

In this research, two crucial optimization problems of berth allocation and yard assignment in the context of bulk ports are studied. We discuss how these problems are interrelated and can be combined and solved as a single large scale optimization problem. More importantly we emphasize the differences in operations between bulk ports and container terminals which emphasizes the need to devise specific solutions for bulk ports. The objective is to minimize the total service time of vessels berthing at the port. We propose an exact solution algorithm based on branch and price framework to solve the integrated problem. In the proposed model, the master problem is formulated as a set-partitioning problem, and subproblems to identify columns with negative reduced costs are solved using mixed integer programming. The proposed algorithm is tested and validated through numerical experiments based on instances inspired from real bulk port data. The results indicate that the algorithm can be successfully used to solve instances containing up to 40 vessels within reasonable computational time.

Umang Nitish, EPFL, TRANSP-OR

Reactive methods to solve the berth allocation problem with stochastic arrival and handling times

In this research we study the dynamic, hybrid berth allocation problem (BAP) for bulk ports in real time as disruptions occur. In practice, the actual arrival times and handling times of the vessels deviate from their expected values, which can disrupt the original berthing plan and possibly make it infeasible. We consider a given baseline berthing schedule, and solve the BAP in real time as actual data is revealed in real time. The objective is to minimize the total realized costs of the updated berthing schedule. To model the uncertainty in the data, the arrival times of the vessels are assumed to be uniformly distributed around a nominal expected value, while the vessel handling times are assumed to be distributed according to a truncated exponential distribution. We present an optimization based recovery algorithm based on set partitioning method and a smart greedy algorithm to reassign the vessels in events of disruptions. A simulation studies is carried out to assess the solution performance and efficiency of the proposed algorithms. Results indicate that the proposed algorithms can significantly reduce the total realized costs of the berthing schedule as compared to the ongoing practice of reassigning vessels at the port.