Symposium in Artificial Intelligence, Data Analytics and Optimization and PhD defense of Tu San Pham

Location: room 00.21A, IICK building, KU Leuven, campus Kortrijk, Etienne Sabbelaan 53, 8500 Kortrijk

Date: 10th and 11th, March, 2020

We are pleased to announce the symposium organized at KU Leuven, campus Kortrijk on the 10th and 11th of March. 

We will have six speakers along with a poster session with the participants from different groups from Kortrijk, Ghent, Lille, Rotterdam and Bielefeld, followed by the PhD defense of Tu San Pham.

Please help us to organize the event better by informing us about your attendant using this link registration

The detailed program:

Time	Program
Tuesday 10/3
14:00-14:45	Kevin Tierney, Neural Large Neighborhood Search for Vehicle Routing Problems
14:45 – 15:30	Michael Römer, Modeling Multiactivity Shift Scheduling Problems with State-Expanded Networks
15:30-16:30	Coffee break and poster session
16:30 – 17:15	Dimitri Papadimitriou,Machine Learning methods meeting Data Assimilation
17:15-18:00	Ilker Birbil, Data Privacy in Bid-Price Control for Network Revenue Management
Wednesday 11/3
09:00-09:45	Laetitia Jourdan, Multi-objective optimization for knowledge discovery in big data
09:45 – 10:30	Louis Martin Rousseau, Improving Optimization Bounds using Machine Learning: Decision Diagrams meet Deep Reinforcement Learning
10:30 – 11:00	Coffee break
11:00 – 14:00	PhD defense of Tu San Pham, Formal, exact and metaheuristic methods for combinatorial optimization

 

The list of speakers along with the abstracts of their talks can be found below.

1. Kevin Tierney, Universität Bielefeld, Neural Large Neighborhood Search for Vehicle Routing Problems

Learning how to automatically solve optimization problems has the potential to provide the next big leap in optimization technology. The performance of automatically learned heuristics on routing problems has been steadily improving in recent years, but approaches based purely on machine learning are still outperformed by state-of-the-art optimization methods. To close this performance gap, we propose a novel large neighborhood search (LNS) framework for vehicle routing that integrates learned heuristics for generating new solutions. The learning mechanism is based on a deep neural network with an attention mechanism and has been especially designed to be integrated into an LNS search setting. We evaluate our approach on the capacitated vehicle routing problem (CVRP) and the split delivery vehicle routing problem (SDVRP). On CVRP instances with up to 297 customers our approach significantly outperforms an LNS that uses only handcrafted heuristics and a well-known heuristic from the literature. Furthermore, we show for the CVRP and the SDVRP that our approach surpasses the performance of existing machine learning approaches and comes close to the performance of state-of-the-art optimization approaches.

 

2. Michael Römer, Universität Bielefeld,  Modeling Multiactivity Shift Scheduling Problems with State-Expanded Networks

In this talk, we propose a new MILP formulation for multi-activity shift scheduling problems based on aggregated flows in state-expanded networks. We discuss the relation of the new formulation to other formulations relying on graphical optimizations models based on formal languages such as context-free grammars or deterministic finite automata. In addition, we present computational results with well-known instances showing that the novel formulation yields both smaller MILP models and in most cases faster solution times than the other model types, including implicit grammar-based models.

3. Dimitri Papadimitriou, University of Antwerp, Machine Learning methods meeting Data Assimilation

Data assimilation is the process of combining time ordered observation data with numerical model to i) produce accurate/optimal characterization of current model state (state modeling) and ii) predict observations given a model state and the temporal evolution in time of model states (state prediction). This method finds a wide spectrum of applicability from geophysics/climatology to biophysics to obtain well initialized short-term numerical forecasts combined with observation analysis. In this context, sequential data assimilation aims at finding at every assimilation step an analysis/model state x_a that explains the observation y. The handling of such (nonlinear inverse) problem involves the solving of the (ill-posed) nonlinear operator equation y = H(x_a), where H is the nonlinear time-invariant observation operator (mapping from state into observation space). To provide stable approximates to such ill-posed nonlinear operator equation and avoid numerical instability when inverting ill-conditioned matrix, this paper develops a regularization method based on penalization by total variation. Motivated by the nonlinearity of the problem, an iterative method (to total variation) is combined with nonlinearity approximation for solving such nonlinear inverse problems. It then compares it to neural-learning based method; thus, instead of involving physics-based method for the solving of the inverse problem, a direct method is considered that approximates the inverse nonlinear time-invariant observation operator $H^{-1}$. Computational and convergence analysis in presence of noisy data and numerical results involving advection-diffusion-reaction phenomena are then presented.

 

4.  Ilker Birbil, Erasmus University, Rotterdam, Data Privacy in Bid-Price Control for Network Revenue Management

We present a network revenue management problem where multiple parties agree to share some of the capacities of the network. This collaboration is performed by constructing a large mathematical programming model available to all parties. The parties then use the solution of this model in their own bid-price control systems. In this setting, the major concern for the parties is the privacy of their input data and the optimal solutions containing their individual decisions. To address this concern, we propose an approach based on solving an alternative data-private model constructed with input masking and random transformations. Our main result shows that each party can safely recover only its own optimal decisions after the same data-private model is solved by each party. We also discuss several special cases where possible privacy leakage would require attention. Observing that the dense data-private model may take more time to solve than the sparse original non-private model, we further propose a modeling approach that introduces sparsity into the data-private model. We support our results with a simulation study where we use a real-world network structure. The talk ends with a discussion on a decomposition approach that we have recently started to work on.

 

5. Laetitia Jourdan, Université de Lille, Multi-objective optimization for knowledge discovery in big data

Classical knowledge discovery tasks, such that classification, feature selection, association rules mining may be seen as multi-objective combinatorial optimization problems. Indeed, in many cases, some elements have to be combined to produce the solution that may be evaluated thanks to several quality criteria (it is usually necessary to maximize the specificity of the extracted knowledge while maximizing its generality to be applicable).

Hence efficient multi-objective optimization techniques may contribute to extract interesting knowledge from datasets. In a context of big data, some additional specificities have to be taken into account, and metaheuristics are well suited to address them.

In this presentation, I will focus on how knowledge discovery tasks may be modelled as multi-objective optimization problems and give some insight on how to solve them. I will also focus on the use of optimisation and multi-objective optimisation to realise the knowledge discovery pipeline (MO-AutoML). 

 

6. Louis Martin Rousseau, Polytechnique de Montréal, Improving Optimization Bounds using Machine Learning: Decision Diagrams meet Deep Reinforcement Learning

Prescriptive analytics, which has optimization at its core, provides organizations with scalable software for large-scale automated decision-making.  Combinatorial optimization algorithms rely heavily on generic methods for identifying tight bonds, which provide both solutions to problems and optimality guarantees. One broad class of algorithms is dynamic programming (DP), which often leverages approximate dynamic programming (ADP) to cope with the well-known “curse of dimensionality” and to provide objective function bounds. This paper studies how machine learning (ML), and more specifically deep reinforcement learning (DRL), can be used to improve bounds provided by ADP models, in particular through learning variable ordering for decision diagrams which represent the ADP. The DRL models introduced lead to improved primal and dual bounds, even over linear programming relaxation. The contributions of this paper are (1) a novel and generic mechanism for utilizing ML to obtain high-quality heuristic solutions and, (2) one of the first applications of ML to improve DP relaxation bounds in a generic fashion.  We apply the methods to classic optimization problems, and exhibit through computational testing that optimization bounds can be significantly improved through DRL.