Pascal Van Hentenryck

JAIR Journal 2026 Journal Article

Integrating Column Generation and Large Neighborhood Search for Bus Driver Scheduling with Complex Break Constraints

• Lucas Kletzander
• Tommaso Mannelli Mazzoli
• Nysret Musliu
• Pascal Van Hentenryck

Background: The Bus Driver Scheduling Problem (BDSP) is a combinatorial optimization problem with the goal to design shifts to cover prearranged bus tours. The objective takes into account the operational cost as well as the satisfaction of drivers. This problem is heavily constrained due to strict legal rules and collective agreements. Objectives: The objective of this article is to provide state-of-the-art exact and hybrid solution methods that can provide high-quality solutions for instances of different sizes. Methods: This work presents a comprehensive study of both an exact method, Branch and Price (B&P), as well as a Large Neighborhood Search (LNS) framework which uses B&P or Column Generation (CG) for the repair phase to solve the BDSP. It further proposes and evaluates a novel deeper integration of B&P and LNS, storing the generated columns from the LNS subproblems and reusing them for other subproblems, or to find better global solutions. Results: The article presents a detailed analysis of several components of the solution methods and their impact, including general improvements for the B&P subproblem, which is a high-dimensional Resource Constrained Shortest Path Problem (RCSPP), and the components of the LNS. The evaluation shows that our approach provides new state-of-the-art results for instances of all sizes, including exact solutions for small instances, and low gaps to a known lower bound for mid-sized instances. Conclusions: We observe that B&P provides the best results for small instances, while the tight integration of LNS and CG can provide high-quality solutions for larger instances, further improving over LNS which just uses CG as a black box. The proposed methods are general and can also be applied to other rule sets and related optimization problems.

AAAI Conference 2025 Conference Paper

Contextual Stochastic Optimization for School Desegregation Policymaking

• Hongzhao Guan
• Nabeel Gillani
• Tyler Simko
• Jasmine Mangat
• Pascal Van Hentenryck

Most US school districts draw geographic "attendance zones" to assign children to schools based on their home address, a process that can replicate existing neighborhood racial/ethnic and socioeconomic status (SES) segregation in schools. Redrawing boundaries can reduce segregation, but estimating expected rezoning impacts is often challenging because families can opt-out of their assigned schools. This paper seeks to alleviate this societal problem by developing a joint redistricting and choice modeling framework, called redistricting with choices (RWC). The RWC framework is applied to a large US public school district to estimate how redrawing elementary school boundaries might realistically impact levels of socioeconomic segregation. The main methodological contribution of RWC is a contextual stochastic optimization model that aims to minimize district-wide segregation by integrating rezoning constraints with a machine learning-based school choice model. The study finds that RWC yields boundary changes that might reduce segregation by a substantial amount (23%) -- but doing so might require the re-assignment of a large number of students, likely to mitigate re-segregation that choice patterns could exacerbate. The results also reveal that predicting school choice is a challenging machine learning problem. Overall, this study offers a novel practical framework that both academics and policymakers might use to foster more diverse and integrated schools.

ICML Conference 2024 Conference Paper

Compact Optimality Verification for Optimization Proxies

• Wenbo Chen 0001
• Haoruo Zhao
• Mathieu Tanneau
• Pascal Van Hentenryck

Recent years have witnessed increasing interest in optimization proxies, i. e. , machine learning models that approximate the input-output mapping of parametric optimization problems and return near-optimal feasible solutions. Following recent work by (Nellikkath & Chatzivasileiadis, 2021), this paper reconsiders the optimality verification problem for optimization proxies, i. e. , the determination of the worst-case optimality gap over the instance distribution. The paper proposes a compact formulation for optimality verification and a gradient-based primal heuristic that brings significant computational benefits to the original formulation. The compact formulation is also more general and applies to non-convex optimization problems. The benefits of the compact formulation are demonstrated on large-scale DC Optimal Power Flow and knapsack problems.

NeurIPS Conference 2024 Conference Paper

Dual Lagrangian Learning for Conic Optimization

• Mathieu Tanneau
• Pascal Van Hentenryck

This paper presents Dual Lagrangian Learning (DLL), a principled learning methodology for dual conic optimization proxies. DLL leverages conic duality and the representation power of ML models to provide high-duality, dual-feasible solutions, and therefore valid Lagrangian dual bounds, for linear and nonlinear conic optimization problems. The paper introduces a systematic dual completion procedure, differentiable conic projection layers, and a self-supervised learning framework based on Lagrangian duality. It also provides closed-form dual completion formulae for broad classes of conic problems, which eliminate the need for costly implicit layers. The effectiveness of DLL is demonstrated on linear and nonlinear conic optimization problems. The proposed methodology significantly outperforms a state-of-the-art learning-based method, and achieves 1000x speedups over commercial interior-point solvers with optimality gaps under 0. 5\% on average.

IJCAI Conference 2024 Conference Paper

Empathy and AI: Achieving Equitable Microtransit for Underserved Communities

• Eleni Bardaka
• Pascal Van Hentenryck
• Crystal Chen Lee
• Christopher B. Mayhorn
• Kai Monast
• Samitha Samaranayake
• Munindar P. Singh

This paper describes a newly launched project that will produce a new approach to public microtransit for underserved communities. Public microtransit cannot rely on pricing signals to manage demand, and current approaches face the challenges of simultaneously being underutilized and overextended. This project conceives of the setting as a sociotechnical system. Its main idea is to engage users through AI agents in conjunction with platform constraints to find solutions that purely technical conceptions cannot find. The project was specified over an intense series of discussions with key stakeholders (riders, city government, and nongovernmental agencies) and brings together expertise in the disciplines of AI, Operations Research, Urban Planning, Psychology, and Community Development. The project will culminate in a pilot study, results from which will facilitate the transfer of its technology to additional communities.

AAAI Conference 2024 Conference Paper

Finding ε and δ of Traditional Disclosure Control Systems

• Saswat Das
• Keyu Zhu
• Christine Task
• Pascal Van Hentenryck
• Ferdinando Fioretto

This paper analyzes the privacy of traditional Statistical Disclosure Control (SDC) systems under a differential privacy interpretation. SDCs, such as cell suppression and swapping, promise to safeguard the confidentiality of data and are routinely adopted in data analyses with profound societal and economic impacts. Through a formal analysis and empirical evaluation of demographic data from real households in the U.S., the paper shows that widely adopted SDC systems not only induce vastly larger privacy losses than classical differential privacy mechanisms, but, they may also come at a cost of larger accuracy and fairness.

ICAPS Conference 2024 Conference Paper

Investigating Large Neighbourhood Search for Bus Driver Scheduling

• Tommaso Mannelli Mazzoli
• Lucas Kletzander
• Pascal Van Hentenryck
• Nysret Musliu

The Bus Driver Scheduling Problem (BDSP) is a combinatorial optimisation problem with high practical relevance. The aim is to assign bus drivers to predetermined routes while minimising a specified objective function that considers operating costs as well as employee satisfaction. Since we must satisfy several rules from a collective agreement and European regulations, the BDSP is highly constrained. Hence, using exact methods to solve large real-life-based instances is computationally too expensive, while heuristic methods still have a considerable gap to the optimum. Our paper presents a Large Neighbourhood Search (LNS) approach to solve the BDSP. We propose several novel destroy operators and an approach using column generation to repair the sub-problem. We analyse the impact of the destroy and repair operators and investigate various possibilities to select them, including adaptivity. The proposed approach improves all the upper bounds for larger instances that exact methods cannot solve, as well as for some mid-sized instances, and outperforms existing heuristic approaches for this problem on all benchmark instances.

