Real-world decision-making problems often involve decision-dependent uncertainty, where the probability distribution of the random vector depends on the model’s decisions. Few studies focus on two-stage stochastic programs with this type of endogenous uncertainty, and those that do lack general methodologies. We propose a general method for solving a class of these programs based on random variable transformation, a technique widely employed in probability and statistics. The random variable transformation converts a stochastic program with endogenous uncertainty (original program) into an equivalent stochastic program with decision-independent uncertainty (transformed program), for which solution procedures are well studied. Additionally, endogenous uncertainty usually leads to nonlinear nonconvex programs, which are theoretically intractable. Nonetheless, we show that for some classical endogenous distributions, the proposed method yields mixed-integer linear or convex programs with exogenous uncertainty. We validate this method by applying it to a network design and facility-protection problem, considering distinct decision-dependent distributions for the random variables. Although the original formulation of this problem is nonlinear nonconvex for most endogenous distributions, the proposed method transforms it into mixed-integer linear programs with exogenous uncertainty. We solve these transformed programs with the sample average approximation method. We highlight the superior performance of our approach compared with solving the original program in the case that a mixed-integer linear formulation of this program exists. History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. Funding: This research was funded by Scale AI [the SCALE-AI Chair in Data-Driven Supply Chains], the Fonds de recherche du Québec [the FRQ -IVADO Research Chair], the IVADO [the FRQ -IVADO Research Chair], and the Natural Sciences and Engineering Research Council of Canada [Grant 2024-04051]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0847 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0847 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

The combinatorial pricing problem (CPP) is a bilevel problem in which the leader maximizes their revenue by imposing tolls on certain items 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 two distinct dynamic programming models—namely, a novel formulation designated as the selection diagram and the well-known decision diagram. We also produce numerical results to evaluate their performances across three different specializations of the CPP and a closely related problem that is the knapsack interdiction problem. Our results showcase the potential of the two proposed reformulations over the natural value function approach, expanding the set of tools to solve combinatorial bilevel programs. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: Financial support from IVADO and Fonds de recherche du Québec [FRQ-IVADO Research Chair], and the Natural Sciences and Engineering Research Council of Canada [Grants 2019-04557 and 2024-04051] is gratefully acknowledged. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0686 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0686 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Using school choice as a motivating example, we introduce a stylized model of a many-to-one matching market where the clearinghouse seeks to implement contingent priorities—i.e., priorities that depend on the current assignment—to improve the likelihood that students with siblings are assigned together. We provide a series of guidelines and introduce two natural approaches to implement them: (i) absolute, whereby a prioritized student can displace any student without siblings assigned to the school, and (ii) partial, whereby prioritized students can only displace students that have a less favorable lottery than their priority provider. We study several properties of the corresponding mechanisms, including the existence of a stable assignment under contingent priorities, the complexity of finding one if it exists, and its incentive properties. Furthermore, we introduce a soft version of these priorities to guarantee existence, and we provide mathematical programming formulations to find such stable matching or certify that one does not exist. Finally, using data from the Chilean school choice system, we show that our framework can significantly increase the number of students assigned to their top preference and the number of siblings assigned together relative to current practice. A full version of this paper can be found at https://arxiv.org/abs/2409.04914

Generative Flow Networks, known as GFlowNets, have been introduced in recent times, presenting an exciting possibility for neural networks to model distributions across various data structures. In this paper, we broaden their applicability to encompass scenarios where the data structures are optimal solutions of a combinatorial problem. Concretely, we propose the use of GFlowNets to learn the distribution of optimal solutions for kidney exchange problems (KEPs), a generalized form of matching problems involving cycles.

Abstract With the increasing effects of climate change, the urgency to step away from fossil fuels is greater than ever before. Electric vehicles (EVs) are one way to diminish these effects, but their widespread adoption is often limited by the insufficient availability of charging stations. In this work, our goal is to expand the infrastructure of EV charging stations, in order to provide a better quality of service in terms of user satisfaction (and availability of charging stations). Specifically, our focus is directed towards urban areas. We first propose a model for the assignment of EV charging demand to stations, framing it as a maximum flow problem. This model is the basis for the evaluation of user satisfaction with a given charging infrastructure. Secondly, we incorporate the maximum flow model into a mixed‐integer linear program, where decisions on the opening of new stations and on the expansion of their capacity through additional outlets is accounted for. We showcase our methodology for the city of Montreal, demonstrating the scalability of our approach to handle real‐world scenarios. We conclude that considering both spacial and temporal variations in charging demand is meaningful when solving realistic instances.

