Branch-and-cut is one of the most successful methods to exactly solve combinatorial optimization problems. A key decision problem in branch-and-cut is cut generation —the problem of deciding whether to generate cuts or to branch at each node of the search tree. This decision significantly impacts performance: generating efficient cuts can remove a substantial portion of the infeasible region and reduce tree size. However, in many cases, generating cuts slows runtime as separation routines could be time-consuming, and the violated cuts found by these routines could be inefficient. Hence, a smart strategy for generating cuts is crucial for the efficiency of branch-and-cut algorithms. There are two main types of cuts: generic cuts derived from the integrality of variables and combinatorial cuts based on the facial structure of the convex hull of feasible solutions. Combinatorial cuts are particularly determinant in branch-and-cut for many NP-hard combinatorial optimization problems, e.g., the Traveling Salesman Problem and the Max-Cut problem. In this article, we propose a framework combining supervised learning and deep reinforcement learning to learn strategies for generating combinatorial cuts in branch-and-cut. Our framework contains two components: a cut detector to predict the cut existence and a cut evaluator to choose between generating cuts and branching. We conduct experiments on two well-known combinatorial cut classes: subtour elimination constraints for the Traveling Salesman problem and cycle inequalities for the Max-Cut problem. Our results show that the proposed framework outperforms the commonly used strategies for cut generation, even on instances larger than those used for training.

Abstract In this article, we consider a particular case of bi‐objective optimization (BOO), called bi‐objective minimization (BOM), where the two objective functions to be minimized take only positive values. As well as for BOO, most of the methods proposed in the literature for solving BOM focus on computing the Pareto‐optimal solutions representing different trade‐offs between two objectives. However, it may be difficult for a central decision‐maker to determine the preferred solutions due to the huge number of solutions in the Pareto set. We propose a novel criterion for selecting the preferred Pareto‐optimal solutions by introducing the concept of ‐Nash Fairness (‐) solutions inspired by the definition of proportional fairness. The ‐ solutions are the feasible solutions achieving some proportional nash equilibrium between the two objectives. The positive parameter is introduced to reflect the relative importance of the first objective to the second one. For this work, we will discuss existential and algorithmic questions about the ‐ solutions by first showing their existence for BOM. Furthermore, the ‐ solution set can be a strict subset of the Pareto set. As there are possibly many ‐ solutions, we focus on extreme ‐ solutions achieving the smallest values for one of the objectives. Then, we propose two Newton‐based iterative algorithms for finding extreme ‐ solutions. Finally, we present computational results on some instances of the bi‐objective travelling salesman problem (BOTSP) and the bi‐objective shortest path problem.

International audience

Managing autonomous vehicles inside restricted areas for internal logistics purpose raises the question of safety. We deal here with this issue, and propose a Safe Shortest Path model, which we handle first through tree search in a static context, and next through learning techniques in a dynamic context.

International audience

International audience

We deal here with a fleet of autonomous vehicles which is required to perform internal logistics tasks inside some protected area.This fleet is supposed to be ruled by a hierarchical supervision architecture, which, at the top level distributes and schedules Pick up and Delivery tasks, and, at the lowest level, ensures safety at the crossroads and controls the trajectories.We focus here on the top level, while introducing a time dependent estimation of the risk induced by the traversal of any arc at a given time.We set a model, state some structural results, and design, in order to route and schedule the vehicles according to a well-fitted compromise between speed and risk, a bi-level algorithm and a A* algorithm which both relies on a reinforcement learning scheme.

We study the classical linear programing relaxation of the ‐median problem, together with the so‐called “odd directed cycle inequalities.” We characterize in terms of forbidden subgraphs, the oriented graphs for which this system of inequalities defines an integral polytope. This completes the study started in Baïou and Barahona (2016), where oriented graphs with no triangles were treated.

We study the maximum node-weighted induced bipartite subgraph problem in planar graphs with maximum degree three. We show that this is polynomially solvable. It was shown in Choi, Nakajima, and Rim [SIAM J. Discrete Math., 2 (1989), pp. 38--47] that it is NP-complete if the maximum degree is four. We extend these ideas to the problem of balancing signed graphs. We also consider maximum weighted induced acyclic subgraphs of planar directed graphs. If the maximum degree is three, it is easily shown that this is polynomially solvable. We show that for planar graphs with maximum degree four the same problem is NP-complete.

We study a prize-collecting version of the uncapacitated facility location problem and of the p-median problem. We say that the uncapacitated facility location polytope has the intersection property if adding the extra equation that fixes the number of opened facilities does not create any fractional extreme point. We characterize the graphs for which this polytope has the intersection property and give a complete description of the polytope for this class of graphs. This characterization yields a polynomial time cutting plane algorithm for these graphs. We also give a combinatorial polynomial time algorithm to solve the different variants of the p-median and facility location problems studied in this paper.

We study a system of linear inequalities associated with some facility location problems. We show that this system defines a polytope with integer extreme points if and only if the graph does not contain a certain type of odd cycles. We also derive odd cycle inequalities and give a separation algorithm.

Abstract Given a graph where increasing the weight of an edge has a nondecreasing convex piecewise linear cost, we study the problem of finding a minimum cost increase of the weights so that the value of all minimum spanning trees is equal to some target value. Frederickson and Solis‐Oba gave an algorithm for the case when the costs are linear. We give a different derivation of their algorithm, and we slightly extend it to deal with convex piecewise linear costs. We formulate the problem as a combinatorial linear program and show how to produce primal and dual solutions. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008

Given a graph G=(V,E) with weights on its edges and a set of specified nodes $S\subseteq V$, the Steiner 2-edge survivable network problem is to find a minimum weight subgraph of G such that between every two nodes of S there are at least two edge-disjoint paths. This problem has applications to the design of reliable communication and transportation networks. In this paper, we give a complete linear description of the polytope associated with the solutions to this problem when the underlying graph is series-parallel. We also discuss related polyhedra.