State-of-the-art Mixed Integer Linear Programming (MILP) solvers combine systematic tree search with a plethora of hard-coded heuristics, such as branching rules. While approaches to learn branching strategies have received increasing attention and have shown very promising results, most of the literature focuses on learning fast approximations of the \emph{strong branching} rule. Instead, we propose to learn branching rules from scratch with Reinforcement Learning (RL). We revisit the work of Etheve et al. (2020) and propose a generalization of Markov Decisions Processes (MDP), which we call \emph{tree MDP}, that provides a more suitable formulation of the branching problem. We derive a policy gradient theorem for tree MDPs that exhibits a better credit assignment compared to its temporal counterpart. We demonstrate through computational experiments that this new framework is suitable to tackle the learning-to-branch problem in MILP, and improves the learning convergence.

We obtain a 1.5-approximation algorithm for the metric uncapacitated facility location (UFL) problem, which improves on the previously best known 1.52-approximation algorithm by Mahdian, Ye, and Zhang. Note that the approximability lower bound by Guha and Khuller is $1.463\dots$. An algorithm is a ($\lambda_f$,$\lambda_c$)-approximation algorithm if the solution it produces has total cost at most $\lambda_f\cdot F^*+\lambda_c\cdot C^*$, where $F^*$ and $C^*$ are the facility and the connection cost of an optimal solution. Our new algorithm, which is a modification of the $(1+2/e)$-approximation algorithm of Chudak and Shmoys, is a $(1.6774,1.3738)$-approximation algorithm for the UFL problem and is the first one that touches the approximability limit curve $(\gamma_f,1+2e^{-\gamma_f})$ established by Jain, Mahdian, and Saberi. As a consequence, we obtain the first optimal approximation algorithm for instances dominated by connection costs. When combined with a $(1.11,1.7764)$-approximation algorithm proposed by Jain et al., and later analyzed by Mahdian et al., we obtain the overall approximation guarantee of 1.5 for the metric UFL problem. We also describe how to use our algorithm to improve the approximation ratio for the 3-level version of UFL.

At the IPCO VI conference Cornuéjols and Dawande proposed a set of 0-1 linear programming instances that proved to be very hard to solve by traditional methods, and in particular by linear programming-based branch-and-bound. They offered these market split instances as a challenge to the integer programming community. The market split problem can be formulated as a system of linear diophantine equations in 0-1 variables. In our study we use the algorithm of Aardal, Hurkens, and Lenstra (1998) based on lattice basis reduction. This algorithm is not restricted to deal with market split instances only but is a general method for solving systems of linear diophantine equations with bounds on the variables. We show computational results from solving both feasibility and optimization versions of the market split instances with up to 7 equations and 60 variables and discuss various branching strategies and their effect on the number of enumerated nodes. To our knowledge, the largest feasibility and optimization instances solved before had 6 equations and 50 variables, and 4 equations and 30 variables, respectively. We also present a probabilistic analysis describing how to compute the probability of generating infeasible market split instances. By generating instances the way prescribed by Cornuéjols and Dawande, one obtains relatively many feasible instances for sizes larger than 5 equations and 40 variables.

We present new approximation algorithms for several facility location problems.In each facility location problem that we study, there is a set of locations at which we may build a facility (such as a warehouse), where the cost of building at location i is ~i; ftiermore, there is a set of client locations (such as stores) that require to be serviced by a facility, and if a client at location j is assigned to a facility at location i, a cost of cl] is incurred that is proportional to the distance between i and j.The objective is to determine a set of locations at which to open facilities so as to minimize the total facility and assignment costs.In the incapacitated case, each facility can service an unlimited number of clients, whereas in the capacitated case, each facility can serve, for example, at most u clients.These models and a number of closely related ones have been studied extensively in the Operations Research literature.We shall consider the case in which the distances between locations are non-negative, symmetric and satisfy the triangle inequality.For the incapacitated facility location, we give a polynomial-time algorithm that finds a solution of cost within a factor of 3.16 of the optimal.This is the first constant performance guarantee known for this problem.We also present approximation algorithms with constant performance guarantees for a number of capacitated models as well as a generalization in which there is a 2-level hierarchy of facilities.Our results are based on the filtering and rounding technique of Lin & Wter.We also give a randomized variant of this technique that can then be derandomized to yield improved deterministic performance guarantees.

We study the two-level uncapacitated facility location (TUFL) problem. Given two types of facilities, which we call y-facilities and z-facilities, the problem is to decide which facilities of both types to open, and to which pair of y- and z-facilities each client should be assigned, in order to satisfy the demand at maximum profit. We first present two multi-commodity flow formulations of TUFL and investigate the relationship between these formulations and similar formulations of the one-level uncapacitated facility location (UFL) problem. In particular, we show that all nontrivial facets for UFL define facets for the two-level problem, and derive conditions when facets of TUFL are also facets for UFL. For both formulations of TUFL, we introduce new families of facets and valid inequalities and discuss the associated separation problems. We also characterize the extreme points of the LP-relaxation of the first formulation. While the LP-relaxation of a multi-commodity formulation provides good bounds in general, the number of variables and constraints grows rapidly with the size of the problem instance. An alternative model of TUFL is a single-commodity fixed-charge network flow problem. Rardin and Wolsey showed that by projecting a so-called multi-commodity extended formulation of fixed-charge network flow problems onto the space of flow variables used in the weaker flow formulation, a broad class of valid inequalities can be obtained. We discuss a subclass of these inequalities for TUFL that seems particularly useful for computational purposes.