0-1 Programming

Modeling and Solving Location Routing and Scheduling Problems

  • Z. Akca
  • Ted K. Ralphs
  • R.T. Berger
    • Categories 0-1 Programming, Network Optimization, Production and Logistics Tags , , ,

    This paper studies location routing and scheduling problems, a class of problems in which the decisions of facility location, vehicle routing, and route assignment are optimized simultaneously. For a version with capacity and time restrictions, two formulations are presented, one graph-based and one set-partitioning-based. For the set-partitioning-based formulation, valid inequalities are identified and their effectiveness … Read more

    A Level-3 Reformulation-linearization Technique Based Bound for the Quadratic Assignment Problem

  • Monique Guignard
  • Peter M. Hahn
  • William L. Hightower
  • Yi-Rong Zhu
    • Categories 0-1 Programming, Combinatorial Optimization Tags , , , , ,

    We apply the level-3 Reformulation Linearization Technique (RLT3) to the Quadratic Assignment Problem (QAP). We then present our experience in calculating lower bounds using an essentially new algorithm, based on this RLT3 formulation. This algorithm is not guaranteed to calculate the RLT3 lower bound exactly, but approximates it very closely and reaches it in some … Read more

    Branching proofs of infeasibility in low density subset sum problems

  • Gabor Pataki
  • Mustafa Tural
    • Categories 0-1 Programming, Combinatorial Optimization

    We prove that the subset sum problem has a polynomial time computable certificate of infeasibility for all $a$ weight vectors with density at most $1/(2n)$ and for almost all integer right hand sides. The certificate is branching on a hyperplane, i.e. by a methodology dual to the one explored by Lagarias and Odlyzko; Frieze; Furst … Read more

    Extended Formulations for Packing and Partitioning Orbitopes

  • Yuri Faenza
  • Volker Kaibel
    • Categories 0-1 Programming, Polyhedra Tags , ,

    We give compact extended formulations for the packing and partitioning orbitopes (with respect to the full symmetric group) described and analyzed in Kaibel and Pfetsch (Math. Program. 114 (1), 2008, 1-36). These polytopes are the convex hulls of all 0/1-matrices with lexicographically sorted columns and at most, resp. exactly, one 1-entry per row. They are … Read more

    On Non-Convex Quadratic Programming with Box Constraints

  • Samuel Burer
  • Adam N. Letchford
    • Categories 0-1 Programming, Convex Optimization, Global Optimization Theory Tags , ,

    Non-Convex Quadratic Programming with Box Constraints is a fundamental NP-hard global optimisation problem. Recently, some authors have studied a certain family of convex sets associated with this problem. We prove several fundamental results concerned with these convex sets: we determine their dimension, characterise their extreme points and vertices, show their invariance under certain affine transformations, … Read more

    An Improved Algorithm for the Generalized Quadratic Assignment Problem

  • Monique Guignard
  • Peter M. Hahn
  • Artur Alves Pessoa
  • Yi-Rong Zhu
    • Categories 0-1 Programming, Combinatorial Optimization Tags , ,

    In the Generalized Quadratic Assignment Problem (GQAP), given M facilities and N locations, one must assign each facility to one location so as to satisfy the given facility space requirements, minimizing the sum of installation and facility interaction costs. In this paper, we propose a new Lagrangean relaxation and a lower bounding procedure for the … 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

    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

    Solving chance-constrained combinatorial problems to optimality

  • Olivier Klopfenstein
    • Categories 0-1 Programming, Stochastic Programming Tags ,

    The aim of this paper is to provide new efficient methods for solving general chance-constrained integer linear programs to optimality. Valid linear inequalities are given for these problems. They are proved to characterize properly the set of solutions. They are based on a specific scenario, whose definition impacts strongly on the quality of the linear … Read more