Mathematical models for the kidney exchange problem with reserve arcs

The kidney exchange problem with reserve arcs (KEP-RA) is an extension of the classical kidney exchange problem in which one is allowed to select in the solution a limited number of arcs that do not belong to the compatibility graph. This problem is motivated by recent breakthroughs in the field of kidney transplantation involving immunosuppressants … Read more

Descent Scheme for a Class of Bilevel Programming Problems

In this paper, a class of bilevel programming problems is studied, in which the lower level is a quadratic programming problem, and the upper level problem consists of a nonlinear objective function with coupling constraints. An iterative process is developed to generate a sequence of points, which converges to the solution of this problem. In … Read more

A Single-Level Reformulation of Integer Bilevel Programs using Decision Diagrams

Integer bilevel programs are notoriously difficult to solve due to the absence of strong and efficiently computable relaxations. In this work, we introduce a novel single-level reformulation of these programs by leveraging a network flow-based representation of the follower’s value function, utilizing decision diagrams and linear programming duality. This approach enables the development of scalable … Read more

Stable Set Polytopes with Rank |V(G)|/3 for the Lovász-Schrijver SDP Operator

We study the lift-and-project rank of the stable set polytope of graphs with respect to the Lovász–Schrijver SDP operator \( \text{LS}_+ \) applied to the fractional stable set polytope. In particular, we show that for every positive integer \( \ell \), the smallest possible graph with \( \text{LS}_+ \)-rank \( \ell \) contains \( 3\ell … Read more

Improved Approximation Algorithms for Low-Rank Problems Using Semidefinite Optimization

Inspired by the impact of the Goemans-Williamson algorithm on combinatorial optimization, we construct an analogous relax-then-sample strategy for low-rank optimization problems. First, for orthogonally constrained quadratic optimization problems, we derive a semidefinite relaxation and a randomized rounding scheme, which obtains provably near-optimal solutions, mimicking the blueprint from Goemans and Williamson for the Max-Cut problem. We … Read more

Insights into the computational complexity of the single-source capacitated facility location problem with customer preferences

Single-source capacitated facility location problems (SSCFLPs) are well known in the operations research literature. A set of facilities is opened and each customer is assigned to exactly one open facility so that the capacity at each facility is respected. This customer assignment, however, deprives customers from choosing facilities according to their individual preferences. If customers … Read more

The Edge-based Contiguous p-median Problem with Connections to Logistics Districting

This paper introduces the edge-based contiguous p-median (ECpM) problem to partition the roads in a network into a given number of compact and contiguous territories. Two binary programming models are introduced, both of which incorporate a network distance. The first model requires an exponential number of cut set-based constraints to model contiguity; it is paired … Read more

Polynomial-Time Algorithms for Setting Tight Big-M Coefficients in Transmission Expansion Planning with Disconnected Buses

The increasing penetration of renewable energy into power systems necessitates the development of effective methodologies to integrate initially disconnected generation sources into the grid. This paper introduces the Longest Shortest-Path-Connection (LSPC) algorithm, a graph-based method to enhance the mixed-integer linear programming disjunctive formulation of Transmission Expansion Planning (TEP) using valid inequalities (VIs). Traditional approaches for … Read more

A Generalized Voting Game for Categorical Network Choices

This paper presents a game-theoretical framework for data classification and network discovery, focusing on pairwise influences in multivariate choices. The framework consists of two complementary games in which individuals, connected through a signed weighted graph, exhibit network similarity. A voting rule captures the influence of an individual’s neighbors, categorized as attractive (friend-like) or repulsive (enemy-like), … Read more

On parametric formulations for the Asymmetric Traveling Salesman Problem

The traveling salesman problem is a widely studied classical combinatorial problem for which there are several integer linear formulations. In this work, we consider the Miller-Tucker-Zemlin (MTZ), Desrochers-Laporte (DL) and Single Commodity Flow (SCF) formulations. We argue that the choice of some parameters of these formulations is arbitrary and, therefore, there are families of formulations … Read more