Martine Labbé

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

    Stochastic binary problems with simple penalties for capacity constraints violations

  • Bernard Fortz
  • Martine Labbé
  • Michael Poss
  • F Louveaux
    • Categories (Mixed) Integer Nonlinear Programming, Stochastic Programming Tags , , , ,

    This paper studies stochastic programs with first-stage binary variables and capacity constraints, using simple penalties for capacities violations. In particular, we take a closer look at the knapsack problem with weights and capacity following independent random variables and prove that the problem is weakly \NP-hard in general. We provide pseudo-polynomial algorithms for three special cases … Read more

    A parallel between two classes of pricing problems in transportation and economics

  • Géraldine Heilporn
  • Martine Labbé
  • Patrice Marcotte
  • Gilles Savard
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences Tags , ,

    In this work, we establish a parallel between two classes of pricing problems that have attracted the attention of researchers in economics, theoretical computer science and operations research, each community addressing issues from its own vantage point. More precisely, we contrast the problems of pricing a network or a product line, in order to achieve … Read more