ECAI Conference 2024 Conference Paper

Learning Joint Models of Prediction and Optimization

• James Kotary
• Vincenzo Di Vito Francesco
• Jacob K. Christopher
• Pascal Van Hentenryck
• Ferdinando Fioretto

The Predict-Then-Optimize framework uses machine learning models to predict unknown parameters of an optimization problem from exogenous features before solving. This setting is common to many real-world decision processes, and recently it has been shown that decision quality can be substantially improved by solving and differentiating the optimization problem within an end-to-end training loop. However, this approach requires significant computational effort in addition to handcrafted, problem-specific rules for backpropagation through the optimization step, challenging its applicability to a broad class of optimization problems. This paper proposes an alternative method, in which optimal solutions are learned directly from the observable features by joint predictive models. The approach is generic, and based on an adaptation of the Learning-to-Optimize paradigm, from which a rich variety of existing techniques can be employed. Experimental evaluations show the ability of several Learning-to-Optimize methods to provide efficient and accurate solutions to an array of challenging Predict-Then-Optimize problems.

IJCAI Conference 2024 Conference Paper

On the Effects of Fairness to Adversarial Vulnerability

• Cuong Tran
• Keyu Zhu
• Pascal Van Hentenryck
• Ferdinando Fioretto

Fairness and robustness are two important notions of learning models. Fairness ensures that models do not disproportionately harm (or benefit) some groups over others, while robustness measures the models' resilience against small input perturbations. While equally important properties, this paper illustrates a dichotomy between fairness and robustness, and analyzes when striving for fairness decreases the model robustness to adversarial samples. The reported analysis sheds light on the factors causing such contrasting behavior, suggesting that distance to the decision boundary across groups as a key factor. Experiments on non-linear models and different architectures validate the theoretical findings. In addition to the theoretical analysis, the paper also proposes a simple, yet effective, solution to construct models achieving good tradeoffs between fairness and robustness.

IJCAI Conference 2023 Conference Paper

Reinforcement Learning from Optimization Proxy for Ride-Hailing Vehicle Relocation (Extended Abstract)

• Enpeng Yuan
• Wenbo Chen
• Pascal Van Hentenryck

Idle vehicle relocation is crucial for addressing demand-supply imbalance that frequently arises in the ride-hailing system. Current mainstream methodologies - optimization and reinforcement learning - suffer from obvious computational drawbacks. Optimization models need to be solved in real-time and often trade off model fidelity (hence quality of solutions) for computational efficiency. Reinforcement learning is expensive to train and often struggles to achieve coordination among a large fleet. This paper designs a hybrid approach that leverages the strengths of the two while overcoming their drawbacks. Specifically, it trains an optimization proxy, i. e. , a machine-learning model that approximates an optimization model, and refines the proxy with reinforcement learning. This Reinforcement Learning from Optimization Proxy (RLOP) approach is efficient to train and deploy, and achieves better results than RL or optimization alone. Numerical experiments on the New York City dataset show that the RLOP approach reduces both the relocation costs and computation time significantly compared to the optimization model, while pure reinforcement learning fails to converge due to computational complexity.

AAAI Conference 2023 Conference Paper

Self-Supervised Primal-Dual Learning for Constrained Optimization

• Seonho Park
• Pascal Van Hentenryck

This paper studies how to train machine-learning models that directly approximate the optimal solutions of constrained optimization problems. This is an empirical risk minimization under constraints, which is challenging as training must balance optimality and feasibility conditions. Supervised learning methods often approach this challenge by training the model on a large collection of pre-solved instances. This paper takes a different route and proposes the idea of Primal-Dual Learning (PDL), a self-supervised training method that does not require a set of pre-solved instances or an optimization solver for training and inference. Instead, PDL mimics the trajectory of an Augmented Lagrangian Method (ALM) and jointly trains primal and dual neural networks. Being a primal-dual method, PDL uses instance-specific penalties of the constraint terms in the loss function used to train the primal network. Experiments show that, on a set of nonlinear optimization benchmarks, PDL typically exhibits negligible constraint violations and minor optimality gaps, and is remarkably close to the ALM optimization. PDL also demonstrated improved or similar performance in terms of the optimality gaps, constraint violations, and training times compared to existing approaches.

IJCAI Conference 2023 Conference Paper

SF-PATE: Scalable, Fair, and Private Aggregation of Teacher Ensembles

• Cuong Tran
• Keyu Zhu
• Ferdinando Fioretto
• Pascal Van Hentenryck

A critical concern in data-driven processes is to build models whose outcomes do not discriminate against some protected groups. In learning tasks, knowledge of the group attributes is essential to ensure non-discrimination, but in practice, these attributes may not be available due to legal and ethical requirements. To address this challenge, this paper studies a model that protects the privacy of individuals’ sensitive information while also allowing it to learn non-discriminatory predictors. A key feature of the proposed model is to enable the use of off-the-shelves and non-private fair models to create a privacy-preserving and fair model. The paper analyzes the relation between accuracy, privacy, and fairness, and assesses the benefits of the proposed models on several prediction tasks. In particular, this proposal allows both scalable and accurate training of private and fair models for very large neural networks.

IJCAI Conference 2022 Conference Paper

Differential Privacy and Fairness in Decisions and Learning Tasks: A Survey

• Ferdinando Fioretto
• Cuong Tran
• Pascal Van Hentenryck
• Keyu Zhu

This paper surveys the recent work in the intersection of differential privacy (DP) and fairness. It focuses on surveying the work observing that DP systems may exacerbate bias and disparate impacts for different groups of individuals. The survey reviews the conditions under which privacy and fairness may be aligned or contrasting goals, analyzes how and why DP exacerbates bias and unfairness in decision problems and learning tasks, and reviews the available solutions to mitigate the fairness issues arising in DP systems. The survey provides a unified understanding of the main challenges and potential risks arising when deploying privacy-preserving machine learning or decisions making tasks under a fairness lens.

AAAI Conference 2022 Conference Paper

Fast Approximations for Job Shop Scheduling: A Lagrangian Dual Deep Learning Method

• James Kotary
• Ferdinando Fioretto
• Pascal Van Hentenryck

The Jobs shop Scheduling Problem (JSP) is a canonical combinatorial optimization problem that is routinely solved for a variety of industrial purposes. It models the optimal scheduling of multiple sequences of tasks, each under a fixed order of operations, in which individual tasks require exclusive access to a predetermined resource for a specified processing time. The problem is NP-hard and computationally challenging even for medium-sized instances. Motivated by the increased stochasticity in production chains, this paper explores a deep learning approach to deliver efficient and accurate approximations to the JSP. In particular, this paper proposes the design of a deep neural network architecture to exploit the problem structure, its integration with Lagrangian duality to capture the problem constraints, and a post-processing optimization to guarantee solution feasibility. The resulting method, called JSP-DNN, is evaluated on hard JSP instances from the JSPLIB benchmark library. Computational results show that JSP-DNN can produce JSP approximations of high quality at negligible computational costs.

IJCAI Conference 2022 Conference Paper

Post-processing of Differentially Private Data: A Fairness Perspective

• Keyu Zhu
• Ferdinando Fioretto
• Pascal Van Hentenryck

