Mixed-Integer Linear Programming (MILP) lies at the core of many real-world combinatorial optimization (CO) problems, traditionally solved by branch-and-bound (B&B). A key driver influencing B&B solvers efficiency is the variable selection heuristic that guides branching decisions. Looking to move beyond static, hand-crafted heuristics, recent work has explored adapting traditional reinforcement learning (RL) algorithms to the B&B setting, aiming to learn branching strategies tailored to specific MILP distributions. In parallel, RL agents have achieved remarkable success in board games, a very specific type of combinatorial problems, by leveraging environment simulators to plan via Monte Carlo Tree Search (MCTS). Building on these developments, we introduce Plan-and-Branch-and-Bound (PlanB&B), a model-based reinforcement learning (MBRL) agent that leverages a learned internal model of the B&B dynamics to discover improved branching strategies. Computational experiments empirically validate our approach, with our MBRL branching agent outperforming previous state-of-the-art RL methods across four standard MILP benchmarks.

Mixed-Integer Linear Programming (MILP) is a powerful framework used to address a wide range of NP-hard combinatorial optimization problems, often solved by Branch and bound (B&B). A key factor influencing the performance of B&B solvers is the variable selection heuristic governing branching decisions. Recent contributions have sought to adapt reinforcement learning (RL) algorithms to the B&B setting to learn optimal branching policies, through Markov Decision Processes (MDP) inspired formulations, and ad hoc convergence theorems and algorithms. In this work, we introduce BBMDP, a principled vanilla MDP formulation for variable selection in B&B, allowing to leverage a broad range of RL algorithms for the purpose of learning optimal B&B heuristics. Computational experiments validate our model empirically, as our branching agent outperforms prior state-of-the-art RL agents on four standard MILP benchmarks.

International audience

We study the uncapacitated lot-sizing problem with uncertain demand and costs. The problem is modeled as a multistage stochastic mixed-integer linear program in which the evolution of the uncertain parameters is represented by a scenario tree. To solve this problem, we propose a new extension of the stochastic dual dynamic integer programming algorithm (SDDiP). This extension aims at being more computationally efficient in the management of the expected cost-to-go functions involved in the model, in particular by reducing their number and by exploiting the current knowledge on the polyhedral structure of the stochastic uncapacitated lot-sizing problem. The algorithm is based on a partial decomposition of the problem into a set of stochastic subproblems, each one involving a subset of nodes forming a subtree of the initial scenario tree. We then introduce a cutting plane–generation procedure that iteratively strengthens the linear relaxation of these subproblems and enables the generation of an additional strengthened Benders’ cut, which improves the convergence of the method. We carry out extensive computational experiments on randomly generated large-size instances. Our numerical results show that the proposed algorithm significantly outperforms the SDDiP algorithm at providing good-quality solutions within the computation time limit. Summary of Contribution: This paper investigates a combinatorial optimization problem called the uncapacitated lot-sizing problem. This problem has been widely studied in the operations research literature as it appears as a core subproblem in many industrial production planning problems. We consider a stochastic extension in which the input parameters are subject to uncertainty and model the resulting stochastic optimization problem as a multistage stochastic integer program. To solve this stochastic problem, we propose a novel extension of the recently published stochastic dual dynamic integer programming (SDDiP) algorithm. The proposed extension relies on two main ideas: the use of a partial decomposition of the scenario tree and the exploitation of existing knowledge on the polyhedral structure of the stochastic uncapacitated lot-sizing problem. We provide the results of extensive computational experiments carried out on large-size randomly generated instances. These results show that the proposed extended algorithm significantly outperforms the SDDiP at providing good-quality solutions for the stochastic uncapacitated lot-sizing problem. Although the paper focuses on a basic lot-sizing problem, the proposed algorithmic framework may be useful to solve more complex practical production planning problems.

We consider an uncapacitated multi-echelon lot-sizing problem within a remanufacturing system involving three production echelons: disassembly, refurbishing and reassembly. We seek to plan the production activities on this system over a multi-period horizon. We assume a stochastic environment, in which the input data of the optimization problem are subject to uncertainty. We consider a multi-stage stochastic integer programming approach relying on scenario trees to represent the uncertain information structure and propose a solution method based on an extension of the stochastic dual dynamic programming algorithm. Our results show that this approach can provide good quality solutions for large-size instances in a reasonable time and significantly outperforms the use of a stand-alone mathematical solver.

We present a new approach for scheduling independent tasks on multiple CPUs and multiple GPUs. The tasks are assumed to be parallelizable on CPUs using the moldable model: the final number of cores allotted to a task can be decided and set by the scheduler. More precisely, we design an algorithm aiming at minimizing the makespan-the maximum completion time of all tasks-for this scheduling problem. The proposed algorithm combines a dual approximation scheme with a fast integer linear program (ILP). It determines both the partitioning of the tasks, i.e., whether a task should be mapped to CPUs or a GPU, and the number of CPUs allotted to a moldable task if mapped to the CPUs. A worst-case analysis shows that the algorithm has an approximation ratio of 3/2 + ε. Since the time complexity of the ILP-based algorithm could be non-polynomial, we also present a polynomial-time algorithm with an approximation ratio of 2 + ε. We complement the theoretical analysis of our two novel algorithms with a simulation study. In these simulations, we compare our algorithms to a modified version of the classical HEFT algorithm, which we adapted to handle moldable tasks. The simulation results show that our algorithm with the (3/2 + ε)-approximation ratio produces significantly shorter schedules than the modified HEFT for most of the instances. In addition, our results provide evidence that our ILP-based algorithm can solve larger problem instances in a reasonable amount of time.

Summary More and more computers use hybrid architectures combining multi‐core processors and hardware accelerators such as graphics processing units (GPUs). We present in this paper a new method for scheduling efficiently parallel applications with m CPUs and k GPUs, where each task of the application can be processed either on a core (CPU) or on a GPU. The objective is to minimize the maximum completion time (makespan). The corresponding scheduling problem is Non‐deterministic Polynomial (NP)‐time hard, Copyright © 2014 John Wiley & Sons, Ltd.

Today, many high performance computing platforms use hybrid architectures combining multi-core processors and hardware accelerators like GPUs (Graphic Processing Units). This paper presents a new method for scheduling tasks for biological sequence comparison applications with CPUs and GPUs. This strategy is called SWDUAL and is based on a dual approximation scheme for determining which tasks are most suitable to be executed on the GPUs. The objective is to obtain fast execution time and minimize the idle time on each PE (Processing Element). It is implemented using a master-slave model. Results obtained when sequences were compared to five public genomic databases show that this method allows to reduce the execution time on hybrid platforms when compared to other public available implementations.