FGILP: An integer linear program solver based on function graphs

Yung Te Lai; Massoud Pedram; Sarma B.K. Vrudhula

FGILP: An integer linear program solver based on function graphs

Yung Te Lai, Massoud Pedram, Sarma B.K. Vrudhula

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Edge-Valued Binary-Decision Diagrams (EVBDD)s 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 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, has been implemented in C under the SIS environment. The preliminary results of FGILP are comparable to those of LINDO.

Original language	English (US)
Title of host publication	Proc 1993 IEEE ACM Int Conf Comput Aided Des
Editors	Anon
Publisher	Publ by IEEE
Pages	685-689
Number of pages	5
ISBN (Print)	0818644923
State	Published - Dec 1 1993
Externally published	Yes
Event	Proceedings of the 1993 IEEE/ACM International Conference on Computer-Aided Design - Santa Clara, CA, USA Duration: Nov 7 1993 → Nov 11 1993

Publication series

Name	Proc 1993 IEEE ACM Int Conf Comput Aided Des

Other

Other	Proceedings of the 1993 IEEE/ACM International Conference on Computer-Aided Design
City	Santa Clara, CA, USA
Period	11/7/93 → 11/11/93

ASJC Scopus subject areas

Engineering(all)

Cite this

@inproceedings{6d0c693394fa4501858d2bc7d5acc8a3,

title = "FGILP: An integer linear program solver based on function graphs",

abstract = "Edge-Valued Binary-Decision Diagrams (EVBDD)s 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 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, has been implemented in C under the SIS environment. The preliminary results of FGILP are comparable to those of LINDO.",

author = "Lai, {Yung Te} and Massoud Pedram and Vrudhula, {Sarma B.K.}",

year = "1993",

month = dec,

day = "1",

language = "English (US)",

isbn = "0818644923",

series = "Proc 1993 IEEE ACM Int Conf Comput Aided Des",

publisher = "Publ by IEEE",

pages = "685--689",

editor = "Anon",

booktitle = "Proc 1993 IEEE ACM Int Conf Comput Aided Des",

note = "Proceedings of the 1993 IEEE/ACM International Conference on Computer-Aided Design ; Conference date: 07-11-1993 Through 11-11-1993",

}

TY - GEN

T1 - FGILP

T2 - Proceedings of the 1993 IEEE/ACM International Conference on Computer-Aided Design

AU - Lai, Yung Te

AU - Pedram, Massoud

AU - Vrudhula, Sarma B.K.

PY - 1993/12/1

Y1 - 1993/12/1

N2 - Edge-Valued Binary-Decision Diagrams (EVBDD)s 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 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, has been implemented in C under the SIS environment. The preliminary results of FGILP are comparable to those of LINDO.

AB - Edge-Valued Binary-Decision Diagrams (EVBDD)s 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 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, has been implemented in C under the SIS environment. The preliminary results of FGILP are comparable to those of LINDO.

UR - http://www.scopus.com/inward/record.url?scp=0027868262&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0027868262&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0027868262

SN - 0818644923

T3 - Proc 1993 IEEE ACM Int Conf Comput Aided Des

SP - 685

EP - 689

BT - Proc 1993 IEEE ACM Int Conf Comput Aided Des

A2 - Anon, null

PB - Publ by IEEE

Y2 - 7 November 1993 through 11 November 1993

ER -

FGILP: An integer linear program solver based on function graphs

Abstract

Publication series

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this