Post-processing immunity is a fundamental property of differential privacy: it enables arbitrary data-independent transformations to differentially private outputs without affecting their privacy guarantees. Post-processing is routinely applied in data-release applications, including census data, which are then used to make allocations with substantial societal impacts. This paper shows that post-processing causes disparate impacts on individuals or groups and analyzes two critical settings: the release of differentially private datasets and the use of such private datasets for downstream decisions, such as the allocation of funds informed by US Census data. In the first setting, the paper proposes tight bounds on the unfairness for traditional post-processing mechanisms, giving a unique tool to decision makers to quantify the disparate impacts introduced by their release. In the second setting, this paper proposes a novel post-processing mechanism that is (approximately) optimal under different fairness metrics, either reducing fairness issues substantially or reducing the cost of privacy. The theoretical analysis is complemented with numerical simulations on Census data.

JAIR Journal 2022 Journal Article

Reinforcement Learning from Optimization Proxy for Ride-Hailing Vehicle Relocation

• Enpeng Yuan
• Wenbo Chen
• Pascal Van Hentenryck

Idle vehicle relocation is crucial for addressing demand-supply imbalance that frequently arises in the ride-hailing system. Current mainstream methodologies - optimization and reinforcement learning - suffer from obvious computational drawbacks. Optimization models need to be solved in real-time and often trade off model fidelity (hence quality of solutions) for computational efficiency. Reinforcement learning is expensive to train and often struggles to achieve coordination among a large fleet. This paper designs a hybrid approach that leverages the strengths of the two while overcoming their drawbacks. Specifically, it trains an optimization proxy, i.e., a machine-learning model that approximates an optimization model, and then refines the proxy with reinforcement learning. This Reinforcement Learning from Optimization Proxy (RLOP) approach is computationally efficient to train and deploy, and achieves better results than RL or optimization alone. Numerical experiments on the New York City dataset show that the RLOP approach reduces both the relocation costs and computation time significantly compared to the optimization model, while pure reinforcement learning fails to converge due to computational complexity.

AAAI Conference 2021 Conference Paper

Bias and Variance of Post-processing in Differential Privacy

• Keyu Zhu
• Pascal Van Hentenryck
• Ferdinando Fioretto

Post-processing immunity is a fundamental property of differential privacy: it enables the application of arbitrary dataindependent transformations to the results of differentially private outputs without affecting their privacy guarantees. When query outputs must satisfy domain constraints, postprocessing can be used to project the privacy-preserving outputs onto the feasible region. Moreover, when the feasible region is convex, a widely adopted class of post-processing steps is also guaranteed to improve accuracy. Post-processing has been applied successfully in many applications including census data-release, energy systems, and mobility. However, its effects on the noise distribution is poorly understood: It is often argued that post-processing may introduce bias and increase variance. This paper takes a first step towards understanding the properties of post-processing. It considers the release of census data and examines, both theoretically and empirically, the behavior of a widely adopted class of postprocessing functions.

AAAI Conference 2021 Conference Paper

Branch and Price for Bus Driver Scheduling with Complex Break Constraints

• Lucas Kletzander
• Nysret Musliu
• Pascal Van Hentenryck

This paper presents a Branch and Price approach for a reallife Bus Driver Scheduling problem with a complex set of break constraints. The column generation uses a set partitioning model as master problem and a resource constrained shortest path problem as subproblem. Due to the complex constraints, the branch and price algorithm adopts several novel ideas to improve the column generation in the presence of a high-dimensional subproblem, including exponential arc throttling and a dedicated two-stage dominance algorithm. Evaluation on a publicly available set of benchmark instances shows that the approach provides the first provably optimal solutions for small instances, improving best-known solutions or proving them optimal for 48 out of 50 instances, and yielding an optimality gap of less than 1% for more than half the instances.

IJCAI Conference 2021 Conference Paper

Decision Making with Differential Privacy under a Fairness Lens

• Cuong Tran
• Ferdinando Fioretto
• Pascal Van Hentenryck
• Zhiyan Yao

Many agencies release datasets and statistics about groups of individuals that are used as input to a number of critical decision processes. To conform with privacy and confidentiality requirements, these agencies are often required to release privacy-preserving versions of the data. This paper studies the release of differentially private datasets and analyzes their impact on some critical resource allocation tasks under a fairness perspective. The paper shows that, when the decisions take as input differentially private data, the noise added to achieve privacy disproportionately impacts some groups over others. The paper analyzes the reasons for these disproportionate impacts and proposes guidelines to mitigate these effects. The proposed approaches are evaluated on critical decision problems that use differentially private census data.

AIJ Journal 2021 Journal Article

Differential privacy of hierarchical Census data: An optimization approach

• Ferdinando Fioretto
• Pascal Van Hentenryck
• Keyu Zhu

AAAI Conference 2021 Conference Paper

Differentially Private and Fair Deep Learning: A Lagrangian Dual Approach

• Cuong Tran
• Ferdinando Fioretto
• Pascal Van Hentenryck

A critical concern in data-driven decision making is to build models whose outcomes do not discriminate against some demographic groups, including gender, ethnicity, or age. To ensure non-discrimination in learning tasks, knowledge of the sensitive attributes is essential, while, in practice, these attributes may not be available due to legal and ethical requirements. To address this challenge, this paper studies a model that protects the privacy of the individuals’ sensitive information while also allowing it to learn non-discriminatory predictors. The method relies on the notion of differential privacy and the use of Lagrangian duality to design neural networks that can accommodate fairness constraints while guaranteeing the privacy of sensitive attributes. The paper analyses the tension between accuracy, privacy, and fairness and the experimental evaluation illustrates the benefits of the proposed model on several prediction tasks.

IJCAI Conference 2021 Conference Paper

End-to-End Constrained Optimization Learning: A Survey

• James Kotary
• Ferdinando Fioretto
• Pascal Van Hentenryck
• Bryan Wilder

This paper surveys the recent attempts at leveraging machine learning to solve constrained optimization problems. It focuses on surveying the work on integrating combinatorial solvers and optimization methods with machine learning architectures. These approaches hold the promise to develop new hybrid machine learning and optimization methods to predict fast, approximate, solutions to combinatorial problems and to enable structural logical inference. This paper presents a conceptual review of the recent advancements in this emerging area.

NeurIPS Conference 2021 Conference Paper

Learning Hard Optimization Problems: A Data Generation Perspective

• James Kotary
• Ferdinando Fioretto
• Pascal Van Hentenryck

Optimization problems are ubiquitous in our societies and are present in almost every segment of the economy. Most of these optimization problems are NP-hard and computationally demanding, often requiring approximate solutions for large-scale instances. Machine learning frameworks that learn to approximate solutions to such hard optimization problems are a potentially promising avenue to address these difficulties, particularly when many closely related problem instances must be solved repeatedly. Supervised learning frameworks can train a model using the outputs of pre-solved instances. However, when the outputs are themselves approximations, when the optimization problem has symmetric solutions, and/or when the solver uses randomization, solutions to closely related instances may exhibit large differences and the learning task can become inherently more difficult. This paper demonstrates this critical challenge, connects the volatility of the training data to the ability of a model to approximate it, and proposes a method for producing (exact or approximate) solutions to optimization problems that are more amenable to supervised learning tasks. The effectiveness of the method is tested on hard non-linear nonconvex and discrete combinatorial problems.

IJCAI Conference 2021 Conference Paper

Real-Time Pricing Optimization for Ride-Hailing Quality of Service

• Enpeng Yuan
• Pascal Van Hentenryck

When demand increases beyond the system capacity, riders in ride-hailing/ride-sharing systems often experience long waiting time, resulting in poor customer satisfaction. This paper proposes a spatio-temporal pricing framework (AP-RTRS) to alleviate this challenge and shows how it naturally complements state-of-the-art dispatching and routing algorithms. Specifically, the pricing optimization model regulates demand to ensure that every rider opting to use the system is served within reason-able time: it does so either by reducing demand to meet the capacity constraints or by prompting potential riders to postpone service to a later time. The pricing model is a model-predictive control algorithm that works at a coarser temporal and spatial granularity compared to the real-time dispatching and routing, and naturally integrates vehicle relocations. Simulation experiments indicate that the pricing optimization model achieves short waiting times without sacrificing revenues and geographical fairness.

