Integer Programming

Exact Algorithms for Combinatorial Optimization Problems with Submodular Objective Functions

  • Frank Baumann
  • Christoph Buchheim
  • Sebastian Berckey
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms

    Many combinatorial optimization problems have natural formulations as submodular minimization problems over well-studied combinatorial structures. A standard approach to these problems is to linearize the objective function by introducing new variables and constraints, yielding an extended formulation. We propose two new approaches for constrained submodular minimization problems. The first is a linearization approach that requires … Read more

    Flow shop scheduling with peak power consumption constraints

  • K. Fang
  • Nelson A. Uhan
  • John W. Sutherland
  • Fu Zhao
    • Categories Combinatorial Optimization, Integer Programming, Scheduling Tags , , , , ,

    We study scheduling as a means to address the increasing energy concerns in manufacturing enterprises. In particular, we consider a flow shop scheduling problem with a restriction on peak power consumption, in addition to the traditional time-based objectives. We investigate both mathematical programming and combinatorial approaches to this scheduling problem, and test our approaches with … Read more

    Solving Mixed-Integer Nonlinear Programs by QP-Diving

  • Christian Kirches
  • Sven Leyffer
  • Ashutosh Mahajan
    • Categories (Mixed) Integer Nonlinear Programming, Quadratic Programming Tags , ,

    We present a new tree-search algorithm for solving mixed-integer nonlinear programs (MINLPs). Rather than relying on computationally expensive nonlinear solves at every node of the branch-and-bound tree, our algorithm solves a quadratic approximation at every node. We show that the resulting algorithm retains global convergence properties for convex MINLPs, and we present numerical results on … Read more

    Bilevel Programming and the Separation Problem

  • Andrea Lodi
  • Ted K. Ralphs
  • Gerhard J. Woeginger
    • Categories Cutting Plane Approaches, Integer Programming Tags , , ,

    In recent years, branch-and-cut algorithms have become firmly established as the most effective method for solving generic mixed integer linear programs (MILPs). Methods for automatically generating inequalities valid for the convex hull of solutions to such MILPs are a critical element of branch-and-cut. This paper examines the nature of the so-called separation problem, which is … Read more

    What Could a Million Cores Do To Solve Integer Programs?

  • Thorsten Koch
  • Ted K. Ralphs
  • Yuji Shinano
    • Categories Integer Programming, Parallel Algorithms Tags , ,

    Given the steady increase in cores per CPU, it is only a matter of time until supercomputers will have a million or more cores. In this article, we investigate the opportunities and challenges that will arise when trying to utilize this vast computing power to solve a single integer linear optimization problem. We also raise … Read more

    A Refined Gomory-Chvátal Closure for Polytopes in the Unit Cube

  • Juliane Dunkel
  • Andreas S. Schulz
    • Categories 0-1 Programming, Cutting Plane Approaches

    We introduce a natural strengthening of Gomory-Chvátal cutting planes for the important class of 0/1-integer programming problems and study the properties of the elementary closure that arises from the new class of cuts. Most notably, we prove that the new closure is polyhedral, we characterize the family of all facet-defining inequalities, and we compare it … Read more

    MILP formulation for islanding of power networks

  • Waqquas Bukhsh
  • Andreas Grothey
  • Kenneth McKinnon
  • Paul Trodden
    • Categories (Mixed) Integer Linear Programming, Applications - Science and Engineering

    In this paper, a mathematical formulation for the islanding of power networks is presented. Given an area of uncertainty in the network, the proposed approach uses mixed integer linear programming to isolate uncertain components and create islands, by intentionally (i) cutting lines, (ii) shedding loads and (iii) switching generators, while maximizing load supply. A key … Read more

    A Dynamic Programming Heuristic for the Quadratic Knapsack Problem

  • Franklin Djeumou Fomeni
  • Adam N. Letchford
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization, Dynamic Programming Tags , ,

    It is well known that the standard (linear) knapsack problem can be solved exactly by dynamic programming in O(nc) time, where n is the number of items and c is the capacity of the knapsack. The quadratic knapsack problem, on the other hand, is NP-hard in the strong sense, which makes it unlikely that it … Read more

    Compact formulations of the Steiner traveling salesman problem and related problems

  • Adam N. Letchford
  • Saeideh Nasiri
  • Dirk Oliver Theis
    • Categories Combinatorial Optimization, Integer Programming Tags , ,

    The Steiner Traveling Salesman Problem (STSP) is a variant of the Traveling Salesman Problem (TSP) that is particularly suitable when dealing with sparse networks, such as road networks. The standard integer programming formulation of the STSP has an exponential number of constraints, just like the standard formulation of the TSP. On the other hand, there … Read more

    Customizing the Solution Process of COIN-OR’s Linear Solvers with Python

  • Dominique Orban
  • Mehdi Towhidi
    • Categories (Mixed) Integer Linear Programming, Linear Programming, Optimization Software Design Principles Tags , , , , , ,

    Implementations of the Simplex method differ only in very specific aspects such as the pivot rule. Similarly, most relaxation methods for mixed-integer programming differ only in the type of cuts and the exploration of the search tree. Implementing instances of those frameworks would therefore be more efficient if linear and mixed-integer programming solvers let users … Read more