Deciding the best way to schedule operations in a computational graph representing a neural network is a central problem in compilers [1]}, [2]}, [3]}.
We can associate a DAG to a computational graph in such a way that nodes represent operations ("ops"), and incoming/outgoing edges represent operands/results of these operations.
Every time one executes an op, the inputsWe use "inputs" and "operands" interchangeably throughout the paper. to that op need to be in memory, and memory for the outputs needs to be allocated. Therefore, each node of the DAG carries a label
\(m : V \rightarrow \mathbb {N}\)  specifying
the memory required to store the output of that op.
A typical first step in scheduling a DAG is to identify topological orders to execute operations.
Compilers for edge devices, which have limited memory, aim at choosing the optimal topological order that minimizes the peak memory footprint [3]}. We focus therefore on the peak local memory usage minimization task, which can be formulated as the following combinatorial optimization problem on a labeled DAG \(G=(V,E,m)\) :
\(\min _{\sigma \in {\cal T}_G} \sigma ),\qquad \sigma ) \equiv \max (M_1(\sigma ), \dots , M_{|V|}(\sigma )),\) 
