FGILP: An integer linear program solver based on function graphs

Edge-valued binary-decision diagrams (EVBDDs) are directed acyclic graphs which can represent and manipulate integer functions as effectively as ordered binary-decision diagrams (OBDDs) do for Boolean functions. They have been used to perform logic verification and compute the decomposability of Boolean functions. In this paper, we present a new EVBDD application for solving integer linear programs (ILP), which is an NP-hard problem that appears in many applications. Our approach is to combine the benefits of the EVBDD data structure (in terms of subgraph sharing and caching of computational results) with the state-of-the-art ILP solving techniques. Our program, called FGILP (Function Graph ILP) has been implemented in C under the SIS environment. The preliminary results of FGILP are comparable to those of LINDO.