integer programming

A Framework for Generalized Benders’ Decomposition and Its Application to Multilevel Optimization

  • Suresh Bolusani
  • Ted K. Ralphs
    • Categories (Mixed) Integer Linear Programming, Game Theory, Stochastic Programming Tags , , ,

    We describe an algorithmic framework generalizing the well-known framework originally introduced by Benders. We apply this framework to several classes of optimization problems that fall under the broad umbrella of multilevel/multistage mixed integer linear optimization problems. The development of the abstract framework and its application to this broad class of problems provides new insights and … Read more

    A Unified Framework for Multistage and Multilevel Mixed Integer Linear Optimization

  • Suresh Bolusani
  • Stefano Coniglio
  • Ted K. Ralphs
  • Sahar Tahernejad
    • Categories (Mixed) Integer Linear Programming, Game Theory, Stochastic Programming Tags , , , , ,

    We introduce a unified framework for the study of multilevel mixed integer linear optimization problems and multistage stochastic mixed integer linear optimization problems with recourse. The framework highlights the common mathematical structure of the two problems and allows for the development of a common algorithmic framework. Focusing on the two-stage case, we investigate, in particular, … Read more

    Achieving Consistency with Cutting Planes

  • Danial Davarnia
  • Atefeh Rajabalizadeh
  • John Hooker
    • Categories 0-1 Programming, Cutting Plane Approaches Tags , , , ,

    Cutting planes accelerate branch-and-bound search primarily by cutting off fractional solutions of the linear programming (LP) relaxation, resulting in tighter bounds for pruning the search tree. Yet cutting planes can also reduce backtracking by excluding inconsistent partial assignments that occur in the course of branching. A partial assignment is inconsistent with a constraint set when … Read more

    Robust Optimization with Decision-Dependent Information Discovery

  • Phebe Vayanos
  • Angelos Georghiou
  • Han Yu
    • Categories Robust Optimization Tags , , ,

    Robust optimization (RO) is a popular paradigm for modeling and solving two- and multi-stage decision-making problems affected by uncertainty. In many real-world applications, such as R&D project selection, production planning, or preference elicitation for product or policy recommendations, the time of information discovery is decision-dependent and the uncertain parameters only become observable after an often costly … Read more

    Integer Programming, Constraint Programming, and Hybrid Decomposition Approaches to Discretizable Distance Geometry Problems

  • Merve Bodur
  • Moira MacNeil
    • Categories Branch and Cut Algorithms, Integer Programming, Other Topics Tags , , , ,

    Given an integer dimension K and a simple, undirected graph G with positive edge weights, the Distance Geometry Problem (DGP) aims to find a realization function mapping each vertex to a coordinate in K-dimensional space such that the distance between pairs of vertex coordinates is equal to the corresponding edge weights in G. The so-called … Read more

    An exact algorithm for robust influence maximization

  • Giacomo Nannicini
  • Roberto Wolfler Calvo
  • Giorgio Sartor
  • Emiliano Traversi
    • Categories Branch and Cut Algorithms, Robust Optimization Tags , ,

    We propose a Branch-and-Cut algorithm for the robust influence maximization problem. The influence maximization problem aims to identify, in a social network, a set of given cardinality comprising actors that are able to influence the maximum number of other actors. We assume that the social network is given in the form of a graph with … Read more

    Arc routing with electric vehicles: dynamic charging and speed-dependent energy consumption

  • Elena Fernandez
  • Markus Leitner
  • Ivana Ljubić
  • Mario Ruthmair
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Production and Logistics Tags , , , , , ,

    Concerns about greenhouse gas emissions and government regulations foster the use of electric vehicles. Several recently published articles study the use of electric vehicles (EVs) in node-routing problems. In contrast, this article considers EVs in the context of arc routing while also addressing practically relevant aspects that have not been addressed sufficiently so far. These … Read more

    Generalized Chvatal-Gomory closures for integer programs with bounds on variables

  • Sanjeeb Dash
  • Oktay Gunluk
  • Dabeen Lee
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , , ,

    Integer programming problems that arise in practice often involve decision variables with one or two sided bounds. In this paper, we consider a generalization of Chvatal-Gomory inequalities obtained by strengthening Chvatal-Gomory inequalities using the bounds on the variables. We prove that the closure of a rational polyhedron obtained after applying the generalized Chvatal-Gomory inequalities is … Read more

    A Generic Exact Solver for Vehicle Routing and Related Problems

  • Artur Alves Pessoa
  • Ruslan Sadykov
  • Eduardo Uchoa
  • François Vanderbeck
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Modeling Languages and Systems Tags , ,

    Major advances were recently obtained in the exact solution of Vehicle Routing Problems (VRPs). Sophisticated Branch-Cut-and-Price (BCP) algorithms for some of the most classical VRP variants now solve many instances with up to a few hundreds of customers. However, adapting and reimplementing those successful algorithms for other variants can be a very demanding task. This … Read more

    Integer Programming for Learning Directed Acyclic Graphs from Continuous Data

  • Simge Küçükyavuz
  • Hasan Manzour
  • Ali Shojaie
  • Hao-Hsiang Wu
    • Categories (Mixed) Integer Linear Programming, Statistics Tags , , ,

    Learning directed acyclic graphs (DAGs) from data is a challenging task both in theory and in practice, because the number of possible DAGs scales superexponentially with the number of nodes. In this paper, we study the problem of learning an optimal DAG from continuous observational data. We cast this problem in the form of a … Read more