This paper considers a class of two-stage stochastic mixed-integer optimization problems where, for a given first-stage solution, we can determine the optimal values of recourse variables sequentially. This class of problems arises in a wide variety of applications. In the case of multivariate discrete distributions for uncertain parameters, a standard stochastic programming formulation of these problems involves an exponential number of scenarios, therefore an exponential number of variables and constraints. We propose a new mixed-integer programming modeling approach where the number of variables and constraints is independent of the number of scenarios and scales at most pseudopolynomially with the problem size. The proposed modeling approach relies on state variables that track the system’s state as the uncertainty realizes sequentially. We demonstrate the advantages of the proposed approach in two applications arising in project scheduling and operating room allocation. Summary of Contribution: This paper proposes a new modeling approach for a class of two-stage stochastic optimization problems that is computationally more efficient than the traditional scenario-based stochastic integer programming models. The proposed modeling approach relies on state variables that track the system's state as the uncertainty realizes sequentially. We demonstrated the efficiency of the proposed approach by computational results on two applications in project scheduling and operating room allocation.

A lower bound for a finite-scenario-based chance-constrained program is the quantile value corresponding to the sorted optimal objective values of scenario subproblems. This quantile bound can be improved by grouping subsets of scenarios at the expense of solving larger subproblems. The quality of the bound depends on how the scenarios are grouped. In this paper, we formulate a mixed-integer bilevel program that optimally groups scenarios to tighten the quantile bounds. For general chance-constrained programs, we propose a branch-and-cut algorithm to optimize the bilevel program, and for chance-constrained linear programs, a mixed-integer linear-programming reformulation is derived. We also propose several heuristics for grouping similar or dissimilar scenarios. Our computational results demonstrate that optimal grouping bounds are much tighter than heuristic bounds, resulting in smaller root-node gaps and better performance of scenario decomposition for solving chance-constrained 0-1 programs. Also, the optimal grouping bounds can be greatly strengthened using larger group size. Summary of Contribution: Chance-constrained programs are in general NP-hard but widely used in practice for lowering the risk of undesirable outcomes during decision making under uncertainty. Assuming finite scenarios of uncertain parameter, chance-constrained programs can be reformulated as mixed-integer linear programs with binary variables representing whether or not the constraints are satisfied in corresponding scenarios. A useful quantile bound for solving chance-constrained programs can be improved by grouping subsets of scenarios at the expense of solving larger subproblems. In this paper, we develop algorithms for optimally and heuristically grouping scenarios to tighten the quantile bounds. We aim to improve both the computation and solution quality of a variety of chance-constrained programs formulated for different Operations Research problems.

Security-constrained unit commitment (SCUC) is a fundamental problem in power systems and electricity markets. In practical settings, SCUC is repeatedly solved via mixed-integer linear programming (MIP), sometimes multiple times per day, with only minor changes in input data. In this work, we propose a number of machine learning techniques to effectively extract information from previously solved instances in order to significantly improve the computational performance of MIP solvers when solving similar instances in the future. Based on statistical data, we predict redundant constraints in the formulation, good initial feasible solutions, and affine subspaces where the optimal solution is likely to lie, leading to a significant reduction in problem size. Computational results on a diverse set of realistic and large-scale instances show that using the proposed techniques, SCUC can be solved on average 4.3 times faster with optimality guarantees and 10.2 times faster without optimality guarantees, with no observed reduction in solution quality. Out-of-distribution experiments provide evidence that the method is somewhat robust against data-set shift. Summary of Contribution. The paper describes a novel computational method, based on a combination of mixed-integer linear programming (MILP) and machine learning (ML), to solve a challenging and fundamental optimization problem in the energy sector. The method advances the state-of-the-art, not only for this particular problem, but also, more generally, in solving discrete optimization problems via ML. We expect that the techniques presented can be readily used by practitioners in the energy sector and adapted, by researchers in other fields, to other challenging operations research problems that are solved routinely.

