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
Section 2 of the Voting Rights Act (VRA) prohibits voting practices that minimize or cancel out minority voting strength. While this section provides no clear framework for avoiding minority vote dilution and creating minority-majority districts, the Supreme Court proposed the Gingles test in the 1986 case Thornberg v Gingles. The Gingles test provides three conditions … Read more
In this paper, we address an extension of the classical two-dimensional bin packing (2BPP) that considers the spread of customer orders (2BPP-OS). The 2BPP-OS addresses a set of rectangular items, required from different customer orders, to be cut from a set of rectangular bins. All the items of a customer order are dispatched together to … Read more
A generalization of Ripà’s square spiral solution for the n × n × ··· × n Points Upper Bound Problem. Additionally, we provide a non-trivial lower bound for the k-dimensional n_1 × n_2 × ··· × n_k Points Problem. In this way, we can build a range in which, with certainty, all the best possible … Read more
Given a \(\{0,1\}\)-matrix \(M\), the graph realization problem for \(M\) asks if there exists a spanning forest such that the columns of \(M\) are incidence vectors of paths in the forest. The problem is closely related to the recognition of network matrices, which are a large subclass of totally unimodular matrices and have many applications … Read more
This paper studies the problem of learning Bayesian networks from continuous observational data, generated according to a linear Gaussian structural equation model. We consider an \(\ell_0\)-penalized maximum likelihood estimator for this problem which is known to have favorable statistical properties but is computationally challenging to solve, especially for medium-sized Bayesian networks. We propose a new … Read more
We present a probabilistic model for stochastic iterative algorithms with the use case of optimization algorithms in mind. Based on this model, we present PAC-Bayesian generalization bounds for functions that are defined on the trajectory of the learned algorithm, for example, the expected (non-asymptotic) convergence rate and the expected time to reach the stopping criterion. … Read more
We consider a two-stage stochastic decision problem where the decision-maker has the opportunity to obtain information about the distribution of the random variables $\xi$ that appear in the problem through a set of discrete actions that we refer to as probing. Probing components of a random vector $\eta$ that is jointly-distributed with $\xi$ allows the … Read more
In this paper, we propose a novel double-proximal augmented Lagrangian method(DP-ALM) for solving a family of linearly constrained convex minimization problems whose objective function is not necessarily smooth. This DP-ALM not only enjoys a flexible dual stepsize, but also contains a proximal subproblem with relatively smaller proximal parameter. By a new prediction-correction reformulation for this … Read more
We derive analytic formulas for the alternating projection method applied to the cone \(S^n_+\) of positive semidefinite matrices and an affine subspace. More precisely, we find recursive relations on parameters representing a sequence constructed by the alternating projection method. By applying these formulas, we analyze the alternating projection method in detail and show that the … Read more