Integer Programming

Anesthesiologist Scheduling with Handoffs: A Combined Approach of Optimization and Human Factors

Categories Integer Programming, Scheduling, Stochastic Programming

We present a two-stage stochastic programming model for optimizing anesthesiologist schedules, explicitly accounting for uncertainty in surgery durations and anesthesiologist handoffs. To inform model design, we conducted an online survey at our partner institution to identify key factors affecting the quality of intraoperative anesthesiologist handoffs. Insights from the survey results are incorporated into the model, … Read more

Optimal personnel scheduling in hospital pharmacies considering management and operators priorities

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

In this paper, we address the problem of allocating and scheduling employees for work shifts in the pharmacy sector of a private hospital. To tackle this issue, we introduce the pharmacy staff scheduling problem (PSSP) in the literature. To solve the problem, we propose a mixed-integer programming formulation that considers various aspects, such as the … Read more

Hic Sunt Dracones: The Structure of the Inverse-Feasible Region of a Multiobjective Integer Program

Categories Combinatorial Optimization, Integer Programming, Multi-Criteria Optimization Tags , ,

Optimization problems that involve multiple, conflicting criteria lead to a set of efficient solutions, and when there are discrete decisions, some solutions may be unsupported. Applications where it is difficult to estimate the parameters for criteria motivate inverse optimization techniques. We provide a theoretical analysis of the set of (unknown) objective parameters which lead to … Read more

A Randomized Algorithm for Sparse PCA based on the Basic SDP Relaxation

Categories (Mixed) Integer Linear Programming, Data Science Algorithms, Semi-definite Programming

Sparse Principal Component Analysis (SPCA) is a fundamental technique for dimensionality reduction, and is NP-hard. In this paper, we introduce a randomized approximation algorithm for SPCA, which is based on the basic SDP relaxation. Our algorithm has an approximation ratio of at most the sparsity constant with high probability, if called enough times. Under a … Read more

Implied Integrality in Mixed-Integer Optimization

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

Implied-integer detection is a well-known presolving technique that is used by many Mixed-Integer Linear Programming solvers. Informally, a variable is said to be implied integer if its integrality is enforced implicitly by integrality of other variables and the constraints of a problem. In this work we formalize the definition of implied integrality by taking a … Read more

Strength of the Upper Bounds for the Edge-Weighted Maximum Clique Problem

Categories Graphs and Matroids, Integer Programming Tags , ,

We theoretically and computationally compare the strength of the three main upper bounds from the literature on the optimal value of the Edge-Weighted Maximum Clique Problem (EWMCP). We provide a set of instances for which the ratio between any of the three upper bounds and the optimal value of the EWMCP is unbounded, showing that … Read more

Random-Restart Best-Response Dynamics for Large-Scale Integer Programming Games and Their Applications

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

This paper presents scalable algorithms for computing pure Nash equilibria (PNEs) in large-scale integer programming games (IPGs), where existing exact methods typically handle only small numbers of players. Motivated by a county-level aquatic invasive species (AIS) prevention problem with 84 decision makers, we develop and analyze random-restart best-response dynamics (RR-BRD), a randomized search framework for … Read more

A Dantzig-Wolfe Single-Level Reformulation for Mixed-Integer Linear Bilevel Optimization: Exact and Heuristic Approaches

Categories (Mixed) Integer Linear Programming, Bilevel Optimization, Branch and Cut Algorithms Tags , , , ,

Bilevel optimization problems arise in numerous real-world applications. While single-level reformulations are a common strategy for solving convex bilevel problems, such approaches usually fail when the follower’s problem includes integer variables. In this paper, we present the first single-level reformulation for mixed-integer linear bilevel optimization, which does not rely on the follower’s value function. Our … Read more

A relax-fix-and-exclude algorithm for an MINLP problem with multilinear interpolations

Categories (Mixed) Integer Nonlinear Programming, Chemical Engineering, Global Optimization Applications Tags , ,

This paper introduces a novel algorithm for Mixed-Integer Nonlinear Programming (MINLP) problems with multilinear interpolations of look-up tables. These problems arise when objectives or constraints contain black-box functions only known at a finite set of evaluations on a predefined grid. We derive a piecewise-linear relaxation for the multilinear interpolants, which require an MINLP formulation. Supported … Read more

Two-way Cutting-plane Algorithm for Best Subset Selection Considering Multicollinearity

Categories Global Optimization, Integer Programming, Optimization in Data Science Tags , , , ,

When linear dependence exists between some explanatory variables in a regression model, the estimates of regression coefficients become unstable, thereby making the interpretation of the estimation results unreliable. To eliminate such multicollinearity, we propose a high-performance method for selecting the best subset of explanatory variables for linear and logistic regression models. Specifically, we first derive … Read more