Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
R. Chandrasekaran, “Integer programming problems for which a simple rounding type algorithm works,” in Progress in Combinatorial Optimization,Waterloo, Ont., 1982, Academic Press: Toronto, Ont., 1984, pp. 101–106.
V. Chandru and J.N. Hooker, “Extended Horn sets in propositional logic,” J. Assoc. Comput. Mach., vol. 38, no. 1, pp. 205–221, 1991.
R.W. Cottle and A.F. Veinott, Jr., “Polyhedral sets having a least element,” Math. Programming, vol. 3, pp. 238–249, 1972.
Chuang Yin Dang, Triangulations and simplicial methods, vol. 421 of Lecture Notes in Economics and Mathematical Systems, Springer-Verlag: Berlin, 1995.
Chuang Yin Dang and van H. Maaren, “A simplicial approach to the determination of an integer point of a simplex,” Math. Oper. Res., vol. 23, no. 2, pp. 403–415, 1998.
Chuang Yin Dang and van H. Maaren, “An abitrary starting variable dimension algorithm for computing an integer point of a simplex,” Comp. Opt. And Appl., vol. 14, pp. 133–155, 1999.
W.F. Dowling and J.H. Gallier, “Linear-time algorithms for testing the satisfiability of propositional Horn formulae,” J. Logic Programming, vol. 1, no. 3, pp. 267–284, 1984.
B. Curtis Eaves, “Computing Kakutani fixed points,” SIAM J. Appl. Math., vol. 21, pp. 236–244, 1971.
W. Forster, “Computing all solutions of systems of polynomial equations by simplicial fixed point algorithms,” in The Computation and Modelling of Economic Equilibria, Tilburg, 1985, vol. 167 of Contrib. Econom. Anal., North-Holland: Amsterdam, 1987, pp. 39–57.
J. Franco, “Relative size of certain polynomial time solvable subclasses of satisfiability,” in Satisfiability Problem: Theory and Applications, Piscataway, NJ, 1996, vol. 35 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Amer. Math. Soc.: Providence, RI, 1997, pp. 211–233.
R.M. Freund, “Variable dimension complexes. II. A unified approach to some combinatorial lemmas in topology,” Math. Oper. Res., vol. 9, no. 4, pp. 498–509, 1984.
F. Glover, “A bound escalation method for the solution of integer linear programs,” Cahiers Centre Études Recherche Opér., vol. 6, pp. 131–168, 1964.
D.S. Hochbaum and J. Naor, “Simple and fast algorithms for linear and integer programs with two varibles per inequality,” SIAM J. Comput., vol. 23, no. 6, pp. 1179–1192, 1994.
M. Kojima, “Studies on piecewise-linear approximations of piecewise-C 1 mappings in fixed points and complementarity theory,” Math. Oper. Res., vol. 3, no. 1, pp. 17–36, 1978.
H.W. Kuhn, “ Finding roots of polynomials by pivoting,” in Fixed Points: Algorithms and Applications, Proc. First Internat. Conf., Clemson Univ., Clemson, S.C., 1974, Academic Press: New York, 1977, pp. 11–39.
J.C. Lagarias, “ The computational complexity of simultaneous Diophantine approximation problems,” SIAMS J. Comput., vol. 14, no. 1, pp. 196–209, 1985.
A. Pnueli, “A method of truncated relaxation for integer programming,” in RC-2267,YorktownHeights: New York, 1968.
H. Scarf, The Computatioal of Economic Equilibria, Yale University Press: New Hasven, Conn., 1973. With the collaboration of Terja Hansen, Cowles Foundation Monograph, No. 24.
M.J. Todd, The Computation of Fixed Points and Applications, Lecture Notes in Economics and Mathematical Systems, vol. 124, Springer-Verlag: Berlin, 1976.
G. van der Laan and A.J.J. Talman, “Aclass of simplicial restart fixed point algorithms without an extra dimension,” Math. Programming, vol. 20, no. 1, pp. 33–48, 1981.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Van Maaren, H., Dang, C. Simplicial Pivoting Algorithms for a Tractable Class of Integer Programs. Journal of Combinatorial Optimization 6, 133–142 (2002). https://doi.org/10.1023/A:1013847510365
Issue Date:
DOI: https://doi.org/10.1023/A:1013847510365