-
作者：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...
