Search

Appointment scheduling problems under uncertainty encounter a fundamental trade-off between cost minimization and customer waiting times. Most existing studies address this trade-off using a weighted sum approach, which puts little emphasis on individual waiting times and, thus, customer satisfaction. In contrast, we study how to minimize total cost while providing waiting time guarantees to all customers. Given box uncertainty sets for service times and no-shows, we introduce the Robust Appointment Scheduling Problem with Waiting Time Guarantees. We show that the problem is NP-hard in general and introduce a mixed-integer linear program that can be solved in reasonable computation time. For special cases, we prove that polynomial-time variants of the well-known Smallest-Variance-First sequencing rule and the Bailey-Welch scheduling rule are optimal. Furthermore, a case study with data from the radiology department of a large university hospital demonstrates that the approach not only guarantees acceptable waiting times but, compared to existing robust approaches, may simultaneously reduce costs incurred by idle time and overtime. This work suggests that limiting instead of minimizing customer waiting times is a win-win solution in the trade-off between customer satisfaction and cost minimization. Additionally, it provides an easy-to-implement and customizable appointment scheduling framework with waiting time guarantees.

We prove that a maintenance problem on frequency-constrained maintenance jobs with a hierarchical structure is integer-factorization hard. This result holds even on simple systems with just two components to maintain. As a corollary, we provide a first hardness result for Levi et al.'s modular maintenance scheduling problem (Naval Research Logistics 61, 472-488, 2014).

We advance the theoretical study of $\{0, 1/2\}$-cuts for integer programming problems $\max\{c^T x \colon A x \leq b, x \text{ integer}\}$. Such cuts are Gomory-Chv\'atal cuts that only need multipliers of value $0$ or $1/2$ in their derivation. The intersection of all $\{0, 1/2\}$-cuts derived from $Ax \le b$ is denoted by $P_{1/2}$ and called the $\{0,1/2\}$-closure of $P = \{x : Ax \le b\}$. The primal separation problem for $\{0, 1/2\}$-cuts is: Given a vertex $\hat x$ of the integer hull of $P$ and some fractional point $x^* \in P$, does there exist a $\{0,1/2\}$-cut that is tight at $\hat x$ and violated by $x^*$? Primal separation is the key ingredient of primal cutting-plane approaches to integer programming. In general, primal separation for $\{0,1/2\}$-cuts is NP-hard. We present two cases for which primal separation is solvable in polynomial time. As an interesting side product, we obtain a(nother) simple proof that matching can be solved in polynomial time. Furthermore, since optimization over the Gomory-Chv\'atal closure is also NP-hard, there has been recent research on solving the optimization problem over the Gomory-Chv\'atal closure approximately. In a similar spirit, we show that the optimization problem over the $\{0,1/2\}$-closure can be solved in polynomial time up to a factor $(1 + \varepsilon)$, for any fixed $\varepsilon > 0$., Comment: 14 pages

The $\{0,\frac{1}{2}\}$-closure of a rational polyhedron $\{ x \colon Ax \le b \}$ is obtained by adding all Gomory-Chv\'atal cuts that can be derived from the linear system $Ax \le b$ using multipliers in $\{0,\frac{1}{2}\}$. We show that deciding whether the $\{0,\frac{1}{2}\}$-closure coincides with the integer hull is strongly NP-hard. A direct consequence of our proof is that, testing whether the linear description of the $\{0,\frac{1}{2}\}$-closure derived from $Ax \le b$ is totally dual integral, is strongly NP-hard., Comment: 7 pages

We introduce a simple, accurate, and extremely efficient method for numerically solving the multi-marginal optimal transport (MMOT) problems arising in density functional theory. The method relies on (i) the sparsity of optimal plans [for $N$ marginals discretized by $\ell$ gridpoints each, general Kantorovich plans require $\ell^N$ gridpoints but the support of optimizers is of size $O(\ell\cdot N)$ [FV18]], (ii) the method of column generation (CG) from discrete optimization which to our knowledge has not hitherto been used in MMOT, and (iii) ideas from machine learning. The well-known bottleneck in CG consists in generating new candidate columns efficiently; we prove that in our context, finding the best new column is an NP-complete problem. To overcome this bottleneck we use a genetic learning method tailormade for MMOT in which the dual state within CG plays the role of an "adversary", in loose similarity to Wasserstein GANs. On a sequence of benchmark problems with up to 120 gridpoints and up to 30 marginals, our method always found the exact optimizers. Moreover, empirically the number of computational steps needed to find them appears to scale only polynomially when both $N$ and $\ell$ are simultaneously increased (while keeping their ratio fixed to mimic a thermodynamic limit of the particle system).