Scenario decomposition algorithms for stochastic programs compute bounds by dualizing all nonanticipativity constraints and solving individual scenario problems independently. We develop an approach that improves on these bounds by reinforcing a carefully chosen subset of nonanticipativity constraints, effectively placing scenarios into groups. Specifically, we formulate an optimization problem for grouping scenarios that aims to improve the bound by optimizing a proxy metric based on information obtained from evaluating a subset of candidate feasible solutions. We show that the proposed grouping problem is NP-hard in general, identify a polynomially solvable case, and present two formulations for solving the problem: a matching formulation for a special case and a mixed-integer programming formulation for the general case. We use the proposed grouping scheme as a preprocessing step for a particular scenario decomposition algorithm and demonstrate its effectiveness in solving standard test instances of two-stage 0–1 stochastic programs. Using this approach, we are able to prove optimality for all previously unsolved instances of a standard test set. Additionally, we implement this scheme as a preprocessing step for PySP, a publicly available and widely used implementation of progressive hedging, and compare this grouping approach with standard grouping approaches on large-scale stochastic unit commitment instances. Finally, the idea is extended to propose a finitely convergent algorithm for two-stage stochastic programs with a finite feasible region.

Abstract We present a set of integer programs (IPs) for the Steiner tree problem with the property that the best solution obtained by solving all IPs provides an optimal Steiner tree. Each IP is polynomial in the size of the underlying graph and our main result is that the linear programming (LP) relaxation of each IP is integral so that it can be solved as a linear program. However, the number of IPs grows exponentially with the number of terminals in the Steiner tree. As a consequence, we are able to solve the Steiner tree problem by solving a polynomial number of LPs, when the number of terminals is fixed.

In this paper, we extend a recently proposed scenario decomposition algorithm for risk-neutral 0-1 stochastic programs to the risk-averse setting. Specifically, we consider two-stage risk-averse 0-1 stochastic programs with objective functions based on coherent risk measures. Using a dual representation of a coherent risk measure, we first derive an equivalent minimax reformulation of the considered problem. We then develop three variants of the scenario decomposition algorithm for this minimax formulation based on different relaxations of the nonanticipaticity constraints. The algorithms proceed by solving scenario subproblems to obtain candidate solutions and bounds and subsequently cutting off the candidate solutions from the search space to achieve convergence to an optimal solution. We design three parallelization schemes for implementing the algorithms with different tradeoffs between overhead time and computation time. Our computational results with risk-averse extensions of two standard stochastic 0-1 programming test instances demonstrate the scalability of the proposed decomposition and parallelization framework.

Electric power generation expansion planning (GEP) is the problem of determining an optimal construction and generation plan of both new and existing electric power plants to meet future electricit...

``Primal heuristics'' are a key contributor to the improved performance of exact branch-and-bound solvers for combinatorial optimization and integer programming. Perhaps the most crucial question concerning primal heuristics is that of at which nodes they should run, to which the typical answer is via hard-coded rules or fixed solver parameters tuned, offline, by trial-and-error. Alternatively, a heuristic should be run when it is most likely to succeed, based on the problem instance's characteristics, the state of the search, etc. In this work, we study the problem of deciding at which node a heuristic should be run, such that the overall (primal) performance of the solver is optimized. To our knowledge, this is the first attempt at formalizing and systematically addressing this problem. Central to our approach is the use of Machine Learning (ML) for predicting whether a heuristic will succeed at a given node. We give a theoretical framework for analyzing this decision-making process in a simplified setting, propose a ML approach for modeling heuristic success likelihood, and design practical rules that leverage the ML models to dynamically decide whether to run a heuristic at each node of the search tree. Experimentally, our approach improves the primal performance of a state-of-the-art Mixed Integer Programming solver by up to 6% on a set of benchmark instances, and by up to 60% on a family of hard Independent Set instances.

