Margarida Carvalho

Gabriele Dragotto

Andrea Lodi 0001

Sriram Sankaranarayanan 0002

2025-01-01

Found. Trends Optim. (published)

A stochastic integer programming approach to reserve staff scheduling with preferences

Carl Perreault‐Lafleur

Guy Desaulniers

2025-01-01

Int. Trans. Oper. Res. (published)

The Strength of Fuel Refueling Location Problem Formulations

Nagisa Sugishita

Ribal Atallah

2024-09-06

ArXiv (preprint)

Accelerated Benders Decomposition and Local Branching for Dynamic Maximum Covering Location Problems

Steven Lamontagne

Ribal Atallah

The maximum covering location problem (MCLP) is a key problem in facility location, with many applications and variants. One such variant is… (see more) the dynamic (or multi-period) MCLP, which considers the installation of facilities across multiple time periods. To the best of our knowledge, no exact solution method has been proposed to tackle large-scale instances of this problem. To that end, in this work, we expand upon the current state-of-the-art branch-and-Benders-cut solution method in the static case, by exploring several acceleration techniques. Additionally, we propose a specialised local branching scheme, that uses a novel distance metric in its definition of subproblems and features a new method for efficient and exact solving of the subproblems. These methods are then compared through extensive computational experiments, highlighting the strengths of the proposed methodologies.

2024-07-01

Computers & Operations Research (published)

Learning to Build Solutions in Stochastic Matching Problems Using Flows (Student Abstract)

William St-Arnaud

Golnoosh Farnadi

2024-03-24

Proceedings of the AAAI Conference on Artificial Intelligence (published)

Solving Combinatorial Pricing Problems using Embedded Dynamic Programming Models

Quang Minh Bui

Jos'e Neto

The combinatorial pricing problem (CPP) is a bilevel problem in which the leader maximizes their revenue by imposing tolls on certain items … (see more)that they can control. Based on the tolls set by the leader, the follower selects a subset of items corresponding to an optimal solution of a combinatorial optimization problem. To accomplish the leader's goal, the tolls need to be sufficiently low to discourage the follower from choosing the items offered by the competitors. In this paper, we derive a single-level reformulation for the CPP by rewriting the follower's problem as a longest path problem using a dynamic programming model, and then taking its dual and applying strong duality. We proceed to solve the reformulation in a dynamic fashion with a cutting plane method. We apply this methodology to 2 distinct dynamic programming models, namely, a novel formulation designated as selection diagram and the well-known decision diagram. We also produce numerical results to evaluate their performances across 3 different specializations of the CPP and a closely related problem that is the knapsack interdiction problem. Our results showcase the potential of the 2 proposed reformulations over the natural value function approach, expanding the set of tools to solve combinatorial bilevel programs.

2024-03-19

ArXiv (preprint)

The effects of nature-based vs. indoor settings on the adaptability, performance and affect of calisthenics exercisers. A registered report.

Henrique Brito

Henrique Lopes

Daniel Carrilho

Adriano Carvalho

Duarte Araújo

2024-03-01

Psychology of Sport And Exercise (published)

The effects of nature-based vs. indoor settings on the adaptability, performance and affect of calisthenics exercisers. A registered report.

Henrique Brito

Henrique Lopes

Daniel Carrilho

Adriano Carvalho

Duarte Araújo

2024-03-01

Psychology of Sport And Exercise (published)

Solving Two-Stage Stochastic Programs with Endogenous Uncertainty via Random Variable Transformation

Maria Bazotte

Thibaut Vidal

2024-02-23

ArXiv (preprint)

The Sample Average Approximation Method for Solving Two-Stage Stochastic Programs with Endogenous Uncertainty

Maria Bazotte

Thibaut Vidal

Real-world decision-making problems involve Type 1 decision-dependent uncertainty, where the probability distribution of the stochastic proc… (see more)ess depends on the model decisions. However, few studies focus on two-stage stochastic programs with this type of endogenous uncertainty, and those that do lack general methodologies. We thus propose herein a general method for solving a class of these programs based on the transformation of random variables, a technique widely employed in probability and statistics. The proposed method is tailored to large-scale problems with discrete or continuous endogenous random variables. The random variable transformation allows the use of the sample average approximation (SAA) method, which provides optimality convergence guarantees under certain conditions. We show that, for some classical distributions, the proposed method reduces to solving mixed-integer linear or convex programs. Finally, we validate this method by applying it to a network design and facility-protection problem, considering distinct decision-dependent distributions for the random variables. Whereas most distributions result in a nonlinear nonconvex deterministic equivalent program, the proposed method solves mixed-integer linear programs in all cases. In addition, it produces attractive performance estimators for the SAA method in a reasonable computational time and outperforms the case in which the endogenous distribution defines a mixed-integer deterministic equivalent.

2024-02-23

ArXiv (preprint)

Computing Approximate Nash Equilibria for Integer Programming Games

Aloïs Duguet

Gabriele Dragotto

Sandra-ulrich Ngueveu

2024-02-06

ArXiv (preprint)

Asymmetry in the complexity of the multi-commodity network pricing problem

Quang Minh Bui

Jos'e Neto

2024-01-01

Math. Program. (published)