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 Process), as well as providing reproducible benchmarking protocols for comparison to existing approaches.

import ecole

env = ecole.environment.Branching(
    reward_function=-1.5 * ecole.reward.LpIterations() ** 2,
    observation_function=ecole.observation.NodeBipartite(),
)
instances = ecole.instance.SetCoverGenerator(n_rows=100, n_cols=200)

for _ in range(10):
    observation, action_set, reward_offset, done, info = env.reset(next(instances))
    while not done:
        observation, 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 approach 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.

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.