-
作者：Gu, Xiaoyi; Dey, Santanu S.; Richard, Jean-Philippe P.
作者单位：University System of Georgia; Georgia Institute of Technology; University of Minnesota System; University of Minnesota Twin Cities
摘要：The goal of this paper is to derive new classes of valid convex inequalities for quadratically constrained quadratic programs (QCQPs) through the technique of lifting. Our first main result shows that, for sets described by one bipartite bilinear constraint together with bounds, it is always possible to sequentially lift a seed inequality that is valid for a restriction obtained by fixing variables to their bounds, when the lifting is accomplished using affine functions of the fixed variables....
-
作者：Li, Xiaocheng; Sun, Chunlin; Ye, Yinyu
作者单位：Imperial College London; Stanford University; Stanford University
摘要：In this paper, we develop a simple and fast online algorithm for solving a class of binary integer linear programs (LPs) arisen in general resource allocation problem. The algorithm requires only one single pass through the input data and is free of matrix inversion. It can be viewed as both an approximate algorithm for solving binary integer LPs and a fast algorithm for solving online LP problems. The algorithm is inspired by an equivalent form of the dual problem of the relaxed LP and it ess...
-
作者：Liu, Peijing; Fattahi, Salar; Gomez, Andres; Kucukyavuz, Simge
作者单位：University of Southern California; University of Michigan System; University of Michigan; Northwestern University
摘要：In this paper, we consider convex quadratic optimization problems with indicator variables when the matrix Q defining the quadratic term in the objective is sparse. We use a graphical representation of the support of Q, and show that if this graph is a path, then we can solve the associated problem in polynomial time. This enables us to construct a compact extended formulation for the closure of the convex hull of the epigraph of the mixed-integer convex problem. Furthermore, motivated by infe...
-
作者：Verschae, Jose; Villagra, Matias; von Niederhausern, Leonard
作者单位：Pontificia Universidad Catolica de Chile; Pontificia Universidad Catolica de Chile; Columbia University; Universidad de O'Higgins; Universidad de Chile; Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI)
摘要：Breaking symmetries is a popular way of speeding up the branch-and-bound method for symmetric integer programs. We study fundamental domains, which are minimal and closed symmetry breaking polyhedra. Our long-term goal is to understand the relationship between the complexity of such polyhedra and their symmetry breaking capability. Borrowing ideas from geometric group theory, we provide structural properties that relate the action of the group with the geometry of the facets of fundamental dom...
-
作者：Eifler, Leon; Gleixner, Ambros
作者单位：Zuse Institute Berlin
摘要：The last milestone achievement for the roundoff-error-free solution of general mixed integer programs over the rational numbers was a hybrid-precision branch-and-bound algorithm published by Cook, Koch, Steffy, and Wolter in 2013. We describe a substantial revision and extension of this framework that integrates symbolic presolving, features an exact repair step for solutions from primal heuristics, employs a faster rational LP solver based on LP iterative refinement, and is able to produce in...
-
作者：Nie, Jiawang; Tang, Xindong
作者单位：University of California System; University of California San Diego; Hong Kong Polytechnic University
摘要：This paper studies convex generalized Nash equilibrium problems that are given by polynomials. We use rational and parametric expressions for Lagrange multipliers to formulate efficient polynomial optimization for computing generalized Nash equilibria (GNEs). The Moment-SOS hierarchy of semidefinite relaxations are used to solve the polynomial optimization. Under some general assumptions, we prove the method can find a GNE if there exists one, or detect nonexistence of GNEs. Numerical experime...
-
作者：Burtscheidt, Johanna; Claus, Matthias; Conti, Sergio; Rumpf, Martin; Sassen, Josua; Schultz, Rudiger
作者单位：University of Duisburg Essen; University of Bonn; University of Bonn
摘要：We consider pessimistic bilevel stochastic programs in which the follower maximizes over a fixed compact convex set a strictly convex quadratic function, whose Hessian depends on the leader's decision. This results in a random upper level outcome which is evaluated by a convex risk measure. Under assumptions including real analyticity of the lower-level goal function, we prove the existence of optimal solutions. We discuss an alternate model, where the leader hedges against optimal lower-level...
-
作者：Bienstock, Daniel; Del Pia, Alberto; Hildebrand, Robert
作者单位：Columbia University; University of Wisconsin System; University of Wisconsin Madison; Virginia Polytechnic Institute & State University
摘要：We focus on rational solutions or nearly-feasible rational solutions that serve as certificates of feasibility for polynomial optimization problems. We show that, under some separability conditions, certain cubic polynomially constrained sets admit rational solutions. However, we show in other cases that it is NP Hard to detect if rational solutions exist or if they exist of any reasonable size. We extend this idea to various settings including near feasible, but super optimal solutions and de...
-
作者：Ye, Jane J.; Yuan, Xiaoming; Zeng, Shangzhi; Zhang, Jin
作者单位：University of Victoria; University of Hong Kong; Peng Cheng Laboratory; Southern University of Science & Technology
摘要：In this paper, we present difference of convex algorithms for solving bilevel programs in which the upper level objective functions are difference of convex functions, and the lower level programs are fully convex. This nontrivial class of bilevel programs provides a powerful modelling framework for dealing with applications arising from hyperparameter selection in machine learning. Thanks to the full convexity of the lower level program, the value function of the lower level program turns out...
-
作者：Naves, Guyslain; Shepherd, F. Bruce; Xia, Henry
作者单位：Aix-Marseille Universite; Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I); University of British Columbia
摘要：Since 1997 there has been a steady stream of advances for the maximum disjoint paths problem. Achieving tractable results has usually required focusing on relaxations such as: (i) to allow some bounded edge congestion in solutions, (ii) to only consider the unit weight (cardinality) setting, (iii) to only require fractional routability of the selected demands (the all-or-nothing flow setting). For the general form (no congestion, general weights, integral routing) of edge-disjoint paths (edp) ...
