Authors: Ayse N. Arslan, Jeremy Omer, Fulin Yan
Abstract: The kidney exchange problem (KEP) is an increasingly important healthcare management problem in most European and North American countries which consists of matching incompatible patient-donor pairs in a centralized system. Despite the significant progress in the exact solution of KEP instances in recent years, larger instances still pose a challenge especially when altruistic donors are taken into account. In this article, we present a branch-and-price algorithm for the exact solution of KEP in the presence of altruistic donors. This algorithm is based on a disaggregated cycle and chains formulation where subproblems are managed through graph copies. We additionally, present a branch-and-price algorithm based on the position-indexed chain-edge formulation, as well as two compact formulations. We formalize and analyze the complexity of the resulting pricing problems and identify the conditions under which they can be solved using polynomial-time algorithms. We propose several algorithmic improvements for the branch-and-price algorithms as well as for the pricing problems. We extensively test all of our implementations using a benchmark made up of different types of instances with the largest instances considered having 10000 pairs and 1000 altruists. Our numerical results show that the proposed algorithm can be up to two orders of magnitude faster compared to the state-of-the-art. All models and algorithms presented in the paper are gathered in an open-access Julia package, KidneyExchange.jl. [Read more]
Abstract: The kidney exchange problem (KEP) is an increasingly important healthcare management problem in most European and North American countries which consists of matching incompatible patient-donor pairs in a centralized system. Despite the significant progress in the exact solution of KEP instances in recent years, larger instances still pose a challenge especially when altruistic donors are taken into account. In this article, we present a branch-and-price algorithm for the exact solution of KEP in the presence of altruistic donors. This algorithm is based on a disaggregated cycle and chains formulation where subproblems are managed through graph copies. We additionally, present a branch-and-price algorithm based on the position-indexed chain-edge formulation, as well as two compact formulations. We formalize and analyze the complexity of the resulting pricing problems and identify the conditions under which they can be solved using polynomial-time algorithms. We propose several algorithmic improvements for the branch-and-price algorithms as well as for the pricing problems. We extensively test all of our implementations using a benchmark made up of different types of instances with the largest instances considered having 10000 pairs and 1000 altruists. Our numerical results show that the proposed algorithm can be up to two orders of magnitude faster compared to the state-of-the-art. All models and algorithms presented in the paper are gathered in an open-access Julia package, KidneyExchange.jl. [Read more]
Authors: Brais González-Rodrı́guez, Aurélien Froger, Ola Jabali, Joe Naoum-Sawaya
Abstract: Establishing the size of an EV fleet is a vital decision for logistics operators. In urban settings, this issue is often dealt with by partitioning the geographical area around a depot into service zones, each served by a single vehicle. Such zones ultimately guide daily routing decisions. We study the problem of determining the optimal partitioning of an urban logistics area served by EVs. We cast this problem in a Continuous Approximation (CA) framework. Considering a ring radial region with a depot at its center, we introduce the electric vehicle fleet sizing problem (EVFSP). As the current range of EVs is fairly sufficient to perform service in urban areas, we assume that the EV fleet is exclusively charged at the depot, i.e., en-route charging is not allowed. In the EVFSP we account for EV features such as limited range, and non-linear charging and energy pricing functions stemming from Time-of-use (ToU) tariffs. Specifically, we combine non-linear charging functions with pricing functions into charging cost functions, establishing the cost of charging an EV for a target charge level. We propose a polynomial time algorithm for determining this function. The resulting function is non-linear with respect to the route length. Therefore, we propose a Mixed Integer Non-linear Program (MINLP) for the EVFSP, which optimizes both dimensions of each zone in the partition. We strengthen our formulation with symmetry breaking constraints. Furthermore, … [Read more]
Abstract: Establishing the size of an EV fleet is a vital decision for logistics operators. In urban settings, this issue is often dealt with by partitioning the geographical area around a depot into service zones, each served by a single vehicle. Such zones ultimately guide daily routing decisions. We study the problem of determining the optimal partitioning of an urban logistics area served by EVs. We cast this problem in a Continuous Approximation (CA) framework. Considering a ring radial region with a depot at its center, we introduce the electric vehicle fleet sizing problem (EVFSP). As the current range of EVs is fairly sufficient to perform service in urban areas, we assume that the EV fleet is exclusively charged at the depot, i.e., en-route charging is not allowed. In the EVFSP we account for EV features such as limited range, and non-linear charging and energy pricing functions stemming from Time-of-use (ToU) tariffs. Specifically, we combine non-linear charging functions with pricing functions into charging cost functions, establishing the cost of charging an EV for a target charge level. We propose a polynomial time algorithm for determining this function. The resulting function is non-linear with respect to the route length. Therefore, we propose a Mixed Integer Non-linear Program (MINLP) for the EVFSP, which optimizes both dimensions of each zone in the partition. We strengthen our formulation with symmetry breaking constraints. Furthermore, … [Read more]
Authors: Ayse N. Arslan, Jeremy Omer, Fulin Yan
Abstract: The kidney exchange problem (KEP) is an increasingly important healthcare management problem in most European and North American countries which consists of matching incompatible patient-donor pairs in a centralized system. Despite the significant progress in the exact solution of KEP instances in recent years, larger instances still pose a challenge especially when altruistic donors are taken into account. In this article, we present a branch-and-price algorithm for the exact solution of KEP in the presence of altruistic donors. This algorithm is based on a disaggregated cycle and chains formulation where subproblems are managed through graph copies. We additionally, present a branch-and-price algorithm based on the position-indexed chain-edge formulation, as well as two compact formulations. We formalize and analyze the complexity of the resulting pricing problems and identify the conditions under which they can be solved using polynomial-time algorithms. We propose several algorithmic improvements for the branch-and-price algorithms as well as for the pricing problems. We extensively test all of our implementations using a benchmark made up of different types of instances with the largest instances considered having 10000 pairs and 1000 altruists. Our numerical results show that the proposed algorithm can be up to two orders of magnitude faster compared to the state-of-the-art. All models and algorithms presented in the paper are gathered in an open-access Julia package, KidneyExchange.jl. [Read more]
Abstract: The kidney exchange problem (KEP) is an increasingly important healthcare management problem in most European and North American countries which consists of matching incompatible patient-donor pairs in a centralized system. Despite the significant progress in the exact solution of KEP instances in recent years, larger instances still pose a challenge especially when altruistic donors are taken into account. In this article, we present a branch-and-price algorithm for the exact solution of KEP in the presence of altruistic donors. This algorithm is based on a disaggregated cycle and chains formulation where subproblems are managed through graph copies. We additionally, present a branch-and-price algorithm based on the position-indexed chain-edge formulation, as well as two compact formulations. We formalize and analyze the complexity of the resulting pricing problems and identify the conditions under which they can be solved using polynomial-time algorithms. We propose several algorithmic improvements for the branch-and-price algorithms as well as for the pricing problems. We extensively test all of our implementations using a benchmark made up of different types of instances with the largest instances considered having 10000 pairs and 1000 altruists. Our numerical results show that the proposed algorithm can be up to two orders of magnitude faster compared to the state-of-the-art. All models and algorithms presented in the paper are gathered in an open-access Julia package, KidneyExchange.jl. [Read more]
Authors: François Clautiaux, Siham Essodaigui, Alain Nguyen, Ruslan Sadykov, Nawel Younes
Abstract: In this paper, we consider a new industrial problem, which occurs in the context of the automobile industry. This problem occurs during the testing phase of a new vehicle. It involves determining all the variants of the vehicle to be manufactured in order to carry out these tests, and scheduling these tests over time. We model this problem as a new scheduling scheduling problem… [Read more]
Abstract: In this paper, we consider a new industrial problem, which occurs in the context of the automobile industry. This problem occurs during the testing phase of a new vehicle. It involves determining all the variants of the vehicle to be manufactured in order to carry out these tests, and scheduling these tests over time. We model this problem as a new scheduling scheduling problem… [Read more]
Authors: Luis Marques, François Clautiaux, Aurélien Froger
Abstract: In this paper, we study the problem of designing a cabinet made up of a set of shelves that contain compartments whose contents slide forward on opening. Considering a set of items candidate to be stored in the cabinet over a given time horizon, the problem is to design a set of shelves, a set of compartments in each shelf and to select the items to be inserted into the compartments. The objective is to maximize the sum of the profits of the selected items. We formalize the SCPD problem and formulate it as a maximum cost flow problem in a decision hypergraph with additional linear constraints… [Read more]
Abstract: In this paper, we study the problem of designing a cabinet made up of a set of shelves that contain compartments whose contents slide forward on opening. Considering a set of items candidate to be stored in the cabinet over a given time horizon, the problem is to design a set of shelves, a set of compartments in each shelf and to select the items to be inserted into the compartments. The objective is to maximize the sum of the profits of the selected items. We formalize the SCPD problem and formulate it as a maximum cost flow problem in a decision hypergraph with additional linear constraints… [Read more]
Authors: Najib Errami, Eduardo Queiroga, Ruslan Sadykov, Eduardo Uchoa
Abstract: The optimization community has made significant progress in solving Vehicle Routing Problems (VRPs) to optimality using sophisticated Branch-Cut-and-Price (BCP) algorithms. VRPSolver is a BCP algorithm with excellent performance in many VRP variants. However, its complex underlying mathematical model makes it hardly accessible to routing practitioners. To address this, VRPSolverEasy provides a Python interface to VRPSolver that does not require any knowledge of Mixed Integer Programming modeling. Instead, routing problems are defined in terms of familiar elements such as depots, customers, links, and vehicle types. VRPSolverEasy can handle several popular VRP variants and arbitrary combinations of them. [Read more]
Abstract: The optimization community has made significant progress in solving Vehicle Routing Problems (VRPs) to optimality using sophisticated Branch-Cut-and-Price (BCP) algorithms. VRPSolver is a BCP algorithm with excellent performance in many VRP variants. However, its complex underlying mathematical model makes it hardly accessible to routing practitioners. To address this, VRPSolverEasy provides a Python interface to VRPSolver that does not require any knowledge of Mixed Integer Programming modeling. Instead, routing problems are defined in terms of familiar elements such as depots, customers, links, and vehicle types. VRPSolverEasy can handle several popular VRP variants and arbitrary combinations of them. [Read more]
Authors: Xuan Ren, Aurélien Froger, Ola Jabali, Gongqian Liang
Abstract: In this paper, we propose a heuristic algorithm for multiple variants of the vehicle routing problem with drones. Assuming that the drone may be launched from a node and recovered at another, these variants are characterized according to three axes, 1) minimizing the transportation cost or minimizing the makespan, 2) the drone may land and wait or not, and 3) single or multiple trucks each equipped with a single drone. One of our main algorithmic contributions relates to a subproblem of the VRPD. We introduce exact and heuristic dynamic programs for this subproblem. We embed them in a hybrid variable neighborhood search algorithm. We benchmark the performance of our algorithm on nine benchmark sets pertaining to four VRPD variants resulting in 932 instances. Our algorithm computes 651 of 680 optimal solutions and identifies 189 new best-known solutions. [Read more]
Abstract: In this paper, we propose a heuristic algorithm for multiple variants of the vehicle routing problem with drones. Assuming that the drone may be launched from a node and recovered at another, these variants are characterized according to three axes, 1) minimizing the transportation cost or minimizing the makespan, 2) the drone may land and wait or not, and 3) single or multiple trucks each equipped with a single drone. One of our main algorithmic contributions relates to a subproblem of the VRPD. We introduce exact and heuristic dynamic programs for this subproblem. We embed them in a hybrid variable neighborhood search algorithm. We benchmark the performance of our algorithm on nine benchmark sets pertaining to four VRPD variants resulting in 932 instances. Our algorithm computes 651 of 680 optimal solutions and identifies 189 new best-known solutions. [Read more]
Authors: Xavier Blanchot, François Clautiaux, Aurélien Froger, Manuel Ruiz
Abstract: In this paper, we study how a regulatory constraint limiting a measure of unserved demand, called Loss Of Load Expectation (LOLE), can be incorporated into a strategic version of a stochastic generation and transmission expansion planning problem. We show that a direct inclusion of the constraint into the extensive form of the two-stage stochastic problem leads to a formulation that violates the time-consistency principle. To obtain a valid model, we use bilevel programming and introduce a formulation of the problem in which the leader and follower have the same objective function. To solve this formulation, we propose a matheuristic that embeds a Benders decomposition algorithm in a binary search on the total investment cost… [Read more]
Abstract: In this paper, we study how a regulatory constraint limiting a measure of unserved demand, called Loss Of Load Expectation (LOLE), can be incorporated into a strategic version of a stochastic generation and transmission expansion planning problem. We show that a direct inclusion of the constraint into the extensive form of the two-stage stochastic problem leads to a formulation that violates the time-consistency principle. To obtain a valid model, we use bilevel programming and introduce a formulation of the problem in which the leader and follower have the same objective function. To solve this formulation, we propose a matheuristic that embeds a Benders decomposition algorithm in a binary search on the total investment cost… [Read more]
Authors: Ayse N. Arslan, Michael Poss
Abstract: Uncertainty reduction has recently been introduced in the robust optimization literature as a relevant special case of decision-dependent uncertainty. Herein, we first show that when the uncertainty reduction decisions are constrained, the resulting optimization problem is NP-hard. We further show that relaxing these constraints leads to solving a linear number of deterministic problems in certain special cases. We provide insights into possible MILP reformulations and illustrate the practical relevance of our theoretical results on the shortest path instances from the literature. [Read more]
Abstract: Uncertainty reduction has recently been introduced in the robust optimization literature as a relevant special case of decision-dependent uncertainty. Herein, we first show that when the uncertainty reduction decisions are constrained, the resulting optimization problem is NP-hard. We further show that relaxing these constraints leads to solving a linear number of deterministic problems in certain special cases. We provide insights into possible MILP reformulations and illustrate the practical relevance of our theoretical results on the shortest path instances from the literature. [Read more]
Authors: Maryam Daryalal, Ayse N. Arslan, Merve Bodur
Abstract: In this work, we design primal and dual bounding methods for multistage adjustable robust optimization (MSARO) problems motivated by two decision rules rooted in the stochastic programming literature. From the primal perspective, this is achieved by applying decision rules that restrict the functional forms of only a certain subset of decision variables resulting in an approximation of MSARO as a two-stage adaptive robust optimization problem. We leverage the two-stage robust optimization literature in the solution of this approximation. From the dual side, decision rules are applied to the Lagrangian multipliers of a Lagrangian dual of MSARO resulting in a two-stage stochastic optimization problem. We argue that the quality of the resulting dual bound is dependent on the distribution chosen when developing the dual formulation. We therefore define a distributionally robust problem with the aim of optimizing the obtained bound and develop solution methods depending on the nature of the recourse variables. Our framework is general-purpose and does not require strong assumptions such as a stage-wise independent uncertainty set, and can consider integer recourse variables. Computational experiments on newsvendor, location-transportation, and capital budgeting problems show that our bounds yield considerably smaller optimality gaps compared to the existing methods. [Read more]
Abstract: In this work, we design primal and dual bounding methods for multistage adjustable robust optimization (MSARO) problems motivated by two decision rules rooted in the stochastic programming literature. From the primal perspective, this is achieved by applying decision rules that restrict the functional forms of only a certain subset of decision variables resulting in an approximation of MSARO as a two-stage adaptive robust optimization problem. We leverage the two-stage robust optimization literature in the solution of this approximation. From the dual side, decision rules are applied to the Lagrangian multipliers of a Lagrangian dual of MSARO resulting in a two-stage stochastic optimization problem. We argue that the quality of the resulting dual bound is dependent on the distribution chosen when developing the dual formulation. We therefore define a distributionally robust problem with the aim of optimizing the obtained bound and develop solution methods depending on the nature of the recourse variables. Our framework is general-purpose and does not require strong assumptions such as a stage-wise independent uncertainty set, and can consider integer recourse variables. Computational experiments on newsvendor, location-transportation, and capital budgeting problems show that our bounds yield considerably smaller optimality gaps compared to the existing methods. [Read more]