Integer Programming

Coordinate Optimality Reformulation for Mixed-Integer Convex Programs with Indicators

Categories (Mixed) Integer Nonlinear Programming, Quadratic Programming Tags , ,

We consider mixed-integer convex optimization problems in which binary indicators control continuous variables. We introduce the Coordinate Optimality Reformulation (CORe) framework, which augments standard indicator formulations by incorporating coordinate-wise optimality information. The resulting reformulations preserve global optimality while substantially improving branch-and-bound performance, particularly in sparse and structured settings where the coordinate-wise optimality conditions expose exploitable … Read more

An Exact Branch-and-Cut Method for the Asymmetric Orienteering Problem with Terrain-Driven Fatigue

Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Transportation

We present an end-to-end computational framework for provably optimal route planning in orienteering races on real terrain. The framework consists of a GIS pipeline that combines International Orienteering Federation (IOF) map symbols, a digital elevation model (DEM), and the Minetti metabolic model into a fully asymmetric cost matrix, where directional slope costs and cumulative fatigue … 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

Beyond Hand-Derived Inequalities: Decision Diagrams for Cut Generation in Binary Polynomial Optimization

Categories 0-1 Programming, Cutting Plane Approaches, Integer Programming Tags , ,

We study cutting-plane generation for binary polynomial optimization (BPO), whose feasible region is the multilinear set of a hypergraph. Strong inequalities for this set—such as two-links, flowers, and odd $\beta$-cycles—are classically hand-derived for fixed support patterns. Instead, we propose a decision-diagram (DD) approach: for any chosen support, it separates a facet-defining cut in the local … 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

A Numerically-safe Branch-Price-and-Cut Algorithm for the Length-Constrained Cycle Partition Problem

Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Dynamic Programming 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

Integrating Power Profile Optimization with Timetabling for Underground Train Networks

Categories (Mixed) Integer Linear Programming, Polyhedra, Transportation Tags , , ,

We study energy-efficient operation of underground train networks, where energy from regenerative braking is usable only if another train in the same electrically isolated subnetwork accelerates simultaneously. Timetabling models for this setting typically fix one velocity profile per leg and running time, which limits the matching of braking and accelerating phases. We drop this assumption … Read more

Optimal Combinatorial Testing with Constraints: The Balancing Act

Categories (Mixed) Integer Linear Programming, Applications - Science and Engineering, Graphs and Matroids

Imagine that you are in front of a cockpit with several on–off buttons. If you were to thoroughly test it, you would need to try a prohibitive number of configurations. But since most bugs in practice can be isolated to interactions among few components, having tests that cover every possible pairwise configuration is a good … Read more

PaNGEA: Parallel Node Generation and Exploration Algorithm on GPU

Categories (Mixed) Integer Linear Programming, Integer Programming Tags ,

Primal heuristics for finding high-quality feasible solutions are an important component in mixed-integer optimization (MIO) solvers. Recent advances in GPU-accelerated optimization algorithms show the potential of GPU acceleration for continuous optimization. In this paper, we introduce the Parallel Node Generation and Exploration Algorithm (PaNGEA), a GPU-friendly MIO primal heuristic. PaNGEA explores restricted subproblems by combining … Read more

Route `Em and Count `Em: A Two-Stage Stochastic Programming Model for Anti-Submarine Operations

Categories (Mixed) Integer Linear Programming, Stochastic Programming, Transportation Tags , , ,

Tracking targets in undersea warfare requires successful detection by an active search asset. Maximizing detection likelihood requires strategic placement and routing of the search assets in the search region over the planning horizon. We develop a two-stage stochastic integer programming model that maximizes the expected total reward for target detections under uncertainty in target motion … Read more