Integer Programming

Disjunctive Cuts for Non-Convex Mixed Integer Quadratically Constrained Programs

  • Pierre Bonami
  • Jon Lee
  • Anureet Saxena
    • Categories (Mixed) Integer Nonlinear Programming, Constrained Nonlinear Optimization, Global Optimization Tags , , , ,

    This paper addresses the problem of generating strong convex relaxations of Mixed Integer Quadratically Constrained Programming (MIQCP) problems. MIQCP problems are very difficult because they combine two kinds of non-convexities: integer variables and non-convex quadratic constraints. To produce strong relaxations of MIQCP problems, we use techniques from disjunctive programming and the lift-and-project methodology. In particular, … Read more

    Disjunctive Decomposition for Two-Stage Stochastic Mixed-Binary Programs with Random Recourse

  • Lewis Ntaimo
    • Categories Cutting Plane Approaches, Stochastic Programming Tags , , , ,

    This paper introduces disjunctive decomposition for two-stage mixed 0-1 stochastic integer programs (SIPs) with random recourse. Disjunctive decomposition allows for cutting planes based on disjunctive programming to be generated for each scenario subproblem under a temporal decomposition setting of the SIP problem. A new class of valid inequalities for mixed 0-1 SIP with random recourse … Read more

    A p-Cone Sequential Relaxation Procedure for 0-1 Integer Programs

  • Samuel Burer
  • Jieqiu Chen
    • Categories 0-1 Programming, Global Optimization Theory, Second-Order Cone Programming Tags , , , ,

    Given a 0-1 integer programming problem, several authors have introduced sequential relaxation techniques — based on linear and/or semidefinite programming — that generate the convex hull of integer points in at most $n$ steps. In this paper, we introduce a sequential relaxation technique, which is based on $p$-order cone programming ($1 \le p \le \infty$). … Read more

    Building separating concentric balls to solve a multi-instance classification problem

  • Emilio Carrizosa
  • José F. Gordillo
  • Frank Plastria
    • Categories (Mixed) Integer Nonlinear Programming, Data-Mining, Meta Heuristics Tags , , ,

    In this work, we consider a classification problem where the objects to be classified are bags of instances which are vectors measuring d different attributes. The classification rule is defined in terms of a ball, whose center and radius are the parameters to be computed. Given a bag, it is assigned to the positive class … Read more

    Hilbert’s Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility

  • Jesús A. De Loera
  • Jon Lee
  • Peter Malkin
  • Susan Margulies
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization, Graphs and Matroids Tags , ,

    Systems of polynomial equations over an algebraically-closed field K can be used to concisely model many combinatorial problems. In this way, a combinatorial problem is feasible (e.g., a graph is 3-colorable, hamiltonian, etc.) if and only if a related system of polynomial equations has a solution over K. In this paper, we investigate an algorithm … Read more

    A Class Representative Model for Pure Parsimony Haplotyping

  • Daniele Catanzaro
  • Martine Labbé
  • Alessandra Godi
    • Categories (Mixed) Integer Linear Programming, Basic Sciences Applications Tags , ,

    Parsimonious haplotype estimation from aligned Single Nucleotide Polymorphism (SNP) fragments consists of finding the minimum number of haplotypes necessary to explain a given set of genotypes. This problem is known to be NP-Hard. Here we describe a new integer linear-programming model to tackle this problem based on the concept of class representatives, already used for … Read more

    Size constrained graph partitioning polytope. Part I: Dimension and trivial facets

  • Martine Labbé
  • F. Aykut Özsoy
    • Categories 0-1 Programming, Polyhedra Tags , , , , ,

    We consider the problem of clustering a set of items into subsets whose sizes are bounded from above and below. We formulate the problem as a graph partitioning problem and propose an integer programming model for solving it. This formulation generalizes several well-known graph partitioning problems from the literature like the clique partitioning problem, the … Read more

    Size constrained graph partitioning polytope. Part II: Non-trivial facets

  • Martine Labbé
  • F. Aykut Özsoy
    • Categories 0-1 Programming, Polyhedra Tags , , , ,

    We consider the problem of clustering a set of items into subsets whose sizes are bounded from above and below. We formulate the problem as a graph partitioning problem and propose an integer programming model for solving it. This formulation generalizes several well-known graph partitioning problems from the literature like the clique partitioning problem, the … Read more

    Constraint Orbital Branching

  • Jeff Linderoth
  • James Ostrowski
  • Fabrizio Rossi
  • Stefano Smriglio
    • Categories Integer Programming, Statistics

    Orbital branching is a method for branching on variables in integer programming that reduces the likelihood of evaluating redundant, isomorphic nodes in the branch-and-bound procedure. In this work, the orbital branching methodology is extended so that the branching disjunction can be based on an arbitrary constraint. Many important families of integer programs are structured such … Read more

    Parallel Approximation, and Integer Programming Reformulation

  • Gabor Pataki
  • Mustafa Tural
    • Categories (Mixed) Integer Linear Programming, Integer Programming, Polyhedra Tags , , ,

    We analyze two integer programming reformulations of the n-dimensional knapsack feasibility problem without assuming any structure on the weight vector $a.$ Both reformulations have a constraint matrix in which the columns form a reduced basis in the sense of Lenstra, Lenstra, and Lov\’asz. The nullspace reformulation of Aardal, Hurkens and Lenstra has n-1 variables, and … Read more