Distribution networks with periodically repeating events often hold great promise to exploit economies of scale. Joint replenishment problems are a fundamental model in inventory management, manufacturing, and logistics that capture these effects. However, finding an efficient algorithm that optimally solves these models, or showing that none may exist, has long been open, regardless of whether empty joint orders are possible or not. In either case, we show that finding optimal solutions to joint replenishment instances with just two products is at least as difficult as integer factorization. To the best of the authors' knowledge, this is the first time that integer factorization is used to explain the computational hardness of any kind of optimization problem. Under the assumption that Riemann's Hypothesis is correct, we can actually prove that the two-item joint replenishment problem with possibly empty joint ordering points is NP-complete under randomized reductions, which implies that not even quantum computers may be able to solve it efficiently. By relating the computational complexity of joint replenishment to cryptography, prime decomposition, and other aspects of prime numbers, a similar approach may help to establish (integer factorization) hardness of additional open periodic problems in supply chain management and beyond, whose solution has eluded standard methods., Comment: 20 pages, 4 figures

We consider single-machine scheduling problems that are natural generalizations or variations of the min-sum set cover problem and the min-sum vertex cover problem. For each of these problems, we give new approximation algorithms. Some of these algorithms rely on time-indexed LP relaxations. We show how a variant of alpha-point scheduling leads to the best-known approximation ratios, including a guarantee of 4 for an interesting special case of the so-called generalized min-sum set cover problem. We also make explicit the connection between the greedy algorithm for min-sum set cover and the concept of Sidney decomposition for precedence-constrained single-machine scheduling, and show how this leads to a 4-approximation algorithm for single-machine scheduling with so-called bipartite OR-precedence constraints.

Simple intersections between one-dimensional channels can act as coherent beam splitters for non-interacting electrons. Here we examine how coherent splitting at such intersections is affected by inter-particle interactions, in the special case of an intersection of topological edge states. We derive an effective impurity model which represents the edge-state intersection within Luttinger liquid theory at low energy. For Luttinger K = 1 / 2 , we compute the exact time-dependent expectation values of the charge density as well as the density-density correlation functions. In general a single incoming charge density wave packet will split into four outgoing wave packets with transmission and reflection coefficients depending on the strengths of the tunnelling processes between the wires at the junction. We find that when multiple charge density wave packets from different directions pass through the intersection at the same time, reflection and splitting of the packets depend on the relative phases of the waves. Active use of this phase-dependent splitting of wave packets may make Luttinger interferometry possible. We also find that coherent incident packets generally suffer partial decoherence from the intersection, with some of their initially coherent signal being transferred into correlated quantum noise. In an extreme case four incident coherent wave packets can be transformed entirely into density-density correlations, with the charge density itself having zero expectation value everywhere in the final state.

We present a deterministic polynomial-time algorithm for computing $d^{d+o(d)}$-approximate (pure) Nash equilibria in (proportional sharing) weighted congestion games with polynomial cost functions of degree at most $d$. This is an exponential improvement of the approximation factor with respect to the previously best deterministic algorithm. An appealing additional feature of the algorithm is that it only uses best-improvement steps in the actual game, as opposed to the previously best algorithms, that first had to transform the game itself. Our algorithm is an adaptation of the seminal algorithm by Caragiannis et al. [FOCS'11, TEAC 2015], but we utilize an approximate potential function directly on the original game instead of an exact one on a modified game. A critical component of our analysis, which is of independent interest, is the derivation of a novel bound of $[d/\mathcal{W}(d/\rho)]^{d+1}$ for the Price of Anarchy (PoA) of $\rho$-approximate equilibria in weighted congestion games, where $\mathcal{W}$ is the Lambert-W function. More specifically, we show that this PoA is exactly equal to $\Phi_{d,\rho}^{d+1}$, where $\Phi_{d,\rho}$ is the unique positive solution of the equation $\rho (x+1)^d=x^{d+1}$. Our upper bound is derived via a smoothness-like argument, and thus holds even for mixed Nash and correlated equilibria, while our lower bound is simple enough to apply even to singleton congestion games., Comment: To be published in Mathematics of Operations Research