Branch and Cut Algorithms

A Bilevel Approach for Identifying the Worst Contingencies for Nonconvex Alternating Current Power Systems

  • Brian Dandurand
  • Kibaek Kim
  • Sven Leyffer
    • Categories (Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms, Robust Optimization Tags , , ,

    We address the bilevel optimization problem of identifying the most critical attacks to an alternating current (AC) power flow network. The upper-level binary maximization problem consists in choosing an attack that is treated as a parameter in the lower-level defender minimization problem. Instances of the lower-level global minimization problem by themselves are NP-hard due to … Read more

    Integer Programming Formulations for Minimum Spanning Tree Interdiction

  • Foad Mahdavi Pajou
  • Jose L. Walteros
  • Ningji Wei
    • Categories Branch and Cut Algorithms, Integer Programming, Network Optimization Tags , , ,

    We consider a two-player interdiction problem staged over a graph where the leader’s objective is to minimize the cost of removing edges from the graph so that the follower’s objective, i.e., the weight of a minimum spanning tree in the residual graph, is increased up to a predefined level $r$. Standard approaches for graph interdiction … 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

    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

    A Solution Approach to Distributionally Robust Chance-Constrained Assignment Problems

  • Jinlin Li
  • Sanjay Mehrotra
  • Shanshan Wang
    • Categories Applications - OR and Management Sciences, Branch and Cut Algorithms, Scheduling

    We study assignment problem with chance constraints (CAP) and its distributionally robust counterpart (DR-CAP). We present a technique for estimating big-M in such a formulation that takes advantage of the ambiguity set. We consider a 0-1 bilinear knapsack set to develop valid inequalities for CAP and DR-CAP. This is generalized to the joint chance constraint … Read more

    An Iterative Graph Expansion Approach for the Scheduling and Routing of Airplanes

  • Armin Fügenschuh
  • Fabian Gnegel
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Transportation Tags , , ,

    A tourism company that offers fly-in safaris is faced with the challenge to route and schedule its fleet of airplanes in an optimal way. Over the course of a given time horizon several groups of tourists have to be picked up at airports and flown to their destinations within a certain time-window. Furthermore the number … Read more

    On the depth of cutting planes

  • Laurent Poirrier
  • James Yu
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Cutting Plane Approaches Tags , ,

    We introduce a natural notion of depth that applies to individual cutting planes as well as entire families. This depth has nice properties that make it easy to work with theoretically, and we argue that it is a good proxy for the practical strength of cutting planes. In particular, we show that its value lies … Read more

    A branch and cut algorithm for the time-dependent profitable tour problem with resource constraints

  • Gonzalo Lera-Romero
  • Juan José Miranda-Bront
    • Categories Branch and Cut Algorithms, Transportation

    In this paper we study the time-dependent profitable tour problem with resource con-straints (TDPTPRC), a generalization of the profitable tour problem (PTP) which includes variable travel times to account for road congestion. In this problem, the set of customers to be served is not given and must be determined based on the profit collected when … Read more

    A scalable mixed-integer decomposition approach for optimal power system restoration

  • Ignacio Aravena
  • Shmuel Oren
  • Deepak Rajan
  • Georgios Patsakis
  • Jennifer Rios
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Energy Tags , , ,

    The optimal restoration problem lies at the foundation of the evaluation and improvement of resilience in power systems. In this paper we present a scalable decomposition algorithm, based on the integer L-shaped method, for solving this problem for realistic power systems. The algorithm works by partitioning the problem into a master problem and a slave … Read more