(Mixed) Integer Linear Programming

A Branch-and-Cut Algorithm for Mixed Integer Bilevel Linear Optimization Problems and Its Implementation

  • S.T. DeNegre
  • Ted K. Ralphs
  • S. Tahernejad
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Optimization Software and Modeling Systems Tags , , ,

    In this paper, we describe an algorithmic framework for solving mixed integer bilevel linear optimization problems (MIBLPs) by a generalized branch-and-cut approach. The framework presented merges features from existing algorithms (for both traditional mixed integer linear optimization and MIBLPs) with new techniques to produce a flexible and robust framework capable of solving a wide range … Read more

    Generation techniques for linear and integer programming instances with controllable properties

  • Davaatseren Baatar
  • Hans D Mittelmann
  • Simon Bowly
  • Kate Smith-Miles
    • Categories (Mixed) Integer Linear Programming, Optimization Software and Modeling Systems Tags , ,

    This paper addresses the problem of generating synthetic test cases for experimentation in linear programming. We propose a method which maps instance generation and instance space search to an alternative encoded space. This allows us to develop a generator for feasible bounded linear programming instances with controllable properties. We show that this method is capable … Read more

    Location of charging stations in electric car sharing systems

  • Georg Brandstätter
  • Markus Leitner
  • Ivana Ljubić
    • Categories (Mixed) Integer Linear Programming, Transportation Tags , , , , ,

    Electric vehicles are a prime candidate for use within an urban car sharing system, both from an economic and environmental perspective. However, their relatively short range necessitates frequent and rather time-consuming recharging throughout the day. Thus, charging stations must be built throughout the system’s operational area where cars can be charged between uses. In this … Read more

    Determining optimal locations for charging stations of electric car-sharing systems under stochastic demand

  • Georg Brandstätter
  • Michael Kahr
  • Markus Leitner
    • Categories (Mixed) Integer Linear Programming, Transportation Tags , , , , ,

    In this article, we introduce and study a two-stage stochastic optimization problem suitable to solve strategic optimization problems of car-sharing systems that utilize electric cars. By combining the individual advantages of car-sharing and electric vehicles, such electric car-sharing systems may help to overcome future challenges related to pollution, congestion, or shortage of fossil fuels. A … Read more

    Co-optimization of Demand Response and Reserve Offers for a Major Consumer

  • Miguel F. Anjos
  • Anthony Downward
  • Michael C. Ferris
  • Mahbubeh Habibian
  • Golbon Zakeri
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Stochastic Programming Tags , ,

    In this paper we present a stochastic optimization problem for a strategic major consumer who has flexibility over its consumption and can offer reserve. Our model is a bi-level optimization model (reformulated as a mixed-integer program) that embeds the optimal power flow problem, in which electricity and reserve are co-optimized. We implement this model for … Read more

    A hybrid approach for Bi-Objective Optimization

  • Kim Allan Andersen
  • Thomas R. Stidsen
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Multi-Criteria Optimization

    A large number of the real world planning problems which are today solved using Operations Research methods are actually multi-objective planning problems, but most of them are solved using single-objective methods. The reason for converting, i.e. simplifying, multi- objective problems to single-objective problems is that no standard multi-objective solvers exist and specialized algorithms need to … Read more

    Random Sampling and Machine Learning to Understand Good Decompositions

  • Saverio Basso
  • Alberto Ceselli
  • Andrea Tettamanzi
    • Categories (Mixed) Integer Linear Programming, Data-Mining Tags , ,

    Motivated by its implications in the development of general purpose solvers for decomposable Mixed Integer Programs (MIP), we address a fundamental research question, that is to assess if good decomposition patterns can be consistently found by looking only at static properties of MIP input instances, or not. We adopt a data driven approach, devising a … Read more

    A Novel Matching Formulation for Startup Costs in Unit Commitment

  • Bernard Knueven
  • James Ostrowski
  • Jean-Paul Watson
    • Categories (Mixed) Integer Linear Programming, Scheduling Tags , ,

    We present a novel formulation for startup cost computation in the unit commitment problem (UC). Both the proposed formulation and existing formulations in the literature are placed in a formal, theoretical dominance hierarchy based on their respective linear programming relaxations. The proposed formulation is tested empirically against existing formulations on large-scale unit commitment instances drawn … Read more

    Partial hyperplane activation for generalized intersection cuts

  • Egon Balas
  • Aleksandr M. Kazachkov
  • François Margot
  • Selvaprabu Nadarajah
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , ,

    The generalized intersection cut (GIC) paradigm is a recent framework for generating cutting planes in mixed integer programming with attractive theoretical properties. We investigate this computationally unexplored paradigm and observe that a key hyperplane activation procedure embedded in it is not computationally viable. To overcome this issue, we develop a novel replacement to this procedure … Read more

    Locality sensitive heuristics for solving the Data Mule Routing Problem

  • Lucia Drummond
  • Luiz Satoru Ochi
  • P.H. González
  • Philippe Michelon
  • P.L.A Munhoz
  • U.S. Souza
    • Categories (Mixed) Integer Linear Programming, Approximation Algorithms, Telecommunications Tags , , , ,

    A usual way to collect data in a Wireless Sensor Network (WSN) is by the support of a special agent, called data mule, that moves between sensor nodes and performs all communication between them. In this work, the focus is on the construction of the route that the data mule must follow to serve all … Read more