1-2期

最新文章

• Error bounds for parametric polynomial systems with applications to higher-order stability analysis and convergence rates AI翻译
  作者：Li, G.; Mordukhovich, B. S.; Nghia, T. T. A.; Pham, T. S.
  作者单位：University of New South Wales Sydney; Wayne State University; Oakland University
  摘要：The paper addresses parametric inequality systems described by polynomial functions in finite dimensions, where state-dependent infinite parameter sets are given by finitely many polynomial inequalities and equalities. Such systems can be viewed, in particular, as solution sets to problems of generalized semi-infinite programming with polynomial data. Exploiting the imposed polynomial structure together with powerful tools of variational analysis and semialgebraic geometry, we establish a far-...
• On quantile cuts and their closure for chance constrained optimization problems AI翻译
  作者：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...
• Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone AI翻译
  作者：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...
• Minimal cut-generating functions are nearly extreme AI翻译
  作者：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...
• The diameters of network-flow polytopes satisfy the Hirsch conjecture AI翻译
  作者：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.
• On the use of intersection cuts for bilevel optimization AI翻译
  作者：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...
• Valid inequalities for separable concave constraints with indicator variables AI翻译
  作者：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...
• Approximating graph-constrained max-cut AI翻译
  作者：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 ...
• On error bound moduli for locally Lipschitz and regular functions AI翻译
  作者：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...
• Improved approximations for cubic bipartite and cubic TSP AI翻译
  作者：van Zuylen, Anke
  作者单位：William & Mary
  摘要：We show improved approximation guarantees for the traveling salesman problem on cubic bipartite graphs and cubic graphs. For connected cubic bipartite graphs with n nodes, we improve on recent results of Karp and Ravi by giving a local improvement algorithm that finds a tour of length at most 5/ 4n -2. For 2-connected cubic graphs, we show that the techniques of Momke and Svensson can be combined with the techniques of Correa, Larre and Soto, to obtain a tour of length at most ('4/ 3 -1/ 8754...