

Meetings 20142015
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: HECManagement 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 multiperiod 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 perdestination routing decision process underlying packet networks. We observe that the resolution with realistic topologies and
traffic demands becomes rapidly intractable with stateoftheart 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 sourcedestination pairs, while keeping the
requirement of destinationbased 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 branchandcut strategies and a Lagrangian relaxation approach.
Joint work with Enrico Gorgone (ULB) and Dimitri Papadimitriou (AlcatelLucent Bell Labs)
Where: HECManagement 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 discreteevent 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: HECManagement School of the University of Liege  14, rue Louvrex (N1) 4000 Liège Room 025
January 2015, Thursday 22 (10:30 am): Kris Coolen(HECULg)
Sequential diagnosis of koutofn systems with imperfect tests
A koutofn 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 koutofn 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 koutofn 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 socalled `interrupted blockwalking' policies combines these merits of global optimality and of compactness.
Where: HECManagement 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 lowdimensional 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 onedimensional case: optimization and separation are well solved (in linear time), and a polyhedral description in the natural variables and a linearsized 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 NPhard for the standard convexity in dimensions three and higher, and inapproximable when the dimension is part of the input. For the twodimensional (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., polynomialsize) ideal extended formulation, which is related to the cubictime dynamic programming optimization algorithm of BautistaSantiago 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 coauthors.)
Where: HECManagement 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 biobjective homecare scheduling problem: analyzing the tradeoff 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, nursepatient incompatibilities, multiple transportation modes and preferences of patients regarding visit times and nurses. Our goal is to analyze the tradeoff between the operating costs of the company offering these services and the level of patient convenience offered. For this purpose a biobjective 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 metaheuristic approach based on the MultiDirectional Local Search framework, using Large Neighborhood Search as a subheuristic, has been developed. This metaheuristic 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: HECManagement 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: HECManagement School of the University of Liege  14, rue Louvrex (N1) 4000 Liège Room 120

