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.

In the context of community detection, correlation clustering (CC) provides a measure of balance for social networks as well as a tool to explore their structures. However, CC does not encompass features such as the mediation between the clusters, which could be all the more relevant with the recent rise of ideological polarization. In this work, we study correlation clustering under mediation (CCM), a new variant of CC in which a set of mediators is determined. This new signed graph clustering problem is proved to be NP-hard and formulated as an integer programming formulation. An extensive investigation of the mediation set structure leads to the development of two efficient exact enumeration algorithms for CCM. The first one exhaustively enumerates the maximal sets of mediators in order to provide several relevant solutions. The second algorithm implements a pruning mechanism, which drastically reduces the size of the exploration tree in order to return a single optimal solution. Computational experiments are presented on two sets of instances: signed networks representing voting activity in the European Parliament and random signed graphs. History: Accepted by Van Hentenryck, Area Editor for Pascal. Funding: This work was supported by Fondation Mathématique Jacques Hadamard [Grant P-2019-0031]. 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.2022.0129 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2022.0129 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Abstract We propose a two‐stage recoverable robustness approach that minimizes the recovery cost. In many applications, once the uncertainty is revealed, it can be more important to recover a solution which is as similar as possible to the nominal solution than to minimize the nominal objective value of . This for example occurs when the nominal solution is implemented on a regular basis or when the uncertainty is revealed late. We define the proactive problem which minimizes the weighted recovery costs over a discrete set of scenarios while ensuring optimality of the nominal objective value of . We model the recovery cost of a scenario by a distance between the first‐stage nominal solution and the second‐stage solution recovered for this scenario. We show for two different solution distances and that the proactive problem is ‐hard for both the integer min‐cost flow problem with uncertain arc demands and for the integer max‐flow problem with uncertain arc capacities. For these two problems, we prove that once uncertainty is revealed, even identifying a reactive solution with a minimal distance to a given solution is ‐hard for , and is polynomial for . We highlight the benefits of the proactive approach in a case study on a railroad planning problem. First, we compare it to the anchored and the ‐distance approaches. Then, we show the efficiency of the proactive solution over reactive solutions. Finally, we illustrate the recovery cost reduction when relaxing the optimality constraint on the nominal objective of the proactive solution . We also consider the min–max version of the proactive problem where we minimize the maximal recovery cost over all scenarios. We show that the same complexity results hold for this version. We also exhibit a class of problems for which the set of extreme points of the convex hull of a discrete uncertainty set always contain a worst‐case scenario. We show that this result does not hold for three distinct classes deduced from the first one.

Abstract The K‐partitioning problem consists in partitioning the nodes of a complete graph G = (V, E) with weights on the edges in exactly K clusters such that the sum of the weights of the edges inside the clusters is minimized. For this problem, we propose two node‐cluster formulations adapted from the literature on similar problems as well as two edge‐representative formulations. We introduced the first edge‐representative formulation in a previous work while the second is obtained by adding an additional set of edge variables. We compare the structure of the polytopes of the two edge‐representative formulations and identify a new family of facet‐defining inequalities. The quality of the linear relaxation and the resolution times of the four formulations are compared on various data sets. We provide bounds on the relaxation values of the node‐cluster formulations which may account for their low performances. Finally, we propose a branch‐and‐cut strategy, based on the edge‐representative formulations, which performs even better.