• Parametric Integer Programming
• Use case
• Dependencies
• Bibliography
• Disclaimer

Parametric Integer Programming

This is a minimum working example of Parametric Integer Programming¹ (PIP), a means to solving Integer Linear Programs (ILPs) with parameters $\theta$ in either the objective or the right-hand sides of the constraints (through duality).

$$ \begin{aligned} J^{*}(\theta )=&\min _{x\in \mathbb {R} ^{n}}f(x,\theta )\\ &{\text{subject to }}g(x,\theta )\leq 0.\\ &\theta \in \Theta \subset \mathbb {R} ^{m} \end{aligned} $$

The principal idea is to run a simplex solver but symbolically, i.e., leave the parameters unevaluated until the pivot step, at which point you branch depending on the sign of the coefficient (and already explored branches). The solution is then a piecewise affine function of the parameters.

For example, the system

$$ \begin{aligned} & \text{minimize}_{\lambda_1, \lambda_2} && z = x_1\lambda_1 + x_2\lambda_2 \\ & \text{subject to} && \lambda_1 + \lambda_2 \leq 5 \\ & && -\lambda_1 \leq 1 \\ & && -\lambda_2 \leq 2 \\ & && -\lambda_1 + \lambda_2 \leq 0 \\ & && \lambda_1, \lambda_2 \succcurlyeq 0 \\ & \text{and} && \boldsymbol {\lambda}, \mathbf {x} \in \mathbb {Z} ^{n},\end{aligned} $$

induces the following tree structure

and produces the following solution

Images from ².

Use case

What's a use-case for this technique? Suppose you have a Deep Neural Network (DNN), for which you'd like to statically plan memory allocations (for the intermediate tensors produced during a forward pass of the DNN). This is an instance of Dynamic Storage Allocation:

$$ \begin{align} \min\; & \sum{\mathtt{offset}_i}\\ \end{align} $$

where tensors $\mathtt{mem}_i$ with overlapping life-times are constrained to be ordered in the address space by

$$ \begin{align} & \mathtt{offset}_i + \mathtt{mem}_i \leq \mathtt{offset}_j + z_{ij} * \mathtt{M} \\ & \mathtt{offset}_j + \mathtt{mem}_j\leq\mathtt{offset}_i + \left(1-{z_{ij}}\right)*\mathtt{M} \end{align} $$

where $\mathtt{M}$ is a big M and $z_{ij}$ are decision variables defined

$$ z_{ij} := \begin{cases} 0 & \text{if }\mathtt{offset}_i + \mathtt{mem}_i\leq\mathtt{offset}_j\\ 1 & \text{if }\mathtt{offset}_j + \mathtt{mem}_j\leq\mathtt{offset}_i \end{cases} $$

This is clearly an Integer Linear Program (ILP) and if we treat $\mathtt{mem}_i$ as parameters we can reformulate the problem as a PIP. Using such a formulation, you can (potentially) speed up solving the ILP, thereby enabling optimal static memory allocation, at runtime. For example, using a related, but less powerful, technique called Disciplined Parametric Programming, for ResNet18, we see as much as a 10x speed up:

Dependencies

Besides the dependencies listed in requirements.txt, you will, at minimum, need a free license for Wolfram Engine. A license for Gurobi is also recommended; be sure to set GRB_LICENSE_FILE=<PATH>/gurobi.lic in the env variables.

Disclaimer

This repo is purely for illustration and experimentation. The code is guaranteed to be neither correct nor fast nor original i.e., it has, in fact, been cobbled together from various sources. Maybe one day it'll be something...

Bibliography

Footnotes

1. Parametric integer programming 1988 by Paul Feautrier ↩

2. Section 5.1 of New Algorithmics for Polyhedral Calculus via Parametric Linear Programming by Alexandre Maréchal (this is the best gentle introduction to the ideas) ↩