A Branch and Price Algorithm for Scheduling in Surgery Pre-admission Testing Clinics

A Surgery Pre-Admission Testing (PAT) clinic is a hospital unit designed to serve pre-operative patients by gathering critical patient information and performing procedure-specific tests to prepare them for surgery. Patients may require multiple tests, each conducted by a specialized nurse. A patient must be assigned to a room before starting any test and must stay … Read more

Towards Optimal Offline Reinforcement Learning

We study offline reinforcement learning problems with a long-run average reward objective. The state-action pairs generated by any fixed behavioral policy thus follow a Markov chain, and the empirical state-action-next-state distribution satisfies a large deviations principle. We use the rate function of this large deviations principle to construct an uncertainty set for the unknown true … Read more

Integer Control Approximations for Graphon Dynamical Systems

Graphons generalize graphs and define a limit object of a converging graph sequence. The notion of graphons allows for a generic representation of coupled network dynamical systems. We are interested in approximating optimal switching controls for graphon dynamical systems. To this end, we apply a decomposition approach comprised of a relaxation and a reconstruction step. … Read more

A Rank-One-Update Method for the Training of Support Vector Machines

This paper considers convex quadratic programs associated with the training of support vector machines (SVM). Exploiting the special structure of the SVM problem a new type of active set method with long cycles and stable rank-one-updates is proposed and tested (CMU: cycling method with updates). The structure of the problem allows for a repeated simple … Read more

A Universally Optimal Primal-Dual Method for Minimizing Heterogeneous Compositions

This paper proposes a universal, optimal algorithm for convex minimization problems of the composite form $g_0(x)+h(g_1(x),\dots, g_m(x)) + u(x)$. We allow each $g_j$ to independently range from being nonsmooth Lipschitz to smooth, from convex to strongly convex, described by notions of H\”older continuous gradients and uniform convexity. Note that, although the objective is built from … Read more

The uniqueness of Lyapunov rank among symmetric cones

The Lyapunov rank of a cone is the dimension of the Lie algebra of its automorphism group. It is invariant under linear isomorphism and in general not unique—two or more non-isomorphic cones can share the same Lyapunov rank. It is therefore not possible in general to identify cones using Lyapunov rank. But suppose we look … Read more

Optimal Experimental Design with Routing Constraints

Data collection in application domains like agriculture and environmental science requires the deployment of sensors in large remote areas. These use cases challenge the traditional optimal experimental design (OED) formulation from statistics by their scale as well as the presence of complex operational constraints, such as that data is collected along the trajectory of a … Read more

Risk-aware Logic-based Benders Decomposition for a Location-Allocation-Pricing Problem with Stochastic Price-Sensitive Demands

We consider a capacitated location-allocation-pricing problem in a single-commodity supply chain with stochastic price-sensitive demands, where the location, allocation and pricing decisions are made simultaneously. Under a general risk measure representing an arbitrary risk tolerance policy, the problem is modeled as a two-stage stochastic mixed-integer program with a translation-invariant monotone risk measure. To solve the … Read more

On Sum-Rules for Second-Order Contingent Derivatives

We are concerned with contingent derivatives and their second-order counterparts (introduced by Ngai et al.) of set-valued mappings. Special attention is given to the development of new sum-rules for second-order contingent derivatives. To be precise, we want to find conditions under which the second-order contingent derivative of the sum of a smooth and a set-valued … Read more

Analyzing the numerical correctness of branch-and-bound decisions for mixed-integer programming

Most state-of-the-art branch-and-bound solvers for mixed-integer linear programming rely on limited-precision floating-point arithmetic and use numerical tolerances when reasoning about feasibility and optimality during their search. While the practical success of floating-point MIP solvers bears witness to their overall numerical robustness, it is well-known that numerically challenging input can lead them to produce incorrect results. … Read more