IJCAI Conference 2020 Conference Paper

Differential Privacy for Stackelberg Games

• Ferdinando Fioretto
• Lesia Mitridati
• Pascal Van Hentenryck

This paper introduces a differentially private (DP) mechanism to protect the information exchanged during the coordination of sequential and interdependent markets. This coordination represents a classic Stackelberg game and relies on the exchange of sensitive information between the system agents. The paper is motivated by the observation that the perturbation introduced by traditional DP mechanisms fundamentally changes the underlying optimization problem and even leads to unsatisfiable instances. To remedy such limitation, the paper introduces the Privacy-Preserving Stackelberg Mechanism (PPSM), a framework that enforces the notions of feasibility and fidelity (i. e. near-optimality) of the privacy-preserving information to the original problem objective. PPSM complies with the notion of differential privacy and ensures that the outcomes of the privacy-preserving coordination mechanism are close-to-optimality for each agent. Experimental results on several gas and electricity market benchmarks based on a real case study demonstrate the effectiveness of the proposed approach. A full version of this paper [Fioretto et al. , 2020b] contains complete proofs and additional discussion on the motivating application.

IJCAI Conference 2020 Conference Paper

OptStream: Releasing Time Series Privately (Extended Abstract)

• Ferdinando Fioretto
• Pascal Van Hentenryck

Many applications of machine learning and optimization operate on sensitive data streams, posing significant privacy risks for individuals whose data appear in the stream. Motivated by an application in energy systems, this paper presents OptStream, a novel algorithm for releasing differentially private data streams under the w-event model of privacy. The procedure ensures privacy while guaranteeing bounded error on the released data stream. OptStream is evaluated on a test case involving the release of a real data stream from the largest European transmission operator. Experimental results show that OptStream may not only improve the accuracy of state-of-the-art methods by at least one order of magnitude but also support accurate load forecasting on the privacy-preserving data.

AAAI Conference 2020 Conference Paper

Predicting AC Optimal Power Flows: Combining Deep Learning and Lagrangian Dual Methods

• Ferdinando Fioretto
• Terrence W.K. Mak
• Pascal Van Hentenryck

The Optimal Power Flow (OPF) problem is a fundamental building block for the optimization of electrical power systems. It is nonlinear and nonconvex and computes the generator setpoints for power and voltage, given a set of load demands. It is often solved repeatedly under various conditions, either in real-time or in large-scale studies. This need is further exacerbated by the increasing stochasticity of power systems due to renewable energy sources in front and behind the meter. To address these challenges, this paper presents a deep learning approach to the OPF. The learning model exploits the information available in the similar states of the system (which is commonly available in practical applications), as well as a dual Lagrangian method to satisfy the physical and engineering constraints present in the OPF. The proposed model is evaluated on a large collection of realistic mediumsized power systems. The experimental results show that its predictions are highly accurate with average errors as low as 0. 2%. Additionally, the proposed approach is shown to improve the accuracy of the widely adopted linear DC approximation by at least two orders of magnitude.

IJCAI Conference 2020 Conference Paper

Real-Time Dispatching of Large-Scale Ride-Sharing Systems: Integrating Optimization, Machine Learning, and Model Predictive Control

• Connor Riley
• Pascal Van Hentenryck
• Enpeng Yuan

This paper considers the dispatching of large-scale real-time ride-sharing systems to address congestion issues faced by many cities. The goal is to serve all customers (service guarantees) with a small number of vehicles while minimizing waiting times under constraints on ride duration. This paper proposes an end-to-end approach that tightly integrates a state-of-the-art dispatching algorithm, a machine-learning model to predict zone-to-zone demand over time, and a model predictive control optimization to relocate idle vehicles. Experiments using historic taxi trips in New York City indicate that this integration decreases average waiting times by about 30% over all test cases and reaches close to 55% on the largest instances for high-demand zones.

JAIR Journal 2019 Journal Article

OptStream: Releasing Time Series Privately

• Ferdinando Fioretto
• Pascal Van Hentenryck

Many applications of machine learning and optimization operate on data streams. While these datasets are fundamental to fuel decision-making algorithms, often they contain sensitive information about individuals, and their usage poses significant privacy risks. Motivated by an application in energy systems, this paper presents OptStream, a novel algorithm for releasing differentially private data streams under the w-event model of privacy. OptStream is a 4-step procedure consisting of sampling, perturbation, reconstruction, and post-processing modules. First, the sampling module selects a small set of points to access in each period of interest. Then, the perturbation module adds noise to the sampled data points to guarantee privacy. Next, the reconstruction module re-assembles non-sampled data points from the perturbed sample points. Finally, the post-processing module uses convex optimization over the privacy-preserving output of the previous modules, as well as the privacy-preserving answers of additional queries on the data stream, to improve accuracy by redistributing the added noise. OptStream is evaluated on a test case involving the release of a real data stream from the largest European transmission operator. Experimental results show that OptStream may not only improve the accuracy of state-of-the-art methods by at least one order of magnitude but also supports accurate load forecasting on the privacy-preserving data.

AAMAS Conference 2019 Conference Paper

Privacy-Preserving Federated Data Sharing

• Ferdinando Fioretto
• Pascal Van Hentenryck

Consider a set of agents with sensitive datasets who are interested in the same prediction task and would like to share their datasets without revealing private information. For instance, the agents may be medical centers with their own historical databases and the task may be the diagnosis of a rare form of a disease. This paper investigates whether sharing privacy-preserving versions of these datasets may improve the agent predictions. It proposes a Privacy-preserving Federated Data Sharing (PFDS) protocol that each agent can run locally to produce a privacy-preserving version of its original dataset. The PFDS protocol is evaluated on several standard prediction tasks and experimental results demonstrate the potential of sharing privacy-preserving datasets to produce accurate predictors.

IJCAI Conference 2019 Conference Paper

Privacy-Preserving Obfuscation of Critical Infrastructure Networks

• Ferdinando Fioretto
• Terrence W. K. Mak
• Pascal Van Hentenryck

The paper studies how to release data about a critical infrastructure network (e. g. , a power network or a transportation network) without disclosing sensitive information that can be exploited by malevolent agents, while preserving the realism of the network. It proposes a novel obfuscation mechanism that combines several privacy-preserving building blocks with a bi-level optimization model to significantly improve accuracy. The obfuscation is evaluated for both realism and privacy properties on real energy and transportation networks. Experimental results show the obfuscation mechanism substantially reduces the potential damage of an attack exploiting the released data to harm the real network.

AAAI Conference 2018 Conference Paper

Community-Based Trip Sharing for Urban Commuting

• Mohd. Hafiz Hasan
• Pascal Van Hentenryck
• Ceren Budak
• Jiayu Chen
• Chhavi Chaudhry

This paper explores Community-Based Trip Sharing which uses the structure of communities and commuting patterns to optimize car or ride sharing for urban communities. It introduces the Commuting Trip Sharing Problem (CTSP) and proposes an optimization approach to maximize trip sharing. The optimization method, which exploits trip clustering, shareability graphs, and mixed-integer programming, is applied to a dataset of 9000 daily commuting trips from a mid-size city. Experimental results show that community-based trip sharing reduces daily car usage by up to 44%, thus producing significant environmental and traffic benefits and reducing parking pressure. The results also indicate that daily flexibility in pairing cars and passengers has significant impact on the benefits of the approach, revealing new insights on commuting patterns and trip sharing.