We consider the integer L-shaped method for two-stage stochastic integer programs. To improve the performance of the algorithm, we present and combine two strategies. First, to avoid time-consuming exact evaluations of the second-stage cost function, we propose a simple modification that alternates between linear and mixed-integer subproblems. Next, to better approximate the shape of the second-stage cost function, we present a general framework to generate optimality cuts via a cut-generating linear program that considers information from all solutions found up to any given stage of the method. To address the impact of the proposed approaches, we report computational results on two classes of stochastic integer problems.

We consider a class of linear programs involving a set of covering constraints of which at most k are allowed to be violated. We show that this covering linear program with violation is strongly 𝒩𝒫-hard. To improve the performance of mixed-integer programming-based schemes for these problems, we introduce and analyze a coefficient strengthening scheme, adapt and analyze an existing cutting plane technique, and present a branching technique. Through computational experiments, we empirically verify that these techniques are significantly effective in improving solution times over the CPLEX mixed-integer programming solver. In particular, we observe that the proposed schemes can cut down solution times from as much as six days to under four hours.

We propose a robust optimization framework to deal with uncertain component reliabilities in redundancy allocation problems in series-parallel systems. The proposed models are based on linearized versions of standard mixed integer nonlinear programming (MINLP) formulations of these problems. We extend the linearized models to address uncertainty by assuming that the component reliabilities belong to a budgeted uncertainty set, and develop robust counterpart models. A key challenge is that, because the models involve nonlinear functions of the uncertain data, classical robust optimization approaches cannot apply directly to construct their robust optimization counterparts. We exploit problem structure to develop robust counterparts and exact solution methods, and present computational results demonstrating their performance.

We design and implement an intensity-modulated radiation therapy plan generation technology that effectively and efficiently optimizes beam geometry as well as beam intensities. Our approach is based on an existing linear programming-based fluence map optimization model that approximates dose-volume requirements using conditional value-at-risk (C-VaR) constraints. We show how the parameters of the C-VaR constraints can be used to control various metrics of treatment plan quality. Next, we develop an automated search strategy for parameter tuning. Finally, beam angle selection is integrated with fluence map optimization. The beam angle selection scheme employs a bicriteria scoring of beam angle geometries and a selection mechanism to choose from among the set of nondominated geometries. The overall technology is automated and generates several high-quality treatment plans satisfying dose prescription requirements in a single invocation and without human guidance. The technology has been tested on various real-patient cases with uniform success.

This paper studies two mixed-integer linear programming (MILP) formulations for piecewise linear functions considered in Li et al. [Li, H.-L., H.-C. Lu, C.-H. Huang, N.-Z. Hu. 2009. A superior representation method for piecewise linear functions. INFORMS J. Comput. 21(2) 314–321]. Although the ideas used to construct one of these formulations are theoretically interesting and could eventually provide a computational advantage, we show that their use in modeling piecewise linear functions yields a poor MILP formulation. We specifically show that neither of the formulations in this paper has a favorable strength property shared by all standard MILP formulations for piecewise linear functions. We also show that both formulations in Li et al. (2009) are significantly outperformed computationally by standard MILP formulations.

This paper develops a linear-programming-based branch-and-bound algorithm for mixed-integer conic quadratic programs. The algorithm is based on a known higher-dimensional or lifted polyhedral relaxation of conic quadratic constraints. The algorithm is different from other linear-programming-based branch-and-bound algorithms for mixed-integer nonlinear programs in that it is not based on cuts from gradient inequalities and it sometimes branches on integer feasible solutions. The algorithm is tested on a series of portfolio optimization problems. It is shown that it significantly outperforms commercial and open-source solvers based on both linear and nonlinear relaxations.

Stochastic integer programs (SIPs) represent a very difficult class of optimization problems arising from the presence of both uncertainty and discreteness in planning and decision problems. Although applications of SIPs are abundant, nothing is available by way of computational software. On the other hand, commercial software packages for solving deterministic integer programs have been around for quite a few years, and more recently, a package for solving stochastic linear programs has been released. In this paper, we describe how these software tools can be integrated and exploited for the effective solution of general-purpose SIPs. We demonstrate these ideas on four problem classes from the literature and show significant computational advantages.