Integer Programming

A Decision-Support Framework for Structuring and Reducing Large Multi-Objective Solution Sets via Clustering: An Application to Proton Therapy

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

This paper proposes a four-stage decision-support framework for structuring and reducing large multi-objective solution sets into compact and interpretable collections of representative alternatives. The methodology combines: (Phase 1) systematic solution generation through extended goal programming and structured preference exploration; (Phase 2) robustness-aware enrichment and profiling under weight sensitivity analysis; (Phase 3) filtering and dominance-based reduction … Read more

Congressional Apportionment

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

This book chapter is a gentle introduction to the mathematics of congressional apportionment. It emphasizes the connections between mathematical optimization and the classical apportionment methods (e.g., Jefferson, Adams, Hamilton, Webster, Huntington-Hill, Dean). CitationPrepared for a forthcoming book edited by Bruce Golden and Doug ShierArticleDownload View PDF

Indicator Cuts for Benders Decomposition with Mixed-Integer Subproblems

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

Classical Benders decomposition fails when the subproblem is a mixed-integer program, due to the absence of strong duality. We propose a novel class of dual-free indicator cuts that are applicable to all Benders-decomposable problems with a pure-integer master problem and mixed-integer linear programming (MILP) subproblems. These cuts are derived from the monotonicity property of the … Read more

Generalizing single-level relaxations for bilevel linear programs

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

We consider a broad class of bilevel linear programs in which the follower’s decisions are all continuous, while the leader’s decisions may include integrality restrictions. Solving such problems to optimality is known to be NP-hard. A classical approach in bilevel optimization for constructing lower and upper bounds is based on a single-level relaxation, in which … Read more

Rational Jacobi Rotations and the Complexity of Approximating Mixed Integer Quadratic Programming

Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Quadratic Programming Tags , , , ,

We present an algorithm that finds an epsilon-approximate solution to a mixed integer quadratic programming (MIQP) problem, and that runs on a Turing machine in time polynomial in the size of the instance and in 1/epsilon, provided that the number of integer variables and the number of negative eigenvalues of the Hessian of the objective … Read more

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

Optimal Route Planning for Orienteering: Branch-and-Cut with Terrain Cost Surfaces and Fatigue

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

We address the problem of optimal route planning for competitive orien- teering on real terrain. A Geographic Information System (GIS) pipeline transforms orienteering map data and digital terrain models into a fully asymmetric cost matrix that captures directional slope costs (via the Minetti metabolic model) and cumulative athlete fatigue. The resulting problem, the Asymmetric Orienteering … 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