integer programming

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

    A Method for Convex Black-Box Integer Global Optimization

  • Jeffrey Larson
  • Sven Leyffer
  • Prashant Palkar
  • Stefan M. Wild
    • Categories Convex Optimization Tags , , ,

    We study the problem of minimizing a convex function on the integer lattice when the function cannot be evaluated at noninteger points. We propose a new underestimator that does not require access to (sub)gradients of the objective but, rather, uses secant linear functions that interpolate the objective function at previously evaluated points. These linear mappings … Read more

    A Computational Comparison of Optimization Methods for the Golomb Ruler Problem

  • Burak Kocuk
  • Willem-Jan van Hoeve
    • Categories Integer Programming Tags , ,

    The Golomb ruler problem is defined as follows: Given a positive integer n, locate n marks on a ruler such that the distance between any two distinct pair of marks are different from each other and the total length of the ruler is minimized. The Golomb ruler problem has applications in information theory, astronomy and … Read more

    Identifying the Optimal Value Function of a Negative Markov Decision Process: An Integer Programming Approach

  • Amin Dehghanian
    • Categories (Mixed) Integer Linear Programming, Dynamic Programming Tags , , ,

    Mathematical programming formulation to identify the optimal value function of a negative Markov decision process (MDP) is non-convex, non-smooth, and computationally intractable. Also note that other well-known solution methods of MDP do not work properly for a negative MDP. More specifically, the policy iteration diverges, and the value iteration converges but does not provide an … Read more