-
作者：Xie, Weijun; Ahmed, Shabbir
作者单位：Virginia Polytechnic Institute & State University; University System of Georgia; Georgia Institute of Technology
摘要：A chance constrained optimization problem over a finite distribution involves a set of scenario constraints from which a small subset can be violated. We consider the setting where all scenario constraints are mixed-integer convex. Existing works typically consider a mixed integer nonlinear programming (MINLP) formulation of this problem by introducing binary variables to indicate which constraint systems are to be satisfied or violated. A variety of cutting plane approaches for this MINLP for...
-
作者：Permenter, Frank; Parrilo, Pablo
作者单位：Massachusetts Institute of Technology (MIT)
摘要：We develop a practical semidefinite programming (SDP) facial reduction procedure that utilizes computationally efficient approximations of the positive semidefinite cone. The proposed method simplifies SDPs with no strictly feasible solution (a frequent output of parsers) by solving a sequence of easier optimization problems and could be a useful pre-processing technique for SDP solvers. We demonstrate effectiveness of the method on SDPs arising in practice, and describe our publicly-available...
-
作者：Basu, Amitabh; Hildebrand, Robert; Molinaro, Marco
作者单位：Johns Hopkins University; International Business Machines (IBM); IBM USA; Pontificia Universidade Catolica do Rio de Janeiro
摘要：We study continuous (strongly) minimal cut generating functions for the model where all variables are integer. We consider both the original Gomory-Johnson setting as well as a recent extension by Yldz and Cornuejols (Math Oper Res 41:1381-1403, 2016). We show that for any continuous minimal or strongly minimal cut generating function, there exists an extreme cut generating function that approximates the (strongly) minimal function as closely as desired. In other words, the extreme functions a...
-
作者：Borgwardt, S.; De Loera, J. A.; Finhold, E.
作者单位：University of Colorado System; University of Colorado Denver; University of California System; University of California Davis; Fraunhofer Gesellschaft
摘要：We solve a problem in the combinatorics of polyhedra motivated by the network simplex method. We show that the Hirsch conjecture holds for the diameter of the graphs of all network-flow polytopes, in particular the diameter of a network-flow polytope for a network with n nodes and m arcs is never more than m + n - 1. A key step to prove this is to show the same result for classical transportation polytopes.
-
作者：Junger, Michael; Vanderbeck, Francois
-
作者：Fischetti, Matteo; Ljubic, Ivana; Monaci, Michele; Sinnl, Markus
作者单位：University of Padua; ESSEC Business School; University of Bologna; University of Vienna
摘要：We address a generic mixed-integer bilevel linear program (MIBLP), i.e., a bilevel optimization problem where all objective functions and constraints are linear, and some/all variables are required to take integer values. We first propose necessary modifications needed to turn a standard branch-and-bound MILP solver into an exact and finitely-convergent MIBLP solver, also addressing MIBLP unboundedness and infeasibility. As in other approaches from the literature, our scheme is finitely-conver...
-
作者：Lim, Cong Han; Linderoth, Jeff; Luedtke, James
作者单位：University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison
摘要：We study valid inequalities for optimization models that contain both binary indicator variables and separable concave constraints. These models reduce to a mixed-integer linear program (MILP) when the concave constraints are ignored, or to a nonconvex global optimization problem when the binary restrictions are ignored. In algorithms designed to solve these problems to global optimality, cutting planes to strengthen the relaxation are traditionally obtained using valid inequalities for the MI...
-
作者：Shen, Xiangkun; Lee, Jon; Nagarajan, Viswanath
作者单位：University of Michigan System; University of Michigan
摘要：An instance of the graph-constrained max-cut ( GCMC) problem consists of ( i) an undirected graphG = ( V, E) and ( ii) edge-weights c : V 2 . R+ on a complete undirected graph. The objective is to find a subset S. V of vertices satisfying some graph-based constraint in G that maximizes the weight u. S, v/. S cuv of edges in the cut ( S, V \ S). The types of graph constraints we can handle include independent set, vertex cover, dominating set and connectivity. Our main results are for the case ...
-
作者：Li, M. H.; Meng, K. W.; Yang, X. Q.
作者单位：Chongqing University of Arts & Sciences; Hong Kong Polytechnic University
摘要：In this paper we study local error bound moduli for a locally Lipschitz and regular function via outer limiting subdifferential sets. We show that the distance from 0 to the outer limiting subdifferential of the support function of the subdifferential set, which is essentially the distance from 0 to the end set of the subdifferential set, is an upper estimate of the local error bound modulus. This upper estimate becomes tight for a convex function under some regularity conditions. We show that...
-
作者：Fang, Ethan X.; Liu, Han; Toh, Kim-Chuan; Zhou, Wen-Xin
作者单位：Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park; Princeton University; National University of Singapore; University of California System; University of California San Diego
摘要：This paper studies the matrix completion problem under arbitrary sampling schemes. We propose a new estimator incorporating both max-norm and nuclear-norm regularization, based on which we can conduct efficient low-rank matrix recovery using a random subset of entries observed with additive noise under general non-uniform and unknown sampling distributions. This method significantly relaxes the uniform sampling assumption imposed for the widely used nuclear-norm penalized approach, and makes l...
