-
作者：Borndoerfer, Ralf; Karbstein, Marika; Pfetsch, Marc E.
作者单位：Zuse Institute Berlin; Technical University of Darmstadt
摘要：The Steiner connectivity problem has the same significance for line planning in public transport as the Steiner tree problem for telecommunication network design. It consists in finding a minimum cost set of elementary paths to connect a subset of nodes in an undirected graph and is, therefore, a generalization of the Steiner tree problem. We propose an extended directed cut formulation for the problem which is, in comparison to the canonical undirected cut formulation, provably strong, implyi...
-
作者：Basu, Amitabh; Campelo, Manoel; Conforti, Michele; Cornuejols, Gerard; Zambelli, Giacomo
作者单位：University of California System; University of California Davis; Universidade Federal do Ceara; University of Padua; Carnegie Mellon University; University of London; London School Economics & Political Science
摘要：This paper contributes to the theory of cutting planes for mixed integer linear programs (MILPs). Minimal valid inequalities are well understood for a relaxation of an MILP in tableau form where all the nonbasic variables are continuous; they are derived using the gauge function of maximal lattice-free convex sets. In this paper we study lifting functions for the nonbasic integer variables starting from such minimal valid inequalities. We characterize precisely when the lifted coefficient is e...
-
作者：Harks, Tobias; Hoefer, Martin; Klimm, Max; Skopalik, Alexander
作者单位：Maastricht University; RWTH Aachen University; Technical University of Berlin; Dortmund University of Technology
摘要：Bottleneck congestion games properly model the properties of many real-world network routing applications. They are known to possess strong equilibria-a strengthening of Nash equilibrium to resilience against coalitional deviations. In this paper, we study the computational complexity of pure Nash and strong equilibria in these games. We provide a generic centralized algorithm to compute strong equilibria, which has polynomial running time for many interesting classes of games such as, e.g., m...
-
作者：Ahmadi, Amir Ali; Olshevsky, Alex; Parrilo, Pablo A.; Tsitsiklis, John N.
作者单位：Massachusetts Institute of Technology (MIT)
摘要：We show that unless P = NP, there exists no polynomial time (or even pseudo-polynomial time) algorithm that can decide whether a multivariate polynomial of degree four (or higher even degree) is globally convex. This solves a problem that has been open since 1992 when N. Z. Shor asked for the complexity of deciding convexity for quartic polynomials. We also prove that deciding strict convexity, strong convexity, quasiconvexity, and pseudoconvexity of polynomials of even degree four or higher i...
-
作者：Balas, Egon; Margot, Francois
作者单位：Carnegie Mellon University
摘要：Intersection cuts are generated from a polyhedral cone and a convex set S whose interior contains no feasible integer point. We generalize these cuts by replacing the cone with a more general polyhedron C. The resulting generalized intersection cuts dominate the original ones. This leads to a new cutting plane paradigm under which one generates and stores the intersection points of the extreme rays of C with the boundary of S rather than the cuts themselves. These intersection points can then ...
-
作者：Hirai, Hiroshi
作者单位：University of Tokyo
摘要：In this paper, we establish a novel duality relationship between node-capacitated multiflows and tree-shaped facility locations. We prove that the maximum value of a tree-distance-weighted maximum node-capacitated multiflow problem is equal to the minimum value of the problem of locating subtrees in a tree, and the maximum is attained by a half-integral multiflow. Utilizing this duality, we show that a half-integral optimal multiflow and an optimal location can be found in strongly polynomial ...
-
作者：de Farias, Ismael Regis, Jr.; Zhao, Ming
作者单位：Texas Tech University System; Texas Tech University
摘要：We study the convex hull of the feasible set of the semi-continuous knapsack problem, in which the variables belong to the union of two intervals. Such structure arises in a wide variety of important problems, e. g. blending and portfolio selection. We show how strong inequalities valid for the semi-continuous knapsack polyhedron can be derived and used in a branch-and-cut scheme for problems with semi-continuous variables. To demonstrate the effectiveness of these inequalities, which we call ...
-
作者：Alfakih, A. Y.; Taheri, Nicole; Ye, Yinyu
作者单位：University of Windsor; Stanford University; Stanford University
摘要：Let (G, P) be a bar framework of n vertices in general position in , for d a parts per thousand currency sign n - 1, where G is a (d + 1)-lateration graph. In this paper, we present a constructive proof that (G, P) admits a positive semidefinite stress matrix with rank (n - d - 1). We also prove a similar result for a sensor network, where the graph consists of m(a parts per thousand yen d + 1) anchors.
-
作者：Cornuejols, Gerard; Molinaro, Marco
作者单位：Carnegie Mellon University
摘要：In this paper we consider the infinite relaxation of the corner polyhedron with 2 rows. For the 1-row case, Gomory and Johnson proved in their seminal paper a sufficient condition for a minimal function to be extreme, the celebrated 2-Slope Theorem. Despite increased interest in understanding the multiple row setting, no generalization of this theorem was known for this case. We present an extension of the 2-Slope Theorem for the case of 2 rows by showing that minimal 3-slope functions satisfy...
-
作者：Gwinner, Joachim
作者单位：Bundeswehr University Munich
摘要：This paper addresses a new class of differential variational inequalities that have recently been introduced and investigated in finite dimensions as a new modeling paradigm of variational analysis to treat many applied problems in engineering, operations research, and physical sciences. This new subclass of general differential inclusions unifies ordinary differential equations with possibly discontinuous right-hand sides, differential algebraic systems with constraints, dynamic complementari...