AAMAS Conference 2018 Conference Paper

Constrained-Based Differential Privacy for Mobility Services

• Ferdinando Fioretto
• Chansoo Lee
• Pascal Van Hentenryck

Ubiquitous mobile and wireless communication systems have the potential to revolutionize transportation systems, making accurate mobility traces and activity-based patterns available to optimize the design and operations of mobility systems. However, these rich data sets also pose significant privacy risks, potentially revealing highly sensitive information about individual agents. This paper studies how to use differential privacy to release mobility data for transportation applications. It shows that existing approaches do not provide the desired fidelity for practical uses. To remedy this limitation, the paper proposes the idea of Constraint- Based Differential Privacy (CBDP) that casts the production of a private data set as an optimization problem that redistributes the noise introduced by a randomized mechanism to satisfy fundamental constraints of the original data set. The CBDP has strong theoretical guarantees: It is a constant factor away from optimality and when the constraints capture categorical features, it runs in polynomial time. Experimental results show that CBDP ensures that a city-level multi-modal transit system has similar performance measures when designed and optimized over the real and private data sets and improves state-of-art privacy methods by an order of magnitude.

AAAI Conference 2017 Conference Paper

Taming the Matthew Effect in Online Markets with Social Influence

• Franco Berbeglia
• Pascal Van Hentenryck

Social influence has been shown to create a Matthew effect in online markets, increasing inequalities and leading to “winner-take-all” phenomena. Matthew effects have been observed for numerous market policies, including when the products are presented to consumers by popularity or quality. This paper studies how to reduce Matthew effects, while keeping markets efficient and predictable when social influence is used. It presents a market strategy based on randomization and segmentation, that ensures that the best products, if they are close in quality, will have reasonably close market shares. The benefits of this market strategy is justified both theoretically and empirically and the loss in market efficiency is shown to be acceptable.

IJCAI Conference 2016 Conference Paper

Asymptotic Optimality of Myopic Optimization in Trial-Offer Markets with Social Influence

• Andr
• eacute; s Abeliuk
• Gerardo Berbeglia
• Felipe Maldonado
• Pascal Van Hentenryck

We study dynamic trial-offer markets, in which participants first try a product and later decide whether to purchase it or not. In these markets, social influence and position biases have a greater effect on the decisions taken in the sampling stage than those in the buying stage. We consider a myopic policy that maximizes the market efficiency for each incoming participant, taking into account the inherent quality of products, position biases, and social influence. We prove that this myopic policy is optimal and predictable asymptotically.

AAAI Conference 2016 Conference Paper

Benders Decomposition for Large-Scale Prescriptive Evacuations

• Julia Romanski
• Pascal Van Hentenryck

This paper considers prescriptive evacuation planning for a region threatened by a natural disaster such a flood, a wildfire, or a hurricane. It proposes a Benders decomposition that generalizes the two-stage approach proposed in earlier work for convergent evacuation plans. Experimental results show that Benders decomposition provides significant improvements in solution quality in reasonable time: It finds provably optimal solutions to scenarios considered in prior work, closing these instances, and increases the number of evacuees by 10 to 15% on average on more complex flood scenarios.

AAAI Conference 2016 Conference Paper

Intelligent Habitat Restoration Under Uncertainty

• Tommaso Urli
• Jana Brotánková
• Philip Kilby
• Pascal Van Hentenryck

Conservation is an ethic of sustainable use of natural resources which focuses on the preservation of biodiversity, i. e. , the degree of variation of life. Conservation planning seeks to reach this goal by means of deliberate actions, aimed at the protection (or restoration) of biodiversity features. In this paper we present an intelligent system to assist conservation managers in planning habitat restoration actions, with focus on the activities to be carried out in the islands of the Great Barrier Reef (QLD) and the Pilbara (WA) regions of Australia. In particular, we propose a constrained optimisation formulation of the habitat restoration planning (HRP) problem, capturing aspects such as population dynamics and uncertainty. We show that the HRP is NPhard, and develop a constraint programming (CP) model and a large neighbourhood search (LNS) procedure to generate activity plans under budgeting constraints in a reasonable amount of time.

IJCAI Conference 2016 Conference Paper

Interdependent Scheduling Games

• Andres Abeliuk
• Haris Aziz
• Gerardo Berbeglia
• Serge Gaspers
• Petr Kalina
• Nicholas Mattei
• Dominik Peters
• Paul Stursberg

We propose a model of interdependent scheduling games in which each player controls a set of services that they schedule independently. A player is free to schedule his own services at any time; however, each of these services only begins to accrue reward for the player when all predecessor services, which may or may not be controlled by the same player, have been activated. This model, where players have interdependent services, is motivated by the problems faced in planning and coordinating large-scale infrastructures, e. g. , restoring electricity and gas to residents after a natural disaster or providing medical care in a crisis when different agencies are responsible for the delivery of staff, equipment, and medicine. We undertake a game-theoretic analysis of this setting and in particular consider the issues of welfare maximization, computing best responses, Nash dynamics, and existence and computation of Nash equilibria.

AAAI Conference 2016 Conference Paper

Optimizing Infrastructure Enhancements for Evacuation Planning

• Kunal Kumar
• Julia Romanski
• Pascal Van Hentenryck

With rapid population growth and urbanization, emergency services in various cities around the world worry that the current transportation infrastructure is no longer adequate for large-scale evacuations. This paper considers how to mitigate this issue through infrastructure upgrades, such as the additions of lanes to road segments and the raising of bridges and roads. The paper proposes a MIP model for deciding the most effective infrastructure upgrades as well as a Benders decomposition approach where the master problem jointly plans the upgrades and evacuation routes and the subproblem schedules the evacuation itself. Experimental results demonstrate the practicability of the approach on a real case study, filling a significant need for emergencies services.

IJCAI Conference 2015 Conference Paper

A Bargaining Mechanism for One-Way Games

• Andres Abeliuk
• Gerardo Berbeglia
• Pascal Van Hentenryck

We introduce one-way games, a framework motivated by applications in large-scale power restoration, humanitarian logistics, and integrated supplychains. The distinguishable feature of the games is that the payoff of some player is determined only by her own strategy and does not depend on actions taken by other players. We show that the equilibrium outcome in one-way games without payments and the social cost of any ex-post efficient mechanism, can be far from the optimum. We also show that it is impossible to design a Bayes- Nash incentive-compatible mechanism for one-way games that is budget-balanced, individually rational, and efficient. Finally, we propose a privacypreserving mechanism that is incentive-compatible and budget-balanced, satisfies ex-post individual rationality conditions, and produces an outcome which is more efficient than the equilibrium without payments.

AAAI Conference 2015 Conference Paper

Convergent Plans for Large-Scale Evacuations

• Caroline Even
• Victor Pillac
• Pascal Van Hentenryck

Evacuation planning is a critical aspect of disaster preparedness and response to minimize the number of people exposed to a threat. Controlled evacuations aim at managing the flow of evacuees as efficiently as possible and have been shown to produce significant benefits compared to self-evacuations. However, existing approaches do not capture the delays introduced by diverging and crossing evacuation routes, although evidence from actual evacuations highlights that these can lead to significant congestion. This paper introduces the concept of convergent evacuation plans to tackle this issue. It presents a MIP model to obtain optimal convergent evacuation plans which, unfortunately, does not scale to realistic instances. The paper then proposes a two-stage approach that separates the route design and the evacuation scheduling. Experimental results on a real case study show that the two-stage approach produces better primal bounds than the MIP model and is two orders of magnitude faster; It also produces dual bounds stronger than the linear relaxation of the MIP model. Finally, simulations of the evacuation demonstrate that convergent evacuation plans outperform existing approaches for realistic driver behaviors.

