column generation

Non-contiguous satellite channel allocation under cumulative interference: A hybrid price-and-branch approach

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

We study a non-contiguous channelisation problem arising in multi-beam geostationary satellite communications. Carriers have heterogeneous sub- channel demands and priorities; carriers within the same beam cannot share a subchannel, while reuse across beams is permitted subject to carrier- specific cumulative-interference budgets. Demand may be partially satis- fied, with a priority-weighted objective favouring higher-priority tra!c when … Read more

A heuristic framework for a class of vehicle routing problems

Categories Combinatorial Optimization, Meta Heuristics, Transportation Tags , , ,

We propose GenericILS, a general-purpose heuristic framework for generating high-quality upper bounds for Vehicle Routing Problems whose pricing subproblems are modeled, in column-generation-based exact algorithms, as resource-constrained shortest path problems described through Resource Extension Functions (REFs), the standard device for encoding constraints in branch-and-price algorithms. GenericILS reuses REFs implemented for the exact method, without a … Read more

Unshackling Column Generation for Linearized Unconstrained Binary Quadratic Programs

Categories Integer Programming, Linear Programming, Nonlinear Optimization Tags , , ,

When linearizing binary quadratic programs, the most usual way is to replace bilinear products with additional variables constrained to take on consistent values in any feasible solution. In this setting, column generation is a principally desirable solution technique, for instance because the number of such additional linearization variables may be large while many of them … Read more

Case-Pack Allocation in Retail Distribution Networks

Categories Production and Logistics Tags , , , ,

Many retail distribution networks use a hierarchical structure in which regional distribution centers replenish local distribution centers that are closer to customers. In such networks, products are often shipped in large quantities, as case packs, cases or pallets, to the regional distribution center, whereas local distribution centers may require quantities at the individual-unit level. Case … Read more

Exact Branch-and-Price Algorithm for Live Operating Room Reoptimization

Categories (Mixed) Integer Linear Programming, Multi-Criteria Optimization, Scheduling Tags , , , ,

Live reoptimization of operating room schedules is required to cope with disruptions such as emergency arrivals and deviations in surgery durations under strict time limits. The resulting problem can be formulated as a large-scale Resource Constrained Project Scheduling Problem (RCPSP). While exact optimization methods are attractive in this context due to their ability to provide … Read more

Optimal Batching and In-Building Delivery Routing with Capacitated Residential Parcel Lockers

Categories Production and Logistics, Transportation Tags , , ,

Residential parcel lockers (RPLs), unlike their public counterparts, facilitate secure parcel delivery to occupants of private apartment and condominium buildings in urban areas. In this work, we consider the perspective of a last-mile parcel carrier that has access to an RPL in the lobby of a high-rise residential building. Motivated by growing e-commerce demand, we … Read more

Computing diverse solutions to optimization problems

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

Classical optimization methods determine a single optimal or near-optimal solution for a decision problem. In many applications, however, the decision maker is interested in evaluating a pool of high-quality solutions, to encode fairness-oriented criteria or to obtain a portfolio of alternatives to use in case of unexpected scenarios. In this paper, we consider the problem … Read more

Machine Learning–Enhanced Column Generation for Large-Scale Capacity Planning Problems

Categories (Mixed) Integer Linear Programming, Energy, Facility Planning and Design Tags , ,

Capacity Planning problems are a class of optimization problems used in diverse industries to improve resource allocation and make investment decisions. Solving real-world instances of these problems typically requires significant computational effort. To tackle this, we propose machine-learning-aided column generation methods for solving large-scale capacity planning problems. Our goal is to accelerate column generation by … Read more

Combinatorial Benders Decomposition and Column Generation for Optimal Box Selection

Categories Combinatorial Optimization, Cutting Plane Approaches, Transportation Tags , ,

We consider a two-stage optimization problem with sparsity constraints, motivated by a common challenge in packaging logistics: minimizing the volume of transported air by optimizing the size and number of available packaging boxes, given the demand for order items. In the first stage, we select the optimal dimensions of the boxes, while in the second … Read more

The SCIP Optimization Suite 10.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 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