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
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
Lower bounds on minimization problems are essential for convergence of both branching-based and iterative solution methods for optimization problems. They are also required for evaluating the quality of feasible solutions by providing conservative optimality gaps. We provide an analytical lower bound for a class of quadratic optimization problems with binary decision variables. In contrast to … Read more
This paper studies the problems of partitioning the vertices of a graph G = (V,E) into (or covering with) a minimum number of low-diameter clusters from the lenses of approximation algorithms and integer programming. Here, the low-diameter criterion is formalized by an s-club, which is a subset of vertices whose induced subgraph has diameter at … Read more
We present column elimination as a general framework for solving (large-scale) integer programming problems. In this framework, solutions are represented compactly as paths in a directed acyclic graph. Column elimination starts with a relaxed representation, that may contain infeasible paths, and solves a constrained network flow over the graph to find a solution. It then … Read more
University students benefit academically, personally and professionally from an expansion of their in-class social network. To facilitate this, we present a novel and broadly applicable optimization approach that exposes individuals to as many as possible peers that they do not know. This novel class of ‘social seating assignment problems’ is parameterized by the social network, … Read more
This tutorial provides an introduction to the use of decision diagrams for solving discrete optimization problems. A decision diagram is a graphical representation of the solution space, representing decisions sequentially as paths from a root node to a target node. By merging isomorphic subgraphs (or equivalent subproblems), decision diagrams can compactly represent an exponential solution … Read more
The most successful approaches for the TSP use the integer programming model proposed in 1954 by Dantzig, Fulkerson, and Johnson (DFJ). Although this model has exponentially many subtour elimination constraints (SECs), it has been observed that relatively few of them are needed to prove optimality in practice. This leads us to wonder: What is the … Read more
This paper is devoted to the Truck-to-dock Door Assignment Problem. Two integer programming formulations introduced after 2009 are examined. Our review of the literature takes note of the criticisms and limitations addressed to the seminal work of 2009. Although the published adjustments that followed present strong argument and technical background, we have identified several errors, … Read more
We introduce the prime programming problem as a subclass of integer programming. These optimization models impose the restriction of feasible solutions being prime numbers. Then, we demonstrate how several classical problems in number theory can be formulated as prime programs. To solve such problems with a commercial optimization solver, we extend the branch-and-bound procedure of … Read more