AAAI Conference 2015 Conference Paper

Emerging Architectures for Global System Science

• Michela Milano
• Pascal Van Hentenryck

AAAI Conference 2015 Conference Paper

Power System Restoration With Transient Stability

• Hassan Hijazi
• Terrence W.K. Mak
• Pascal Van Hentenryck

We address the problem of power system restoration after a significant blackout. Prior work focus on optimization methods for finding high-quality restoration plans. Optimal solutions consist in a sequence of grid repairs and corresponding steady states. However, such approaches lack formal guarantees on the transient stability of restoration actions, a key property to avoid additional grid damage and cascading failures. In this paper, we show how to integrate transient stability in the optimization procedure by capturing the rotor dynamics of power generators. Our approach reasons about the differential equations describing the dynamics and their underlying transient states. The key contribution lies in modeling and solving optimization problems that return stable generators dispatch minimizing the difference with respect to steady states solutions. Computational efficiency is increased using preprocessing procedures along with traditional reduction techniques. Experimental results on existing benchmarks confirm the feasibility of the new approach.

ECAI Conference 2014 Conference Paper

NICTA Evacuation Planner: Actionable Evacuation Plans with Contraflows

• Caroline Even
• Victor Pillac
• Pascal Van Hentenryck

Evacuations are a critical aspect of disaster management, and generally the first prevention measure to ensure the safety of the population under threat. Designing evacuation plans is a complex task that requires to take into account multiple factors in order to limit congestion and ensure that all evacuees reach safety in time. This paper proposes a conflict-based path-generation algorithm for evacuation planning and a web-based intelligent system targeted at local authorities and emergency services. The key contribution of this paper is to propose the first scalable approach to produce actionable evacuation plans that simultaneously schedules the evacuation and selects contraflow roads. The benefits of the approach are illustrated on two large-scale case studies. The resulting optimization model is integrated in NICTA EVACUATION PLANNER, a tool to model, plan, and simulate evacuations.

AAAI Conference 2014 Conference Paper

Propagating Regular Counting Constraints

• Nicolas Beldiceanu
• Pierre Flener
• Justin Pearson
• Pascal Van Hentenryck

Constraints over finite sequences of variables are ubiquitous in sequencing and timetabling. This led to general modelling techniques and generic propagators, often based on deterministic finite automata (DFA) and their extensions. We consider counter-DFAs (cDFA), which provide concise models for regular counting constraints, that is constraints over the number of times a regular-language pattern occurs in a sequence. We show how to enforce domain consistency in polynomial time for at-most and at-least regular counting constraints based on the frequent case of a cDFA with only accepting states and a single counter that can be increased by transitions. We also show that the satisfaction of exact regular counting constraints is NP-hard and that an incomplete propagator for exact regular counting constraints is faster and provides more pruning than the existing propagator from (Beldiceanu, Carlsson, and Petit 2004). Finally, by avoiding the unrolling of the cDFA used by COSTREGULAR, the space complexity reduces from O(n · |Σ| · |Q|) to O(n · (|Σ| + |Q|)), where Σ is the alphabet and Q the state set of the cDFA.

IJCAI Conference 2013 Conference Paper

Computational Disaster Management

• Pascal Van Hentenryck

ECAI Conference 2012 Conference Paper

Joint Assessment and Restoration of Power Systems

• Pascal Van Hentenryck
• Nabeel Gillani
• Carleton Coffrin

This paper studies the joint damage assessment and recovery of the power infrastructure after a natural disaster has occurred. Earlier work in this area proposed an optimization algorithm for the recovery phase, assuming that the infrastructure damage was known precisely. This paper lifts this assumption which does not always hold in practice. It proposes three approaches to this problem: An online stochastic optimization algorithm, a 2-stage algorithm that first evaluates the damage and then perform restoration, and a hybridization of both approaches. Each of these approaches use information produced by weather and fragility simulation tools that provide potential damage scenarios for the disaster. Experimental results on natural disaster scenarios for the US infrastructure indicate that online stochastic combinatorial optimization provides high-quality solutions to the joint damage assessment and recovery problem.

AAAI Conference 2012 Conference Paper

Last-Mile Restoration for Multiple Interdependent Infrastructures

• Carleton Coffrin
• Pascal Van Hentenryck
• Russell Bent

IJCAI Conference 2011 Conference Paper

Large Neighborhood Search and Adaptive Randomized Decompositions for Flexible Jobshop Scheduling

• Dario Pacino
• Pascal Van Hentenryck

This paper considers a constraint-based scheduling approach to the flexible jobshop, a generalization of the traditional jobshop scheduling where activities have a choice of machines. It studies both large neighborhood (LNS) and adaptive randomized decomposition (ARD) schemes, using random, temporal, and machine decompositions. Empirical results on standard benchmarks show that, within 5 minutes, both LNS and ARD produce many new best solutions and are about 0. 5% in average from the best-known solutions. Moreover, over longer runtimes, they improve 60% of the best-known solutions and match the remaining ones. The empirical results also show the importance of hybrid decompositions in LNS and ARD.

IJCAI Conference 2011 Conference Paper

Symmetry Breaking via LexLeader Feasibility Checkers

• Justin Yip
• Pascal Van Hentenryck

This paper considers matrix models, a class of CSPs which generally exhibit significant symmetries. It proposed the idea of LexLeader feasibility checkers that verify, during search, whether the current partial assignment can be extended into a canonical solution. The feasibility checkers are based on a novel result by [Katsirelos et al. , 2010] on how to check efficiently whether a solution is canonical. The paper generalizes this result to partial assignments, various variable orderings, and value symmetries. Empirical results on 5 standard benchmarks shows that feasibility checkers may bring significant performance gains, when jointly used with DoubleLex or SnakeLex.

ICAPS Conference 2009 Conference Paper

Just-In-Time Scheduling with Constraint Programming

• Jean-Noël Monette
• Yves Deville
• Pascal Van Hentenryck

This paper considers Just-In-Time Job-Shop Scheduling, in which each activity has an earliness and a tardiness cost with respect to a due date. It proposes a constraint programming approach, which includes a novel filtering algorithm and dedicated heuristics. The filtering algorithm uses a machine relaxation to produce a lower bound that can be obtained by solving a Just-In-Time Pert problem. It also includes pruning rules which update the variable bounds and detect precedence constraints. The paper presents experimental results which demonstrate the effectiveness of the approach over a wide range of benchmarks.

AAAI Conference 2008 Conference Paper

Bound Consistency for Binary Length-Lex Set Constraints

• Pascal Van Hentenryck
• Carmen Gervet

The length-lex representation has been recently proposed for representing sets in Constraint Satisfaction Problems. The length-lex representation directly captures cardinality information, provides a total ordering for sets, and allows bound consistency on unary constraints to be enforced in time Õ(c), where c is the cardinality of the set. However, no algorithms were given to enforce bound consistency on binary constraints. This paper addresses this open issue. It presents algorithms to enforce bound consistency on disjointness and cardinality constraints in time O(c3 ). Moreover, it presents a generic bound-consistency algorithm for any binary constraint S which requires Õ(c2 ) calls to a feasibility subroutine for S.

AAAI Conference 2008 Conference Paper

Protein Structure Prediction on the Face Centered Cubic Lattice by Local Search

• Manuel Cebrian
• Pascal Van Hentenryck

