Martine Labbé

Closing the Gap in Linear Bilevel Optimization: A New Valid Primal-Dual Inequality

  • Thomas Kleinert
  • Martine Labbé
  • Martin Schmidt
  • Fränk Plein
    • Categories (Mixed) Integer Linear Programming, Complementarity and Variational Inequalities, Cutting Plane Approaches Tags , , ,

    Linear bilevel optimization problems are often tackled by replacing the linear lower-level problem with its Karush–Kuhn–Tucker (KKT) conditions. The resulting single-level problem can be solved in a branch-and-bound fashion by branching on the complementarity constraints of the lower-level problem’s optimality conditions. While in mixed-integer single-level optimization branch- and-cut has proven to be a powerful extension … Read more

    Deciding Feasibility of a Booking in the European Gas Market on a Cycle is in P for the Case of Passive Networks

  • Martine Labbé
  • Martin Schmidt
  • Johannes Thürauf
  • Fränk Plein
    • Categories Applications - OR and Management Sciences, Network Optimization Tags , , , , ,

    We show that the feasibility of a booking in the European entry-exit gas market can be decided in polynomial time on single-cycle networks that are passive, i.e., do not contain controllable elements. The feasibility of a booking can be characterized by solving polynomially many nonlinear potential-based flow models for computing so-called potential-difference maximizing load flow … Read more

    There’s No Free Lunch: On the Hardness of Choosing a Correct Big-M in Bilevel Optimization

  • Thomas Kleinert
  • Martine Labbé
  • Martin Schmidt
  • Fränk Plein
    • Categories (Mixed) Integer Linear Programming, Complementarity and Variational Inequalities Tags , , , ,

    One of the most frequently used approaches to solve linear bilevel optimization problems consists in replacing the lower-level problem with its Karush-Kuhn-Tucker (KKT) conditions and by reformulating the KKT complementarity conditions using techniques from mixed-integer linear optimization. The latter step requires to determine some big-M constant in order to bound the lower level’s dual feasible … Read more

    Bookings in the European Gas Market: Characterisation of Feasibility and Computational Complexity Results

  • Martine Labbé
  • Martin Schmidt
  • Fränk Plein
    • Categories Applications - OR and Management Sciences, Dynamic Programming, Network Optimization Tags , , , , ,

    As a consequence of the liberalisation of the European gas market in the last decades, gas trading and transport have been decoupled. At the core of this decoupling are so-called bookings and nominations. Bookings are special capacity right contracts that guarantee that a specified amount of gas can be supplied or withdrawn at certain entry … Read more

    Load Scheduling for Residential Demand Response on Smart Grids

  • Miguel F. Anjos
  • Luce Brotcorne
  • Martine Labbé
  • Maria I. Restrepo
    • Categories (Mixed) Integer Linear Programming, Energy Tags , , ,

    The residential load scheduling problem is concerned with finding an optimal schedule for the operation of residential loads so as to minimize the total cost of energy while aiming to respect a prescribed limit on the power level of the residence. We propose a mixed integer linear programming formulation of this problem that accounts for … Read more

    Novel formulations for general and security Stackelberg games

  • Carlos Casorrán
  • Bernard Fortz
  • Martine Labbé
  • Fernando Ordóñez
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Polyhedra Tags , , ,

    In this paper we analyze general Stackelberg games (SGs) and Stackelberg security games (SSGs). SGs are hierarchical adversarial games where players select actions or strategies to optimize their payoffs in a sequential manner. SSGs are a type of SGs that arise in security applications, where the strategies of the player that acts first consist in … Read more

    Lagrangian relaxation for SVM feature selection

  • Manlio Gaudioso
  • Enrico Gorgone
  • Martine Labbé
  • Antonio M. Rodríguez-Chía
    • Categories (Mixed) Integer Linear Programming Tags , , ,

    We discuss a Lagrangian-relaxation-based heuristics for dealing with feature selection in a standard L1 norm Support Vector Machine (SVM) framework for binary classification. The feature selection model we adopt is a Mixed Binary Linear Programming problem and it is suitable for a Lagrangian relaxation approach. Based on a property of the optimal multiplier setting, we … Read more

    An exact approach to the problem of extracting an embedded network matrix

  • Cid C. de Souza
  • Martine Labbé
  • R. M. V. Figueiredo
    • Categories Branch and Cut Algorithms, Network Optimization, Polyhedra Tags , , ,

    We study the problem of detecting a maximum embedded network submatrix in a {-1,0,+1}-matrix. Our aim is to solve the problem to optimality. We introduce a 0-1 integer linear formulation for this problem based on its representation over a signed graph. A polyhedral study is presented and a branch-and-cut algorithm is described for finding an … Read more

    On generalized network design polyhedra

  • Corinne Feremans
  • Martine Labbé
  • Adam N. Letchford
  • Juan-José Salazar-González
    • Categories 0-1 Programming, Polyhedra, Telecommunications Tags , ,

    In recent years, there has been an increased literature on so-called Generalized Network Design Problems, such as the Generalized Minimum Spanning Tree Problem and the Generalized Traveling Salesman Problem. In such problems, the node set of a graph is partitioned into clusters, and the feasible solutions must contain one node from each cluster. Up to … Read more

    Valid inequalities and Branch-and-Cut for the Clique Pricing Problem

  • Géraldine Heilporn
  • Martine Labbé
  • Patrice Marcotte
  • Gilles Savard
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms Tags ,

    Motivated by an application in highway pricing, we consider the problem that consists in setting profit-maximizing tolls on a clique subset of a multicommodity transportation network. Following a proof that clique pricing is NP-hard, we propose strong valid inequalities, some of which define facets of the 2-commodity polyhedron. The numerical efficiency of these inequalities is … Read more