-
作者：Chmiela, Antonia; Munoz, Gonzalo; Serrano, Felipe
作者单位：Zuse Institute Berlin; Universidad de O'Higgins
摘要：The generation of strong linear inequalities for QCQPs has been recently tackled by a number of authors using the intersection cut paradigm-a highly studied tool in integer programming whose flexibility has triggered these renewed efforts in non-linear settings. In this work, we consider intersection cuts using the recently proposed construction of maximal quadratic-free sets. Using these sets, we derive closed-form formulas to compute intersection cuts which allow for quick cut-computations b...
-
作者：Graf, Lukas; Harks, Tobias
摘要：Instantaneous dynamic equilibrium (IDE) is a standard game-theoretic concept in dynamic traffic assignment in which individual flow particles myopically select en route currently shortest paths towards their destination. We analyze IDE within the Vickrey bottleneck model, where current travel times along a path consist of the physical travel times plus the sum of waiting times in all the queues along a path. Although IDE have been studied for decades, several fundamental questions regarding eq...
-
作者：Del Pia, Alberto; Linderoth, Jeff; Zhu, Haoran
作者单位：University of Wisconsin System; University of Wisconsin Madison
摘要：We propose a method to generate cutting-planes from multiple covers of knapsack constraints. The covers may come from different knapsack inequalities if the weights in the inequalities form a totally-ordered set. Thus, we introduce and study the structure of a totally-ordered multiple knapsack set. The valid multi-cover inequalities we derive for its convex hull have a number of interesting properties. First, they generalize the well-known (1, k)-configuration inequalities. Second, they are no...
-
作者：Slot, Lucas; Laurent, Monique
作者单位：Centrum Wiskunde & Informatica (CWI); Tilburg University
摘要：We consider the sum-of-squares hierarchy of approximations for the problem of minimizing a polynomial f over the boolean hypercube B-n = {0, 1}(n). This hierarchy provides for each integer r epsilon N a lower bound f((r)) on the minimum f(min) of f, given by the largest scalar lambda for which the polynomial f - lambda is a sum-of-squares on B-n with degree at most 2r. We analyze the quality of these bounds by estimating the worstcase error f(min) - f((r)) in terms of the least roots of the Kr...
-
作者：Dai, Yu-Hong; Zhang, Liwei
作者单位：Chinese Academy of Sciences; Chinese Academy of Sciences; University of Chinese Academy of Sciences, CAS; Dalian University of Technology
摘要：There are many important practical optimization problems whose feasible regions are not known to be nonempty or not, and optimizers of the objective function with the least constraint violation prefer to be found. A natural way for dealing with these problems is to extend the nonlinear optimization problem as the one optimizing the objective function over the set of points with the least constraint violation. This leads to the study of the shifted problem. This paper focuses on the constrained...
-
作者：Celaya, Marcel; Henk, Martin
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; Technical University of Berlin
摘要：We study proximity bounds within a natural model of random integer programs of the type max c(inverted perpendicular) x : Ax = b, x is an element of Z(>= 0), where A is an element of Z(mxn) is of rank m, b is an element of Z(m) and c is an element of Z(n). In particular, we seek bounds for proximity in terms of the parameter Delta( A), which is the square root of the determinant of the Gram matrix AA(inverted perpendicular) of A. We prove that, up to constants depending on n and m, the proximi...
-
作者：Jiang, Jie; Chen, Xiaojun
作者单位：Chongqing University; Hong Kong Polytechnic University
摘要：We formulate pure characteristics demand models under uncertainties of probability distributions as distributionally robust mathematical programs with stochastic complementarity constraints (DRMP-SCC). For any fixed first-stage variable and a random realization, the second-stage problem of DRMP-SCC is a monotone linear complementarity problem (LCP). To deal with ambiguity of probability distributions of the involved random variables in the stochastic LCP, we use the distributionally robust app...
-
作者：Rehfeldt, Daniel; Koch, Thorsten
作者单位：Zuse Institute Berlin; Technical University of Berlin
摘要：The Steiner tree problem in graphs (SPG) is one of the most studied problems in combinatorial optimization. In the past 10 years, there have been significant advances concerning approximation and complexity of the SPG. However, the state of the art in (practical) exact solution of the SPG has remained largely unchallenged for almost 20 years. While the DIMACS Challenge 2014 and the PACE Challenge 2018 brought renewed interest into Steiner tree problems, even the best new SPG solvers cannot mat...
-
作者：Mazumder, Rahul; Wang, Haoyue
作者单位：Massachusetts Institute of Technology (MIT)
摘要：Linear regression is a fundamental modeling tool in statistics and related fields. In this paper, we study an important variant of linear regression in which the predictor-response pairs are partially mismatched. We use an optimization formulation to simultaneously learn the underlying regression coefficients and the permutation corresponding to the mismatches. The combinatorial structure of the problem leads to computational challenges. We propose and study a simple greedy local search algori...
-
作者：Chandrasekaran, Karthekeyan; Wang, Weihang
作者单位：University of Illinois System; University of Illinois Urbana-Champaign
摘要：We consider the graph k-partitioning problem under the min-max objective, termed as Minmax k-cut. The input here is a graph G = (V, E) with non-negative integral edge weights w : E -> Z(+) and an integer k >= 2 and the goal is to partition the vertices into k non-empty parts V-1, ..., V-k so as to minimize max(i=1)(k) w(delta(V-i)). Although minimizing the sum objective Sigma(k)(i=1) w(delta(V-i)), termed as Minsum k-cut, has been studied extensively in the literature, very little is known abo...