Ab initio protein structure prediction is an important problem for which several algorithms have been developed. Algorithms differ by how they represent 3D protein conformations (on-lattice, off-lattice, coarse-grain or fine-grain model), by the energy model they consider, and whether they are heuristic or exact algorithms. This paper presents a local search algorithm to find the native state for the Hydrophobic-Polar (HP) model on the Face Centered Cubic (FCC) lattice; i. e. a self-avoiding walk on the FCC lattice with maximum number of H-H contacts. The algorithm relies on a randomized, structured initialization, a novel fitness function to guide the search, and efficient data structures to obtain self-avoiding walks. Experimental results on benchmark instances show the efficiency and excellent performance of our algorithm, and illustrate the biological pertinence of the FCC lattice.

ECAI Conference 2008 Invited Paper

The Impact of Constraint Programming

• Pascal Van Hentenryck

Constraint programming is a success story for artificial intelligence. It quickly moved from research laboratories to industrial applications and is in daily use to solve complex optimization throughout the world. At the same time, constraint programming continued to evolve, addressing new needs and opportunities. This talk reviews some recent progress in constraint programming, including its hybridization with other optimization approaches, the quest for more autonomous search, and its applications in a variety of nontraditional areas.

IJCAI Conference 2007 Conference Paper

• Russell Bent
• Pascal Van Hentenryck

This paper considers online stochastic multiple vehicle routing with time windows in which requests arrive dynamically and the goal is to maximize the number of serviced customers. Contrary to earlier algorithms which only move vehicles to known customers, this paper investigates waiting and relocation strategies in which vehicles may wait at their current location or relocate to arbitrary sites. Experimental results show that waiting and relocation strategies may dramatically improve customer service, especially for problems that are highly dynamic and contain many late requests. The decisions to wait and to relocate do not exploit any problem-specific features but rather are obtained by including choices in the online algorithm that are necessarily sub-optimal in an offline setting.

IJCAI Conference 2007 Conference Paper

• Luc Mercier
• Pascal Van Hentenryck

Despite significant algorithmic advances in recent years, finding optimal policies for large-scale, multistage stochastic combinatorial optimization problems remains far beyond the reach of existing methods. This paper studies a complementary approach, online anticipatory algorithms, that make decisions at each step by solving the anticipatory relaxation for a polynomial number of scenarios. Online anticipatory algorithms have exhibited surprisingly good results on a variety of applications and this paper aims at understanding their success. In particular, the paper derives sufficient conditions under which online anticipatory algorithms achieve good expected utility and studies the various types of errors arising in the algorithms including the anticipativity and sampling errors. The sampling error is shown to be negligible with a logarithmic number of scenarios. The anticipativity error is harder to bound and is shown to be low, both theoretically and experimentally, for the existing applications.

AAAI Conference 2007 Conference Paper

Population-Based Simulated Annealing for Traveling Tournaments

• Pascal Van Hentenryck

This paper reconsiders the travelling tournament problem, a complex sport-scheduling application which has attracted significant interest recently. It proposes a population-based simulated annealing algorithm with both intensification and diversification. The algorithm is organized as a series of simulated annealing waves, each wave being followed by a macro-intensification. The diversification is obtained through the concept of elite runs that opportunistically survive waves. A parallel implementation of the algorithm on a cluster of workstations exhibits remarkable results. It improves the best known solutions on all considered benchmarks, sometimes reduces the optimality gap by about 60%, and produces novel best solutions on instances that had been stable for several years.

AAAI Conference 2007 Conference Paper

Randomized Adaptive Spatial Decoupling for Large-Scale Vehicle Routing with Time Windows

• Pascal Van Hentenryck

In recent years, the size of combinatorial applications and the need to produce high-quality solutions quickly have increased steadily, providing significant challenges for optimization algorithms. This paper addresses this issue for large-scale vehicle routing problems with time windows, a class of very difficult optimization problems involving complex spatial and temporal dependencies. It proposes a randomized adaptive spatial decoupling (RASD) scheme for vehicle routing with time windows in order to produce highquality solutions quickly. Experimental results on hard instances with 1, 000 customers and 90 vehicles show that the RASD scheme, together with large neighborhood search, significantly improves the quality of the solutions under time constraints. Interestingly, the RASD scheme, when allowed to run longer, also improves the best available solutions in almost all the tested instances.

AAAI Conference 2007 Conference Paper

Synthesis of Constraint-Based Local Search Algorithms from High-Level Models

• Pascal Van Hentenryck

The gap in automation between MIP/SAT solvers and those for constraint programming and constraint-based local search hinders experimentation and adoption of these technologies and slows down scientific progress. This paper addresses this important issue: It shows how effective local search procedures can be automatically synthesized from models expressed in a rich constraint language. The synthesizer analyzes the model and derives the local search algorithm for a specific meta-heuristic by exploiting the structure of the model and the constraint semantics. Experimental results suggest that the synthesized procedures only induce a small loss in efficiency on a variety of realistic applications in sequencing, resource allocation, and facility location.

AAAI Conference 2006 Conference Paper

Length-Lex Ordering for Set CSPs

• Pascal Van Hentenryck

Combinatorial design problems arise in many application areas and are naturally modelled in terms of set variables and constraints. Traditionally, the domain of a set variable is specified by two sets (R, E) and denotes all sets containing R and disjoint from E. This representation has inherent difficulties in handling cardinality and lexicographic constraints so important in combinatorial design. This paper takes a dual view of set variables. It proposes a representation that encodes directly cardinality and lexicographic information, by totally ordering a set domain with a length-lex ordering. The solver can then enforce bound-consistency on all unary constraints in time Õ(k) where k is the set cardinality. In analogy with finite-domain solvers, non-unary constraints can be viewed as inference rules generating new unary constraints. The resulting set solver achieves a pruning (at least) comparable to the hybrid domain of Sadler and Gervet at a fraction of the computational cost.

ICAPS Conference 2005 Conference Paper

Minimizing Breaks in Sport Scheduling with Local Search

• Pascal Van Hentenryck
• Yannis Vergados

Sport scheduling has received significant attention in the recent years and has contributed many challenging applications for optimization technologies. This paper reconsiders the problem of minimizing the number of breaks in round-robin tournaments, an application which has been recently tackled by sophisticated constraint and mathematical programming approaches. It proposes a simulated annealing algorithm that finds optimal solutions very quickly for the largest instances available. On the larger instances (e. g., 28 teams), the algorithm is several orders of magnitude faster than earlier approaches. In addition, the experimental results indicate that near-optimal solutions can be obtained within 10 seconds for large instances. Of particular interest is the simplicity of the implementation, its automatic tuning of the parameters, and the fact that simulated annealing is an effective technique for another sport-scheduling application.

ICAPS Conference 2005 Conference Paper

Online Stochastic Optimization Without Distributions

• Russell Bent
• Pascal Van Hentenryck

This paper considers online stochastic scheduling problems where time constraints severely limit the number of optimizations which can be performed at decision time and/or in between decisions. Prior research has demonstrated that, whenever a distribution of the inputs is available for sampling, online stochatic algorithms may produce significant improvements in solution quality over oblivious approaches. However, the availability of an input distribution, although reasonable in many contexts, is too strong a requirement in a variety of applications. This paper broadens the applicability of online stochastic algorithms by relaxing this requirement and using machine learning techniques or historical data instead. In particular, it shows that machine learning techniques can be engineered to learn the distribution online, when its underlying structure is not available. Moreover, the paper presents the idea of historical sampling which provides a simple and effective way to leverage historical data in continuous and periodic online optimization. Experimental results on packet scheduling and vehicle routing indicate the potential of machine learning and historical sampling for online scheduling.

ICAPS Conference 2004 Conference Paper

