(Mixed) Integer Linear 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

    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

    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

    Non-Convex Mixed-Integer Nonlinear Programming: A Survey

  • Samuel Burer
  • Adam N. Letchford
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Global Optimization Tags , , , , ,

    A wide range of problems arising in practical applications can be formulated as Mixed-Integer Nonlinear Programs (MINLPs). For the case in which the objective and constraint functions are convex, some quite effective exact and heuristic algorithms are available. When non-convexities are present, however, things become much more difficult, since then even the continuous relaxation is … Read more

    Branch-and-Price Guided Search for Integer Programs with an Application to the Multicommodity Fixed Charge Network Flow Problem

  • Mike Hewitt
  • George L. Nemhauser
  • Martin Savelsbergh
    • Categories (Mixed) Integer Linear Programming, Network Optimization

    We develop an exact algorithm for integer programs that uses restrictions of the problem to produce high-quality solutions quickly. Column generation is used both for generating these problem restrictions and for producing bounds on the value of the optimal solution. The performance of the algorithm is greatly enhanced by using structure, such as arises in … Read more

    Improved Load Plan Design Through Integer Programming Based Local Search

  • Alan L. Erera
  • Mike Hewitt
  • Martin Savelsbergh
  • Y Zhang
    • Categories (Mixed) Integer Linear Programming, Transportation Tags , ,

    We present integer programming models of the service network design problem faced by less-than-truckload (LTL) freight transportation carriers, and a solution approach for the large-scale instances that result in practical applications. To accurately represent freight consolidation opportunities, the models use a fine discretization of time. Furthermore, the models simultaneously route freight and empty trailers, and … Read more

    Exact and heuristic approaches to the budget-constrained dynamic uncapacitated facility location-network design problem

  • Natashia Boland
  • Abdolsalam Ghaderi
  • Mohammad Saeid JabalAmeli
    • Categories (Mixed) Integer Linear Programming, Facility Planning and Design, Meta Heuristics Tags , , , ,

    Facility location-network design problems seek to simultaneously determine the locations of fa- cilities and the design of the network connecting the facilities so as to best serve a set of clients accessing the facilities via the network. Here we study a dynamic (multi-period) version of the problem, subject to a budget constraint limiting the investment … Read more

    A New Approach to the Feasibility Pump in Mixed Integer Programming

  • Natashia Boland
  • Andrew C. Eberhard
  • Faramroze G. Engineer
  • Angelos Tsoukalas
    • Categories (Mixed) Integer Linear Programming Tags , , ,

    The feasibility pump is a recent, highly successful heuristic for general mixed integer linear programming problems. We show that the feasibility pump heuristic can be interpreted as a discrete version of the proximal point algorithm. In doing so, we extend and generalize some of the fundamental results in this area to provide new supporting theory. … Read more

    Boosting the Feasibility Pump

  • Natashia Boland
  • Andrew C. Eberhard
  • Faramroze G. Engineer
  • Matteo Fischetti
  • Martin Savelsbergh
  • Angelos Tsoukalas
    • Categories (Mixed) Integer Linear Programming Tags , , , ,

    The Feasibility Pump (FP) has proved to be an effective method for finding feasible solutions to mixed integer programming problems. FP iterates between a rounding procedure and a projection procedure, which together provide a sequence of points alternating between LP feasible but fractional solutions, and integer but LP relaxed infeasible solutions. The process attempts to … Read more

    A Security Framework for Smart Metering with Multiple Data Consumers

  • Antonio Capone
  • Giacomo Verticale
  • Cristina Rottondi
    • Categories (Mixed) Integer Linear Programming, Network Optimization, Telecommunications

    The increasing diffusion of Automatic Meter Reading (AMR) has raised many concerns about the protection of personal data related to energy, water or gas consumption, from which details about the habits of the users can be inferred. On the other hand, aggregated measurements about consumption are crucial for several goals, including resource provisioning, forecasting, and … Read more