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
Motivated by our collaboration with a residency program at an academic health system, we propose new integer programming (IP) approaches for the resident-to-rotation assignment problem (RRAP). Given sets of residents, resident classes, and departments, as well as a block structure for each class, staffing needs, rotation requirements for each class, program rules, and resident vacation … Read more
We analyze the inverse of the Gomory corner relaxation (GCR) of a pure integer program (IP). We prove the inverse GCR is equivalent to the inverse of a shortest path problem, yielding a polyhedral representation of the GCR inverse-feasible region. We present a linear programming (LP) formulation for solving the inverse GCR under the \(L_{1}\) … Read more
We consider the chance-constrained program (CCP) with random right-hand side under a finite discrete distribution. It is known that the standard mixed integer linear programming (MILP) reformulation of the CCP is generally difficult to solve by general-purpose solvers as the branch-and-cut search trees are enormously large, partly due to the weak linear programming relaxation. In … Read more
ArticleDownload View PDF
Inspired by its occurrence as a substructure in a stochastic railway timetabling model, we study in this work a special case of the bipartite boolean quadric polytope. It models conditional relations across three sets of binary variables, where selections within two implying sets imply a choice in a corresponding implied set. We call this polytope … Read more