-
作者：Vandenbussche, D; Nemhauser, GL
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; University System of Georgia; Georgia Institute of Technology
摘要：We present the implementation of a branch-and-cut algorithm for bound constrained nonconvex quadratic programs. We use a class of inequalities developed in [12] as cutting planes. We present various branching strategies and compare the algorithm to several other methods to demonstrate its effectiveness.
-
作者：Neto, JXD; Ferreira, OP; Monteiro, RDC
作者单位：Universidade Federal do Piaui; Universidade Federal de Goias; University System of Georgia; Georgia Institute of Technology
摘要：This paper studies the asymptotic behavior of the central path (X(nu), S(nu), y(nu)) as nu down arrow 0 for a class of degenerate semidefinite programming (SDP) problems, namely those that do not have strictly complementary primal-dual optimal solutions and whose degenerate diagonal blocks X-T(nu) and S-T(nu) of the central path are assumed to satisfy max{||X-T(nu)||, ||S-T(nu)||} = O(root nu). We establish the convergence of the central path towards a primal-dual optimal solution, which is ch...
-
作者：Borradaile, G; Van Hentenryck, P
作者单位：Brown University
摘要：Global optimization problems are often approached by branch and bound algorithms which use linear relaxations of the nonlinear constraints computed from the current variable bounds. This paper studies how to derive safe linear relaxations to account for numerical errors arising when computing the linear coefficients. It first proposes two classes of safe linear estimators for univariate functions. Class-1 estimators generalize previously suggested estimators from quadratic to arbitrary functio...
-
作者：Balas, E; de Souza, CC
作者单位：Carnegie Mellon University; Universidade Estadual de Campinas
摘要：The vertex separator (VS) problem in a graph G = (V, E) asks for a partition of V into nonempty subsets A, B, C such that there is no edge between A and B, and |C| is minimized subject to a bound on max {|A|, |B|}. We give a mixed integer programming formulation of the problem and investigate the vertex separator polytope (VSP), the convex hull of incidence vectors of vertex separators. Necessary and sufficient conditions are given for the VSP to be full dimensional. Central to our investigati...