Centralized mechanisms are becoming the standard approach to solve several assignment problems. Examples include the allocation of students to schools (school choice), high-school graduates to colleges, residents to hospitals and refugees to cities. In most of these markets, a desirable property of the assignment is stability, which guarantees that no pair of agents has incentive to circumvent the matching. Using school choice as our matching market application, we introduce the problem of jointly allocating a school capacity expansion and finding the best stable matching for the students in the expanded market. We analyze theoretically the problem, focusing on the trade-off behind the multiplicity of student-optimal assignments, and the problem complexity. Since the theoretical intractability of the problem precludes the adaptation of classical approaches to solve it efficiently, we generalize existent mathematical programming formulations of stability constraints to our setting. These generalizations result in integer quadratically-constrained programs, which are computationally hard to solve. In addition, we propose a novel mixed-integer linear programming formulation that is exponentially-large on the problem size. We show that the stability constraints can be separated in linear time, leading to an effective cutting-plane method. We evaluate the performance of our approaches in a detailed computational study, and we find that our cutting-plane method outperforms mixed-integer programming solvers applied to existent formulations extended to our problem setting. We also propose two heuristics that are effective for large instances of the problem. Finally, we use the Chilean school choice system data to demonstrate the impact of capacity planning under stability conditions. Our results show that each additional school seat can benefit multiple students. On the one hand, we can focus on access by prioritizing extra seats that benefit previously unassigned students; on the other hand, we can focus on merit by allocating extra seats that benefit several students via chains of improvement. These insights empower the decision-maker in tuning the matching algorithm to provide a fair application-oriented solution.

We present a new model for finding the optimal placement of electric vehicle charging stations across a multiperiod time frame so as to maximise electric vehicle adoption. Via the use of stochastic discrete choice models and user classes, this work allows for a granular modelling of user attributes and their preferences in regard to charging station characteristics. We adopt a simulation approach and precompute error terms for each option available to users for a given number of scenarios. This results in a bilevel optimisation model that is, however, intractable for all but the simplest instances. Our major contribution is a reformulation into a maximum covering model, which uses the precomputed error terms to calculate the users covered by each charging station. This allows solutions to be found more efficiently than for the bilevel formulation. The maximum covering formulation remains intractable in some instances, so we propose rolling horizon, greedy, and greedy randomised adaptive search procedure heuristics to obtain good-quality solutions more efficiently. Extensive computational results are provided, and they compare the maximum covering formulation with the current state of the art for both exact solutions and the heuristic methods. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This work was supported by Hydro-Québec and the Natural Sciences and Engineering Research Council of Canada [Discovery Grant 2017-06054; Collaborative Research and Development Grant CRDPJ 536757–19]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2022.0185 .

We study the network pricing problem where the leader maximizes revenue by determining the optimal amounts of tolls to charge on a set of arcs, under the assumption that the followers will react rationally and choose the shortest paths to travel. Many distinct single-level reformulations of this bilevel optimization program have been proposed; however, their relationship has not been established. In this paper, we aim to build a connection between those reformulations and explore the combination of the path representation with various modeling options, allowing us to generate 12 different reformulations of the problem. Moreover, we propose a new path enumeration scheme, path-based preprocessing, and hybrid framework to further improve performance and robustness when solving the final model. We provide numerical results, comparing all the derived reformulations and confirming the efficiency of the novel dimensionality reduction procedures.

Kidney transplant is the preferred method of treatment for patients suffering from kidney failure. However, not all patients can find a donor which matches their physiological characteristics. Kidney exchange programs (KEPs) seek to match such incompatible patient-donor pairs together, usually with the main objective of maximizing the total number of transplants. Since selecting one optimal solution translates to a decision on who receives a transplant, it has a major effect on the lives of patients. The current practice in selecting an optimal solution does not necessarily ensure fairness in the selection process. In this paper, the existence of multiple optimal plans for a KEP is explored as a mean to achieve individual fairness. We propose the use of randomized policies for selecting an optimal solution in which patients' equal opportunity to receive a transplant is promoted. Our approach gives rise to the problem of enumerating all optimal solutions, which we tackle using a hybrid of constraint programming and linear programming. The advantages of our proposed method over the common practice of using the optimal solution obtained by a solver are stressed through computational experiments. Our methodology enables decision makers to fully control KEP outcomes, overcoming any potential bias or vulnerability intrinsic to a deterministic solver.

Scope and Mission

Learning heuristics for combinatorial optimization problems through graph neural networks have recently shown promising results on some classic NP-hard problems. These are single-level optimization problems with only one player. Multilevel combinatorial optimization problems are their generalization, encompassing situations with multiple players taking decisions sequentially. By framing them in a multi-agent reinforcement learning setting, we devise a value-based method to learn to solve multilevel budgeted combinatorial problems involving two players in a zero-sum game over a graph. Our framework is based on a simple curriculum: if an agent knows how to estimate the value of instances with budgets up to $B$, then solving instances with budget $B+1$ can be done in polynomial time regardless of the direction of the optimization by checking the value of every possible afterstate. Thus, in a bottom-up approach, we generate datasets of heuristically solved instances with increasingly larger budgets to train our agent. We report results close to optimality on graphs up to $100$ nodes and a $185 \times$ speedup on average compared to the quickest exact solver known for the Multilevel Critical Node problem, a max-min-max trilevel problem that has been shown to be at least $\Sigma_2^p$-hard.

We consider a bilevel integer programming model that extends the classic 0–1 knapsack problem in a very natural way. The model describes a Stackelberg game where the leader’s decision interdicts a subset of the knapsack items for the follower. As this interdiction of items substantially increases the difficulty of the problem, it prevents the application of the classical methods for bilevel programming and of the specialized approaches that are tailored to other bilevel knapsack variants. Motivated by the simple description of the model, by its complexity, by its economic applications, and by the lack of algorithms to solve it, we design a novel viable way for computing optimal solutions. Finally, we present extensive computational results that show the effectiveness of the new algorithm on instances from the literature and on randomly generated instances.