Stochastic Cutting Planes for Data-Driven Optimization
We introduce a stochastic version of the cutting-plane method for a large class of data-driven Mixed-Integer Nonlinear Optimization (MINLO) problems. We show that under very weak assumptions the stochastic algorithm is able to converge to an $\epsilon$-optimal solution with high probability. Numerical experiments on several problems show that stochastic cutting planes is able to deliver a multiple order-of-magnitude speedup compared to the standard cutting-plane method. We further experimentally explore the lower limits of sampling for stochastic cutting planes and show that for many problems, a sampling size of $O(\sqrt[3]{n})$ appears to be sufficient for high quality solutions.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Numerical Methods for Convex Multistage Stochastic Optimization
Optimization problems involving sequential decisions in a stochastic environment were studied in Stochastic Programming (SP), Stochastic Optimal Control (SOC) and Markov Decision Processes (MDP). In this paper we mainly …
Stochastic OptimizationVocal Bursts Type PredictionTransformer-based Stagewise Decomposition for Large-Scale Multistage Stochastic Optimization
Solving large-scale multistage stochastic programming (MSP) problems poses a significant challenge as commonly used stagewise decomposition algorithms, including stochastic dual dynamic programming (SDDP), face growing t…
Stochastic OptimizationLearning Cut Generating Functions for Integer Programming
The branch-and-cut algorithm is the method of choice to solve large scale integer programming problems in practice. A key ingredient of branch-and-cut is the use of cutting planes which are derived constraints that reduc…
Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts
The incorporation of cutting planes within the branch-and-bound algorithm, known as branch-and-cut, forms the backbone of modern integer programming solvers. These solvers are the foremost method for solving discrete opt…
BIG-bench Machine LearningOn Irrelevant Literals in Pseudo-Boolean Constraint Learning
Learning pseudo-Boolean (PB) constraints in PB solvers exploiting cutting planes based inference is not as well understood as clause learning in conflict-driven clause learning solvers. In this paper, we show that PB con…