-
作者：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...
-
作者：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...
-
作者：Fischetti, Matteo; Salvagnin, Domenico; Zanette, Arrigo
作者单位：University of Padua; University of Padua
摘要：A new cut selection criterion for Benders' cuts is proposed and computationally analyzed. The results show that the new criterion is more robust-and often considerably faster-than the standard ones.
-
作者：Lodi, Andrea; Malaguti, Enrico; Stier-Moses, Nicolas E.
作者单位：University of Bologna; Columbia University
摘要：Inspired by the One Laptop Per Child project, we consider mesh networks that connect devices that cannot recharge their batteries easily. We study how the mesh should retransmit information to make use of the energy stored in each of the nodes effectively. The solution that minimizes the total energy spent by the whole network may be very unfair to some nodes because they bear a disproportionate burden of the traffic. A Nash equilibrium achieved when nodes minimize the energy they spend does n...
-
作者：Mahjoub, A. Ridha; McCormick, S. Thomas
作者单位：Universite PSL; Universite Paris-Dauphine; Centre National de la Recherche Scientifique (CNRS); University of British Columbia
摘要：We consider the flow on paths versions of Max Flow and Min Cut when we restrict to paths having at most B arcs, and for versions where we allow fractional solutions or require integral solutions. We show that the continuous versions are polynomial even if B is part of the input, but that the integral versions are polynomial only when B <= 3. However, when B <= 3 we show how to solve the problems using ordinary Max Flow/Min Cut. We also give tight bounds on the integrality gaps between the inte...
-
作者：Buchheim, Christoph; Liers, Frauke; Oswald, Marcus
作者单位：University of Cologne; Dortmund University of Technology; Ruprecht Karls University Heidelberg
摘要：In many practical applications, the task is to optimize a non-linear objective function over the vertices of a well-studied polytope as, e.g., the matching polytope or the travelling salesman polytope (TSP). Prominent examples are the quadratic assignment problem and the quadratic knapsack problem; further applications occur in various areas such as production planning or automatic graph drawing. In order to apply branch-and-cut methods for the exact solution of such problems, the objective fu...
-
作者：Andersen, Kent; Louveaux, Quentin; Weismantel, Robert
作者单位：University of Liege; Otto von Guericke University
摘要：In Andersen et al. (Lecture Notes in Computer Science, vol. 4513, Springer, Berlin, pp. 1-15, 2007) we studied a mixed-integer set arising from two rows of a simplex tableau. We showed that facets of such a set can be obtained from lattice point free triangles and quadrilaterals associated with either three or four variables. In this paper we generalize our findings and show that, when upper bounds on the non-basic variables are also considered, further classes of facets arise that cannot be o...
-
作者：Musitelli, Antoine
作者单位：University of Padua
摘要：Binet matrices generalize network matrices and play an important role in combinatorial optimization. A first polynomial-time algorithm for recognizing binet matrices appeared in the author's doctoral thesis. In this paper, we present some key ideas and results involved in the design of this algorithm. We show how we can find a Camion basis of the input matrix, whenever this one is binet, and then reduce the recognition problem to that of special billet matrices called bicyclic and cyclic.
