We study the chanceconstrained bin packing problem, with an application to hospital operating room planning. The bin packing problem allocates items of random sizes that follow a discrete distribution to a set of bins with limited capacity, while minimizing the total cost. The bin capacity constraints are satisfied with a given probability. We investigate a bigM and a 01 bilinear formulation of this problem. We analyze the bilinear structure of the formulation and use the lifting techniques to identify cover, clique, and projection inequalities to strengthen the formulation. We show that in certain cases these inequalities are facetdefining for a bilinear knapsack constraint that arises in the reformulation. An extensive computational study is conducted for the operating room planning problem that minimizes the number of open operating rooms. The computational tests are performed using problems generated based on real data from a hospital. A lowerbound improvement heuristic is combined with the cuts proposed in this paper in a branchandcut framework. The computations illustrate that the techniques developed in this paper can significantly improve the performance of the branchandcut method. Problems with up to 1,000 scenarios are solved to optimality in less than an hour. A safe approximation based on conditionalmore »
This content will become publicly available on February 1, 2023
ALSOX and ALSOX+: Better Convex Approximations for Chance Constrained Programs
In a chance constrained program (CCP), decision makers seek the best decision whose probability of violating the uncertainty constraints is within the prespecified risk level. As a CCP is often nonconvex and is difficult to solve to optimality, much effort has been devoted to developing convex inner approximations for a CCP, among which the conditional valueatrisk (CVaR) has been known to be the best for more than a decade. This paper studies and generalizes the ALSOX, originally proposed by Ahmed, Luedtke, SOng, and Xie in 2017 , for solving a CCP. We first show that the ALSOX resembles a bilevel optimization, where the upperlevel problem is to find the best objective function value and enforce the feasibility of a CCP for a given decision from the lowerlevel problem, and the lowerlevel problem is to minimize the expectation of constraint violations subject to the upper bound of the objective function value provided by the upperlevel problem. This interpretation motivates us to prove that when uncertain constraints are convex in the decision variables, ALSOX always outperforms the CVaR approximation. We further show (i) sufficient conditions under which ALSOX can recover an optimal solution to a CCP; (ii) an equivalent bilinear programming formulation more »
 Award ID(s):
 2046426
 Publication Date:
 NSFPAR ID:
 10324120
 Journal Name:
 Operations Research
 ISSN:
 0030364X
 Sponsoring Org:
 National Science Foundation
More Like this


We develop a sparse image reconstruction method for Poissondistributed polychromatic Xray computed tomography (CT) measurements under the blind scenario where the material of the inspected object and the incident energy spectrum are unknown. We employ our massattenuation spectrum parameterization of the noiseless measurements for singlematerial objects and express the massattenuation spectrum as a linear combination of Bspline basis functions of order one. A block coordinatedescent algorithm is developed for constrained minimization of a penalized Poisson negative loglikelihood (NLL) cost function, where constraints and penalty terms ensure nonnegativity of the spline coefficients and nonnegativity and sparsity of the densitymap image; the image sparsity is imposed using a convex totalvariation (TV) norm penalty term. This algorithm alternates between a Nesterov’s proximalgradient (NPG) step for estimating the densitymap image and a limitedmemory BroydenFletcherGoldfarbShanno with box constraints (LBFGSB) step for estimating the incidentspectrum parameters. We establish conditions for biconvexity of the penalized NLL objective function, which, if satisfied, ensures monotonicity of the NPGBFGS iteration. We also show that the penalized NLL objective satisfies the KurdykaŁojasiewicz property, which is important for establishing local convergence of blockcoordinate descent schemes in biconvex optimization problems. Simulation examples demonstrate the performance of the proposed scheme.

We develop a framework for reconstructing images that are sparse in an appropriate transform domain from polychromatic computed tomography (CT) measurements under the blind scenario where the material of the inspected object and incidentenergy spectrum are unknown. Assuming that the object that we wish to reconstruct consists of a single material, we obtain a parsimonious measurementmodel parameterization by changing the integral variable from photon energy to mass attenuation, which allows us to combine the variations brought by the unknown incident spectrum and mass attenuation into a single unknown massattenuation spectrum function; the resulting measurement equation has the Laplaceintegral form. The massattenuation spectrum is then expanded into basis functions using B splines of order one. We consider a Poisson noise model and establish conditions for biconvexity of the corresponding negative loglikelihood (NLL) function with respect to the densitymap and massattenuation spectrum parameters. We derive a blockcoordinate descent algorithm for constrained minimization of a penalized NLL objective function, where penalty terms ensure nonnegativity of the massattenuation spline coefficients and nonnegativity and gradientmap sparsity of the densitymap image, imposed using a convex totalvariation (TV) norm; the resulting objective function is biconvex. This algorithm alternates between a Nesterov’s proximalgradient (NPG) step and a limitedmemorymore »

d. Many of the infrastructure sectors that are considered to be crucial by the Department of Homeland Security include networked systems (physical and temporal) that function to move some commodity like electricity, people, or even communication from one location of importance to another. The costs associated with these flows make up the price of the network’s normal functionality. These networks have limited capacities, which cause the marginal cost of a unit of flow across an edge to increase as congestion builds. In order to limit the expense of a network’s normal demand we aim to increase the resilience of the system and specifically the resilience of the arc capacities. Divisions of critical infrastructure have faced difficulties in recent years as inadequate resources have been available for needed upgrades and repairs. Without being able to determine future factors that cause damage both minor and extreme to the networks, officials must decide how to best allocate the limited funds now so that these essential systems can withstand the heavy weight of society’s reliance. We model these resource allocation decisions using a twostage stochastic program (SP) for the purpose of network protection. Starting with a general form for a basic twostage SP, wemore »

This work proposes a new algorithm – the Singletimescale Doublemomentum Stochastic Approximation (SUSTAIN) –for tackling stochastic unconstrained bilevel optimization problems. We focus on bilevel problems where the lower level subproblem is stronglyconvex and the upper level objective function is smooth. Unlike prior works which rely on twotimescale or double loop techniques, we design a stochastic momentumassisted gradient estimator for both the upper and lower level updates. The latter allows us to control the error in the stochastic gradient updates due to inaccurate solution to both subproblems. If the upper objective function is smooth but possibly nonconvex, we show that SUSTAIN requires ${O}(\epsilon^{3/2})$ iterations (each using $O(1)$ samples) to find an $\epsilon$stationary solution. The $\epsilon$stationary solution is defined as the point whose squared norm of the gradient of the outer function is less than or equal to $\epsilon$. The total number of stochastic gradient samples required for the upper and lower level objective functions match the bestknown complexity for singlelevel stochastic gradient algorithms. We also analyze the case when the upper level objective function is stronglyconvex.