Iterative Relaxations for Iterative Flattening in Cumulative Scheduling

• Laurent Michel
• Pascal Van Hentenryck

Cumulative scheduling is a generalization of jobshop scheduling, where machines have discrete capacities and activities may require several capacity units. This paper considers iterative flattening, a heuristic procedure aiming at producing high-quality solutions to large cumulative problems in reasonable time. On standard benchmarks (with as much as 900 activities), iterative flattening quickly delivers solutions that are within 10% of the best upper bounds in average. This paper analyzes iterative flattening and identifies a pathological behaviour which explains why it may result in solutions where resources are under-utilized in early parts of the schedules. It proposes a simple extension of the algorithm which has dramatic effect on the quality of the solutions, while preserving its computational efficiency. The new algorithm found 21 new best upper bounds to the same benchmarks and quickly delivers solutions that are within 1% of the best available upper bounds in the average.

AAAI Conference 2004 Conference Paper

Regrets Only! Online Stochastic Optimization under Time Constraints

• Russell Bent
• Pascal Van Hentenryck

This paper considers online stochastic optimization problems where time constraints severely limit the number of offline optimizations which can be performed at decision time and/or in between decisions. It proposes a novel approach which combines the salient features of the earlier approaches: the evaluation of every decision on all samples (expectation) and the ability to avoid distributing the samples among decisions (consensus). The key idea underlying the novel algorithm is to approximate the regret of a decision d. The regret algorithm is evaluated on two fundamentally different applications: online packet scheduling in networks and online multiple vehicle routing with time windows. On both applications, it produces significant benefits over prior approaches.

ICAPS Conference 2004 Conference Paper

The Value of Consensus in Online Stochastic Scheduling

• Russell Bent
• Pascal Van Hentenryck

This paper reconsiders online packet scheduling in computer networks, where the goal is to minimize weighted packet loss and where the arrival distributions of packets, or approximations thereof, are available for sampling. Earlier work proposed an expectation approach, which chooses the next packet to schedule by approximating the expected loss of each decision over a set of scenarios. The expectation approach was shown to significantly outperform traditional approaches ignoring stochastic information. This paper proposes a novel stochastic approach for online packet scheduling, whose key idea is to select the next packet as the one which is scheduled first most often in the optimal solutions of the scenarios. This consensus approach is shown to outperform the expectation approach significantly whenever time constraints and the problem features limit the number of scenarios that can be solved before making a decision. More importantly perhaps, the paper shows that the consensus and expectation approaches can be integrated to combine the benefits of both approaches. These novel online stochastic optimization algorithms are generic and problem-independent, they apply to other online applications as well, and they shed new light on why existing online stochastic algorithms behave well.

IJCAI Conference 2003 Conference Paper

Dynamic Vehicle Routing with Stochastic Requests

• Russell Bent
• Pascal Van Hentenryck

This paper considers vehicle routing problems (VRP) where customer locations and service times are random variables that are realized dynamically during plan execution. It proposes a multiple scenario approach (MSA) that continuously generates plans consistent with past decisions and anticipating future requests. The approach, which combines Al and OR techniques in novel ways, is compared with the best available heuristics that model longdistance courier mail services [Larsen et al, 2002]. Experimental results shows that MSA may significantly decrease travel times and is robust wrt reasonably noisy distributions.

UAI Conference 2002 Conference Paper

A Constraint Satisfaction Approach to the Robust Spanning Tree Problem with Interval Data

• Ionut D. Aron
• Pascal Van Hentenryck

Robust optimization is one of the fundamental approaches to deal with uncertainty in combinatorial optimization. This paper considers the robust spanning tree problem with interval data, which arises in a variety of telecommunication applications. It proposes a constraint satisfaction approach using a combinatorial lower bound, a pruning component that removes infeasible and suboptimal edges, as well as a search strategy exploring the most uncertain edges first. The resulting algorithm is shown to produce very dramatic improvements over the mathematical programming approach of Yaman et al. and to enlarge considerably the class of problems amenable to effective solutions

TCS Journal 2002 Journal Article

Editorial

• Pascal Van Hentenryck

AIJ Journal 1999 Journal Article

Constraint satisfaction over connected row-convex constraints

• Yves Deville
• Olivier Barette
• Pascal Van Hentenryck

AIJ Journal 1998 Journal Article

A gentle introduction to Numerica

• Pascal Van Hentenryck

TCS Journal 1997 Journal Article

Helios: A modeling language for global optimization and its implementation in Newton

• Laurent Michel
• Pascal Van Hentenryck

IJCAI Conference 1997 Conference Paper

Numerica: a Modeling Language for Global Optimization

• Pascal Van Hentenryck

AIJ Journal 1992 Journal Article

A generic arc-consistency algorithm and its specializations

• Pascal Van Hentenryck
• Yves Deville
• Choh-Man Teng

AIJ Journal 1992 Journal Article

Constraint satisfaction using constraint logic programming

• Pascal Van Hentenryck
• Helmut Simonis
• Mehmet Dincbas

KER Journal 1991 Journal Article

Constraint logic programming

• Pascal Van Hentenryck

Abstract Constraint logic programming (CLP) is a generalization of logic programming (LP) where unification, the basic operation of LP languages, is replaced by constraint handling in a constraint system. The resulting languages combine the advantages of LP (declarative semantics, nondeterminism, relational form) with the efficiency of constraint-solving algorithms. For some classes of combinatorial search problems, they shorten the development time significantly while preserving most of the efficiency of imperative languages. This paper surveys this new class of programming languages from their underlying theory, to their constraint systems, and to their applications to combinatorial problems.

IJCAI Conference 1989 Conference Paper

Simulation of Hybrid Circuits in Constraint Logic Programming

• Thomas Graf
• Pascal Van Hentenryck
• Claudia Pradclles
• Laurent Zimmer

This paper presents LOGISIM, a CAD tool to simulate the temporal behaviour of hybrid circuits containing electro-mechanical, electrohydraulic, hydro-mechanic, and digital control devices. LOGISIM combines the advantages of both qualitative and quantitative reasoning by producing a high-level description (discrete states) of the circuit behaviour while reasoning at the quantitative level (physical values). In addition, device models in LOGISIM follow a particular description methodology proposed to avoid introducing an artificial computational complexity in the simulation. LOGISIM is fully implemented in the constraint logic programming language CHIP. The constraint-solving techniques of CHIP used in LOGISIM, i. e. an incremental decision procedure for linear constraints over rational numbers, consistency techniques on domain-variables and conditional propagation, are all necessary to solve the problem efficiently. LOGISIM has been applied successfully to real-life industrial circuits from aerospace industry in the ELSA project and clearly demonstrates the potential of this kind of tool to support the design process for these circuits.

AAAI Conference 1988 Conference Paper

Generality versus Specificity: An Experience with AI and OR Techniques

• Pascal Van Hentenryck

This paper contains an in-depth study of a particular problem in order to evaluate several approaches to the solving of discrete combinatorial problems. We take a warehouse location problem as a case study and present solutions to it by using Integer Programming, a specialized program based on A* and the constraint logic programming CHIP. The merits of each approach are discussed and compared in the light of the problem. Finally, we conclude by arguing that CHIP provides a valuable addition to the current set of tools for solving discrete combinatorial problems.

ECAI Conference 1988 Conference Paper

Solving the Car-Sequencing Problem in Constraint Logic Programming

• Mehmet Dincbas
• Helmut Simonis
• Pascal Van Hentenryck

IJCAI Conference 1987 Conference Paper

A Theoretical Framework for Consistency Techniques in Logic Programming

• Pascal Van Hentenryck