column generation

Behaviorally Informed Planning for Retrofitting, Sheltering, and Mixed-Mode Evacuation in Urban Tsunami Preparedness: Toward a Tsunami-Resilient Istanbul

Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Transportation Tags , , , , ,

Tsunamis, primarily triggered by earthquakes, pose critical threats to coastal populations due to their rapid onset and limited evacuation time. Two main protective actions exist: sheltering in place, which requires substantial retrofitting investments, and evacuation, which is often hindered by congestion, mixed travel modes, and tight inundation times. Given pedestrians’ slower movement and restricted evacuation … Read more

A two-stage optimization approach for selecting electric-flight airports

Categories Applications - OR and Management Sciences, Transportation Tags , , , ,

The decarbonization of short-haul air transport has gained increasing attention, with electric aircraft emerging as a promising alternative to conventional short-haul aviation. However, given the substantial investment anticipated for the necessary infrastructure, a strategic and globally coordinated selection of airports is imperative. The aim of this paper is to address this problem and determine the … Read more

Integrated Schedule Planning for Regional Airlines Using Column Generation

Categories (Mixed) Integer Linear Programming, Airline Optimization, Combinatorial Optimization Tags , , , ,

Problem definition: More than one-third of US domestic flights are operated by regional airlines. This paper focuses on optimizing medium-term schedule planning decisions for a network of regional airlines through the joint optimization of frequency planning, timetable development, fleet assignment, and some limited aspects of route planning, while capturing passengers’ travel decisions through a general … Read more

Column Elimination: An Iterative Approach to Solving Integer Programs

Categories Branch and Cut Algorithms, Dynamic Programming, Integer Programming Tags , , , , ,

We present column elimination as a general framework for solving (large-scale) integer programming problems. In this framework, solutions are represented compactly as paths in a directed acyclic graph. Column elimination starts with a relaxed representation, that may contain infeasible paths, and solves a constrained network flow over the graph to find a solution. It then … Read more

Combinatorial Robust Optimization with Decision-Dependent Information Discovery and Polyhedral Uncertainty

Categories Combinatorial Optimization, Robust Optimization Tags , , ,

Given a nominal combinatorial optimization problem, we consider a robust two-stages variant with polyhedral cost uncertainty, called Decision-Dependent Information Discovery (DDID). In the first stage, DDID selects a subset of uncertain cost coefficients to be observed, and in the second-stage, DDID selects a solution to the nominal problem, where the remaining cost coefficients are still … Read more

Sensitivity Analysis in Dantzig-Wolfe Decomposition

Categories Linear Programming Tags , , ,

Dantzig-Wolfe decomposition is a well-known classical method for solving huge linear optimization problems with a block-angular structure. The most computationally expensive process in the method is pricing: solving block subproblems for a dual solution to produce new columns. Hence, when solving a slightly perturbated problem in which the block-angular structure is preserved, the method’s speed … Read more

The SCIP Optimization Suite 9.0

Categories Integer Programming, Linear, Cone and Semidefinite Programming, Optimization Software and Modeling Systems Tags , , , , , , , , ,

The SCIP Optimization Suite provides a collection of software packages for mathematical optimization, centered around the constraint integer programming (CIP) framework SCIP. This report discusses the enhancements and extensions included in the SCIP Optimization Suite 9.0. The updates in SCIP 9.0 include improved symmetry handling, additions and improvements of nonlinear handlers and primal heuristics, a … Read more

Branch and Price for the Length-Constrained Cycle Partition Problem

Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Transportation Tags , , , ,

The length-constrained cycle partition problem (LCCP) is a graph optimization problem in which a set of nodes must be partitioned into a minimum number of cycles. Every node is associated with a critical time and the length of every cycle must not exceed the critical time of any node in the cycle. We formulate LCCP … Read more

Crew Scheduling and Routing Problem in Road Restoration via Branch-and-Price Algorithms

Categories Applications - OR and Management Sciences, Transportation Tags , , , ,

This paper addresses the single crew scheduling and routing problem in the context of road network repair and restoration, which is critical in assisting complex post-disaster decisions in humanitarian logistics settings. We present three novel formulations for this problem, which are the first suitable for column generation and branch-and-price (BP) algorithms. Specifically, our first formulation … Read more

Integrating Public Transport in Sustainable Last-Mile Delivery: Column Generation Approaches

Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Production and Logistics Tags , , , ,

We tackle the problem of coordinating a three-echelon last-mile delivery system. In the first echelon, trucks transport parcels from distribution centres outside the city to public transport stops. In the second echelon, the parcels move on public transport and reach the city centre. In the third echelon, zero-emission vehicles pick up the parcels at public … Read more