-
作者：Kaibel, Volker; Stephan, Ruediger
作者单位：Otto von Guericke University; Technical University of Berlin
摘要：Given a directed graph D = (N, A) and a sequence of positive integers 1 = c(1) < c(2) < center dot center dot center dot < cm = |N|, we consider those path and cycle polytopes that are defined as the convex hulls of the incidence vectors simple paths and cycles of D of cardinality c(p) for some p is an element of {1, ..., m}, respectively. We present integer characterizations of these polytopes by facet defining linear inequalities for which the separation problem can be solved in polynomial t...
-
作者：Luedtke, James; Ahmed, Shabbir; Nemhauser, George L.
作者单位：University of Wisconsin System; University of Wisconsin Madison; University System of Georgia; Georgia Institute of Technology
摘要：Linear programs with joint probabilistic constraints (PCLP) are difficult to solve because the feasible region is not convex. We consider a special case of PCLP in which only the right-hand side is random and this random vector has a finite distribution. We give a mixed-integer programming formulation for this special case and study the relaxation corresponding to a single row of the probabilistic constraint. We obtain two strengthened formulations. As a byproduct of this analysis, we obtain n...
-
作者：Tseng, Paul
作者单位：University of Washington; University of Washington Seattle
摘要：Convex optimization problems arising in applications, possibly as approximations of intractable problems, are often structured and large scale. When the data are noisy, it is of interest to bound the solution error relative to the (unknown) solution of the original noiseless problem. Related to this is an error bound for the linear convergence analysis of first-order gradient methods for solving these problems. Example applications include compressed sensing, variable selection in regression, ...
-
作者：Guenluek, Oktay; Linderoth, Jeff
作者单位：International Business Machines (IBM); IBM USA; University of Wisconsin System; University of Wisconsin Madison
摘要：We study mixed integer nonlinear programs (MINLP)s that are driven by a collection of indicator variables where each indicator variable controls a subset of the decision variables. An indicator variable, when it is turned off, forces some of the decision variables to assume fixed values, and, when it is turned on, forces them to belong to a convex set. Many practical MINLPs contain integer variables of this type. We first study a mixed integer set defined by a single separable quadratic constr...
-
作者：Anstreicher, Kurt M.; Burer, Samuel
作者单位：University of Iowa
摘要：Let C be the convex hull of points {(1 x) ((1) x)(T) [x is an element of F subset of R-n}. Representing or approximating C is a fundamental problem for global optimization algorithms based on convex relaxations of products of variables. We show that if 17 <= 4 and F is a simplex, then C has a computable representation in terms of matrices X that are doubly nonnegative (positive semidefinite and componentwise nonnegative). We also prove that if n = 2 and F is a box, then C has a representation ...
-
作者：Dey, Santanu S.; Wolsey, Laurence A.
作者单位：Universite Catholique Louvain; Universite Catholique Louvain
摘要：Recently Andersen et al. [1], Borozan and Cornuejols [6] and Cornuejols and Margot [9] have characterized the extreme valid inequalities of a mixed integer set consisting of two equations with two free integer variables and non-negative continuous variables. These inequalities are either split cuts or intersection cuts derived using maximal lattice-free convex sets. In order to use these inequalities to obtain cuts from two rows of a general simplex tableau, one approach is to extend the syste...
-
作者：Cadoux, Florent
摘要：The problem of separation is to find an affine hyperplane, or cut, that lies between the origin O and a given closed convex set Q in a Euclidean space. We study cuts which are deep in a well-defined geometrical sense, and facet-defining. The cases when the deepest cut is decomposable as a combination of facet-defining cuts are characterized using the reverse polar set. When Q is a disjunctive polyhedron, a description of the reverse polar, linked to the so-called cut generating linear program ...
-
作者：Caprara, Alberto; Letchford, Adam N.
作者单位：University of Bologna; Lancaster University
摘要：Combinatorial optimization games form an important subclass of cooperative games. In recent years, increased attention has been given to the issue of finding good cost shares for such games. In this paper, we define a very general class of games, called integer minimization games, which includes the combinatorial optimization games in the literature as special cases. We then present new techniques, based on row and column generation, for computing good cost shares for these games. To illustrat...
-
作者：McCormick, S. Thomas; Fujishige, Satoru
作者单位：University of British Columbia; Kyoto University
摘要：Bisubmodular functions are a natural directed, or signed, extension of submodular functions with several applications. Recently Fujishige and Iwata showed how to extend the Iwata, Fleischer, and Fujishige (IFF) algorithm for submodular function minimization (SFM) to bisubmodular function minimization (BSFM). However, they were able to extend only the weakly polynomial version of IFF to BSFM. Here we investigate the difficulty that prevented them from also extending the strongly polynomial vers...
-
作者：Dumitrescu, Irina; Ropke, Stefan; Cordeau, Jean-Francois; Laporte, Gilbert
作者单位：Universite de Montreal; HEC Montreal; University of Sydney; Universite de Montreal; HEC Montreal
摘要：The Traveling Salesman Problem with Pickup and Delivery (TSPPD) is defined on a graph containing pickup and delivery vertices between which there exists a one-to-one relationship. The problem consists of determining a minimum cost tour such that each pickup vertex is visited before its corresponding delivery vertex. In this paper, the TSPPD is modeled as an integer linear program and its polyhedral structure is analyzed. In particular, the dimension of the TSPPD polytope is determined and seve...
