## Integer linear programming formulations of the filter partitioning minimization problem

Hazhar Rahmani, **Jason M. O'Kane**

*Journal of Combinatorial Optimization*

vol. 40

pp. 431–453

2020
**Abstract**
Combinatorial filters, which take the form of labelled transition graphs,
are a general representation for filtering and inference tasks in robotics.
They are of particular interest in contexts where the objective is to
minimize the computational resources needed to execute the filter. One
specific problem is called the filter minimization (FM) problem, in which
the goal is to find, for a given original filter, a state-minimal filter
equivalent to the original filter. We consider a special case of
FM, called the filter partitioning minimization (FPM) problem, in which the
reduced filter must partition the state space of the original filter. This
problem has been proven to be NP-hard. This paper considers the practical
problem of solving FPM in spite of these hardness results. In contrast to
the best known algorithm for this problem, a heuristic approach based on
graph coloring proposed by O'Kane and Shell, we show how to convert an FPM
instance to an instance of the well-known integer linear programming (ILP)
problem. We present three distinct formulations of this reduction. Though
ILP is itself a challenging problem, reducing FPM to ILP has the advantage
that the ILP problem has been studied in great detail, and highly-optimized
solvers are readily available. We describe experiments comparing this
approach to the heuristic algorithm of O'Kane and Shell. The results show
that the proposed ILP technique performs better in computing exact
solutions as the filter sizes grow, and that the ILP approach obtains
higher-quality feasible solutions, in contexts where time limitations
prohibit the computation of exact solutions.

@article{RahOKa20,
author = {Hazhar Rahmani and Jason M. O'Kane},
journal = {Journal of Combinatorial Optimization},
pages = {431--453},
title = {Integer linear programming formulations of the filter partitioning
minimization problem},
volume = {40},
year = {2020}
}

*Last updated 2021-12-14.*