About QuantOM
Some projects
What is OR ?


Meetings 2014-2015

  • June 2015, Tuesday 16 (10:45 am): by Luce Brotcorne (Inria Lille – Nord Europe)

    Une approche basée sur la programmation mathématique à deux niveaux pour résoudre des problèmes de tarification

    Je présenterai tout d’abord une introduction à la programmation mathématique à deux niveaux en m’attardant tout particulièrement sur leurs potentiels à résoudre des problèmes de tarification. En effet les modèles à deux niveaux permettent de représenter des processus de décision hiérarchisé où un agent de décision (meneur) prend intrinsèquement en compte la réaction d’un autre agent (suiveur) pour atteindre son objectif.
    Ensuite je décrirai plus en détails une application dans le contexte énergétique. Dans ce cas le meneur est un fournisseur d’électricité et le suiveur est un ensemble de clients reliés à un opérateur de Smart Grid. Je concluerai après avoir discuté des résultats obtenus.

    Where: HEC-Management School of the University of Liege - 14, rue Louvrex (N1)- 4000 Liège Room 1711

  • March 2015, Friday 20 (02:00 pm): by Bernard Fortz (ULB)

    Computational strategies for a multi-period network design and routing problem

    The conventional multicommodity capacitated network design problem deals with the simultaneous optimization of capacity installation and traffic flow routing, where a fixed cost is incurred for opening a link and a linear routing cost is paid for sending traffic flow over a link.The routing decision must be performed such that traffic flows remain bounded by the installed capacities. In this talk, we generalize this problem over multiple time periods using an increasing convex cost function which takes into account congestion (number of routing paths per edge) and delay (routing path length).
    We propose a compact Mixed Integer Linear Program (MILP) formulation for this problem, based on the aggregation of traffic flows by destination following the per-destination routing decision process underlying packet networks. We observe that the resolution with realistic topologies and traffic demands becomes rapidly intractable with state-of-the-art solvers due to the weak linear programming bound of the proposed MILP formulation. We also introduce an extended formulation where traffic flows are disaggregated by source-destination pairs, while keeping the requirement of destination-based routing decisions. This extended formulation provides for all evaluated topologies stronger linear programming lower bounds than the base formulation. However, this formulation still suffers from the large size of the resulting variables and constraints sets; hence, solving the linear relaxation of the problem becomes intractable when the network size increases.
    In this talk, we investigate different computational strategies to overcome the computational limits of the formulations. We propose different branch-and-cut strategies and a Lagrangian relaxation approach.
    Joint work with Enrico Gorgone (ULB) and Dimitri Papadimitriou (Alcatel-Lucent Bell Labs)

    Where: HEC-Management School of the University of Liege - 14, rue Louvrex (N1)- 4000 Liège Room 320

  • March 2015, Tuesday 03 (10:00 am): by Serguei Iassinovski (Project Manager at Multitel)

    The Intelligent RAO Simulator

    The Intelligent RAO Simulator is a hybrid tool combining advantages of a discrete-event simulator and an expert system based on production rules.The presentation includes the RAO basics, complex system representation(elements and process), an overview of main features using simple example, demonstrative and real applications. Also, the simulation model of electricity distribution grid controlled by SCADA under a cyber attack is presented in more details (the model is developed in the frames of an FP7 research project).

    Where: HEC-Management School of the University of Liege - 14, rue Louvrex (N1)- 4000 Liège Room 025

  • January 2015, Thursday 22 (10:30 am): Kris Coolen(HEC-ULg)

    Sequential diagnosis of k-out-of-n systems with imperfect tests

    A k-out-of-n system configuration requires that, for the overall system to be functional, at least k out of the total of n components be working. We consider the problem of sequentially testing the components of a k-out-of-n system in order to learn the state of the system, when the tests are costly and when the individual component tests are imperfect, which means that a test can identify a component as working when in reality it is down, and vice versa. Each component is tested at most once. Since tests are imperfect, even when all components are tested the state of the system is not necessarily known with certainty, so we impose a threshold for the probability of correctness of the system state as a stopping criterion for the inspection (or diagnosis).
    We define different classes of inspection policies and we examine global optimality of each of the classes. We find that a globally optimal policy for diagnosing k-out-of-n systems with imperfect tests can be found in polynomial time. This result holds under certain restrictions on the values of the parameters. Of the three policy classes studied, the dominant policies always contain a global optimum, while elementary policies are compact in representation. The newly introduced class of so-called `interrupted block-walking' policies combines these merits of global optimality and of compactness.

    Where: HEC-Management School of the University of Liege - 14, rue Louvrex (N1)- 4000 Liège Room 1711

  • November 2014, Friday 28 (02:00 pm): Prof. Maurice Queyranne (Université Catholique de Louvain)

    Modeling convex subsets of points

    A subset S of a given set of points in a convexity structure is convex if every given point that is in the convex hull of S is itself in S. We are interested in modeling these convexity restrictions when the given set of points is finite. Such restrictions arise, usually in a low-dimensional space (and subject to additional constraints), in many applications, such as in mining, forestry, location, data mining, political districting, and police quadrant design. Modeling convex subset restrictions is well understood for the standard (vector space) convexity in the one-dimensional case: optimization and separation are well solved (in linear time), and a polyhedral description in the natural variables and a linear-sized ideal extended formulation are known. On the other hand, we show that the optimization problem (to find a maximum weight convex subset of given points with weights of arbitrary signs) is NP-hard for the standard convexity in dimensions three and higher, and inapproximable when the dimension is part of the input. For the two-dimensional (planar) case, by Carathéodory's Theorem convexity can be enforced by a polynomial (quartic) number of linear inequalities in the natural binary variables, but the resulting formulation is very weak. We present a compact (i.e., polynomial-size) ideal extended formulation, which is related to the cubic-time dynamic programming optimization algorithm of Bautista-Santiago et al. (2011). We seek more compact or tighter formulations and faster separation algorithms, that could be used for more complex optimization problems with convex subsets of given points. We also consider these questions in related convexity structures.
    (This talk will report on past and current work with numerous co-authors.)

    Where: HEC-Management School of the University of Liege - 14, rue Louvrex (N1)- 4000 Liège Room 119

  • October 2014, Thursday 16 (01:00 pm): Kris Braekers (Hasselt University)

    A bi-objective homecare scheduling problem: analyzing the trade-off between costs and patient convenience

    A homecare scheduling problem in which a set of nurses has to visit a set of patients to perform home- and healthcare activities at patients’ home locations is studied. The problem may be considered as a vehicle routing problem with many side constraints such as time windows, nurse working times, nurse-patient incompatibilities, multiple transportation modes and preferences of patients regarding visit times and nurses. Our goal is to analyze the trade-off between the operating costs of the company offering these services and the level of patient convenience offered. For this purpose a bi-objective optimization problem has been defined, minimizing travel and overtime costs, and minimizing deviation from patient preferences. Small problem instances have been solved exactly using a MIP formulation. To solve larger instances, a meta-heuristic approach based on the Multi-Directional Local Search framework, using Large Neighborhood Search as a subheuristic, has been developed. This meta-heuristic method will be discussed and experimental results will be presented.
    This is a joint work with Sophie Parragh and Fabien Tricoire from the University of Vienna

    Where: HEC-Management School of the University of Liege - 14, rue Louvrex (N1)- 4000 Liège Room 1715

  • September 2014, Monday 15 (10:30 am): Thibaut Lust (Université Pierre et Marie Curie)

    Multiobjective combinatorial optimization: current and future challenges

    Many real optimization problems are multiobjective by nature, involving conflicting objectives. In a multiobjective formulation, a solution simultaneously minimizing each objective does not exist, we have instead a set of solutions called Pareto optimal solutions. A Pareto optimal solution is a solution for which it is impossible to find another solution that dominates it, that is at least as good on all objectives and better for at least one objective. In this talk, we will present the pros and cons of multiobjective formulations through the difficulties of generating all Pareto optimal solutions of multiobjective combinatorial optimization problems (multiobjective knapack problems, multiobjective traveling salesman problems, etc.) Other formulations than Pareto optimization will be presented (by using Lorenz dominance, Choquet integral) and new research challenges around multiobjective optimization will be presented.

    Where: HEC-Management School of the University of Liege - 14, rue Louvrex (N1)- 4000 Liège Room 120

  HEC-Management School - University of Liège