-
作者：Yang, Haoxiang; Morton, David P.
作者单位：Northwestern University; The Chinese University of Hong Kong, Shenzhen
摘要：In this paper, we consider an optimization problem involving crashing an activity network under a single disruption. A disruption is an event whose magnitude and timing are random. When a disruption occurs, the duration of an activity that has yet to start-or alternatively, yet to complete-can change. We formulate a two-stage stochastic mixed-integer program, in which the timing of the stage is random. In our model, the recourse problem is a mixed-integer program. We prove the problem is NP-ha...
-
作者：Kis, Tamas; Horvath, Marko
摘要：In this paper we reconsider a known technique for constructing strong MIP formulations for disjunctive constraints of the form x is an element of boolean OR(m)(i=1) P-i, where the (P)i are polytopes. The formulation is based on the Cayley Embedding of the union of polytopes, namely, Q := conv(boolean OR(m)(i=1) P-i x {epsilon(i)}), where epsilon(i) is the ith unit vector in R-m. Our main contribution is a full characterization of the facets of Q, provided it has a certain network representatio...
-
作者：Pichler, Alois; Xu, Huifu
作者单位：Technische Universitat Chemnitz; University of Southampton
摘要：This paper considers distributionally robust formulations of a two stage stochastic programming problem with the objective of minimizing a distortion risk of the minimal cost incurred at the second stage. We carry out a stability analysis by looking into variations of the ambiguity set under the Wasserstein metric, decision spaces at both stages and the support set of the random variables. In the case when the risk measure is risk neutral, the stability result is presented with the variation o...
-
作者：Zhao, Chen; Xiu, Naihua; Qi, Houduo; Luo, Ziyan
作者单位：Beijing Jiaotong University; University of Southampton
摘要：The sparse nonlinear programming (SNP) problem has wide applications in signal and image processing, machine learning and finance, etc. However, the computational challenge posed by SNP has not yet been well resolved due to the nonconvex and discontinuous to-norm involved. In this paper, we resolve this numerical challenge by developing a fast Newton-type algorithm. As a theoretical cornerstone, we establish a first-order optimality condition for SNP based on the concept of strong beta-Lagrang...
-
作者：Nohra, Carlos J.; Raghunathan, Arvind U.; Sahinidis, Nikolaos, V
作者单位：University System of Georgia; Georgia Institute of Technology; University System of Georgia; Georgia Institute of Technology
摘要：We consider the global optimization of nonconvex mixed-integer quadratic programs with linear equality constraints. In particular, we present a new class of convex quadratic relaxations which are derived via quadratic cuts. To construct these quadratic cuts, we solve a separation problem involving a linear matrix inequality with a special structure that allows the use of specialized solution algorithms. Our quadratic cuts are nonconvex, but define a convex feasible set when intersected with th...
-
作者：Adly, Samir; Attouch, Hedy
作者单位：Universite de Limoges; Centre National de la Recherche Scientifique (CNRS); Universite de Montpellier
摘要：In aHilbert spaceH, we introduce a newclass of first-order algorithms which naturally occur as discrete temporal versions of an inertial differential inclusion jointly involving viscous friction and dry friction. The function f : H -> Rto be minimized is supposed to be differentiable (not necessarily convex), and enters the algorithm via its gradient. The dry friction damping function phi : H -> R+ is convex with a sharp minimum at the origin, (typically phi(x) = r parallel to x parallel to wi...
-
作者：Bodur, Merve; Ahmed, Shabbir; Boland, Natashia; Nemhauser, George L.
作者单位：University of Toronto; University System of Georgia; Georgia Institute of Technology
摘要：We consider integer programming (IP) problems consisting of (possibly a large number of) subsystems and a small number of coupling constraints that link variables from different subsystems. Such problems are called loosely coupled or nearly decomposable. In this paper, we exploit the idea of resource-directive decomposition to reformulate the problem so that it can be decomposed into a resource-directive master problem and a set of multiobjective programming subproblems. Recent methods develop...
-
作者：Dash, Sanjeeb; Gunluk, Oktay; Lee, Dabeen
作者单位：International Business Machines (IBM); IBM USA; Cornell University; Institute for Basic Science - Korea (IBS)
摘要：Many practical integer programming problems involve variables with one or two-sided bounds. Dunkel and Schulz (A refined Gomory-Chvatal closure for polytopes in the unit cube, , 2012) considered a strengthened version of Chvatal-Gomory (CG) inequalities that use 0-1 bounds on variables, and showed that the set of points in a rational polytope that satisfy all these strengthened inequalities is a polytope. Recently, we generalized this result by considering strengthened CG inequalities that use...
-
作者：Yang, Minghan; Milzarek, Andre; Wen, Zaiwen; Zhang, Tong
作者单位：Peking University; The Chinese University of Hong Kong, Shenzhen; Shenzhen Research Institute of Big Data; Shenzhen Institute of Artificial Intelligence & Robotics for Society; Peking University; Hong Kong University of Science & Technology
摘要：In this paper, a novel stochastic extra-step quasi-Newton method is developed to solve a class of nonsmooth nonconvex composite optimization problems. We assume that the gradient of the smooth part of the objective function can only be approximated by stochastic oracles. The proposed method combines general stochastic higher order steps derived from an underlying proximal type fixed-point equation with additional stochastic proximal gradient steps to guarantee convergence. Based on suitable bo...
-
作者：Hwang, Hark-Chin
作者单位：Kyung Hee University
摘要：In this paper, we consider the subcontracting and single-item lot-sizing problem with constant capacities, which is uncapacitated in subcontracting but capacitated in production. For a holistic understanding of the problem, an infinite-period model is proposed. Such a model provides a unified view of a capacitated lot-sizing problem. The usefulness of the infinite-period model is shown by the principle that the firm's production schedule drives the subcontractor's supply schedule. For efficien...
