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 SCIP Optimization Suite 10.0. The updates in SCIP 10.0 include a new solving mode for exactly solving rational mixed-integer linear programs, a new presolver … Read more
The generalized flow problem deals with flows through a network with losses or gains along the arcs. Motivated by energy networks, this paper concentrates on the case with losses along cycles. Such networks can become extremely large, mostly because they are considered over large time horizons. We therefore develop a column generation approach for a … Read more
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
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
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
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
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
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 variable to produce new columns. Therefore, when we want to solve a slightly perturbated problem in which the block-angular structure is preserved … Read more
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
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