Introduction

Ecole is a library of Extensible Combinatorial Optimization Learning Environments designed to ease the development of machine learning approaches for combinatorial optimization. More precisely, the goal of Ecole is to allow for a fast and safe prototyping of any ML for CO approach that can be formulated as a control problem (i.e., a Markov Decision Problem), as well as providing reproducible benchmarking protocols for comparison to existing approaches.

import ecole

env = ecole.environment.Branching(
    reward_function=-ecole.reward.LpIterations(),
    observation_function=ecole.observation.NodeBipartite()
)

for _ in range(10):
     observation, action_set, reward_offset, done = env.reset("path/to/problem")
     while not done:
         obs, action_set, reward, done, info = env.step(action_set[0])

Combinatorial optimization solvers typically rely on a plethora of handcrafted expert heuristics, which can fail to exploit subtle statistical similarities between problem intances. Machine Learning algorithms offer a promising candidate for replacing those heuristics, by learning data-driven policies that automatically account for such statistical relationships, and thereby creating a new kind of highly adaptive solvers [Bengio2018,]_.

For instance, many combinatorial optimization problems can be modeled using Mixed Integer Linear Programming and solved using the branch-and-bound algorithm. Despite its simplicity, the algorithm requires many non-trivial decisions, such as iteratively picking the next variable to branch on. Ecole aims at exposing these algorithmic control problems with a standard reinforcement learning API (agent / environment loop), in order to ease the exploration of new machine learning models and algorithms for learning data-driven policies.

Ecole’s interface is inspired from OpenAi Gym and will look familiar to reinforcement learning praticionners. The state-of-the-art Mixed Integer Linear Programming solver that acts as a controllable algorithm inside Ecole is SCIP.

The reader is referred to [Bengio2020] for motivation on why machine learning is a promising candidate to use for combinatorial optimization, as well as the methodology to do so.

Bengio2020

Bengio, Yoshua, Andrea Lodi, and Antoine Prouvost. “Machine learning for combinatorial optimization: a methodological tour d’horizon.European Journal of Operational Research. 2020.