TY - JOUR
T1 - Simplicial pivoting algorithms for a tractable class of integer programs
AU - Van Maaren, H.
AU - Dang, C.
PY - 2002/6
Y1 - 2002/6
N2 - We present a tractable class of integer feasibility problems. This class of max-closed IP problems was studied in somewhat restricted form by Glover, Pnueli, Hochbaum and Chandrasekaran and has a logic counterpart known as the class of Horn formulas. First we modify the existing algorithms in order to avoid the related recognition problem. Then we show that in order to solve these max-closed IP problems, simplicial path following methods can be used. This is important because these methods are flexible with respect to starting conditions, which make them more suitable than the top-down truncation algorithms that have been suggested.
AB - We present a tractable class of integer feasibility problems. This class of max-closed IP problems was studied in somewhat restricted form by Glover, Pnueli, Hochbaum and Chandrasekaran and has a logic counterpart known as the class of Horn formulas. First we modify the existing algorithms in order to avoid the related recognition problem. Then we show that in order to solve these max-closed IP problems, simplicial path following methods can be used. This is important because these methods are flexible with respect to starting conditions, which make them more suitable than the top-down truncation algorithms that have been suggested.
KW - Horn formulas
KW - Integer programming
KW - Simplicial algorithms
UR - http://www.scopus.com/inward/record.url?scp=0036604766&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-0036604766&origin=recordpage
U2 - 10.1023/A:1013847510365
DO - 10.1023/A:1013847510365
M3 - 21_Publication in refereed journal
VL - 6
SP - 133
EP - 142
JO - Journal of Combinatorial Optimization
JF - Journal of Combinatorial Optimization
SN - 1382-6905
IS - 2
ER -