×

Supernode processing of mixed-integer models. (English) Zbl 0819.90065

Summary: This paper discusses processing software for large scale mixed-integer optimization models. The software is part of the Mathematical OPtimization System MOPS which contains algorithms for solving large- scale LP and mixed-integer programs. The processing techniques are implemented in such a way that they can be applied not only initially but also during the branch-and-bound algorithm.
This paper discusses only a subset of the processing techniques included in MOPS. Algorithmic and software design aspects of the branch-and-bound process are not part of this paper.

MSC:

90C11 Mixed integer programming
90C06 Large-scale problems in mathematical programming

Software:

MOPS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Brearley, A.L., Mitra, G. and Williams, H.P., ?Analysis of mathematical programming problems prior to applying the simplex algorithm,?Math. Prog., 8, 54-83, 1975. · Zbl 0317.90037 · doi:10.1007/BF01580428
[2] Crowder, H., Johnson, E.L., and Padberg, M.W., ?Solving large-scale zero-one linear programming problems,?Oper. Res., 31, 803-834, 1983. · Zbl 0576.90065 · doi:10.1287/opre.31.5.803
[3] Dietrich, B.L. and Escudero, L.F., ?Coefficient reduction for knapsack constraints in 0-1 programs with VUBs,?Oper. Res. Lett., 9, 9-14, 1990. · Zbl 0701.90063 · doi:10.1016/0167-6377(90)90034-3
[4] Dietrich, B.L. and Escudero, L.F., ?Coefficient reduction with cover inequalities,? RC 14913, IBM, T. J. Watson Research Center, Yorktown Heights, N.Y., 1989.
[5] Dietrich, B.L., Escudero, L.F., and Chance, F., ?Efficient reformulation for 0-1 programms?methods and computational results,?Discrete Applied Mathematics, 42, 147-175, 1993. · Zbl 0776.90056 · doi:10.1016/0166-218X(93)90044-O
[6] Guignard, M. and Spielberg, K., ?Logical reduction methods in zero-one programming (minimal preferred variables),?Oper. Res., 29, 49-74, 1981. · Zbl 0452.90044 · doi:10.1287/opre.29.1.49
[7] Hoffmann, K. and Padberg, M.W., ?Improving LP-representations of zero-one linear programs for branch-and-cut,?ORSA Journal on Computing, 3, 121-134, 1991. · Zbl 0755.90062
[8] Hoffmann, K. and Padberg, M.W., ?LP-based combinatorial problem solving,?Annals of Operations Research, 4, 145-194, 1985. · doi:10.1007/BF02022040
[9] Johnson, E.L., Kostreva, M.M. and Suhl, U.H., ?Solving 0-1 integer programming problems arising from large-scale planning models,?Oper. Res., 35, 803-819, 1985. · Zbl 0569.90056 · doi:10.1287/opre.33.4.803
[10] Johnson, E.L. and Padberg, M.W., ?Degree?Two Inequalities, Clique Facets and Biperfect Graphs,?Ann. Discrete Mathematics, 16, 169-187, 1982. · Zbl 0523.52009
[11] Mairs, T.G., Wakefield, G.W., Johnson, E.L., and Spielberg, K., ?On a production allocation and allocation and distribution problem,?Management Science, 24, 1622-1630, 1978. · doi:10.1287/mnsc.24.15.1622
[12] Nemhauser, G.L. and Wolsey, L.A., ?Integer and Combinatorial Optimization,? Wiley, New York, 1988. · Zbl 0652.90067
[13] Savelsbergh, M.W.P., ?Preprosessing and Probing Techniques for Mixed Integer Programming Problems,?ORSA Journal on Computing, to appear 1994. · Zbl 0814.90093
[14] Spielberg, K. and Suhl, U.H., ?An experimental software system for large scale 0-1 problems with efficient data structures and access to MPSX/370,? IBM Research Report RC 8219, IBM T. J. Watson Research Center, Yorktown Heights, N.Y., 1980.
[15] Suhl, U.H., ?Solving large-scale mixed integer programs with fixed charge variables?,Math. Programming, 32, 165-182, 1985. · Zbl 0565.90049 · doi:10.1007/BF01586089
[16] Suhl, U.H. and Suhl, L.M., ?Computing Sparse LU Factorizations for Large-Scale Linear Programming Bases,?ORSA Journal on Computing, 2, 325-335, 1990. · Zbl 0755.90059
[17] Suhl, L.M. and Suhl, U.H., ?A Fast LU-update for linear programming,?Annals of Operations Research, 43, 33-47, 1993. · Zbl 0784.90049 · doi:10.1007/BF02025534
[18] Suhl, U.H., ?MOPS?Mathematical Optimization System,?European Journal of Operational Research, 72, 312-322, 1994. · Zbl 0800.90690 · doi:10.1016/0377-2217(94)90312-3
[19] Van Roy, T. and Wolsey, L.A., ?Solving mixed integer programming problems using automatic reformulation,?Oper. Res., 35, 45-57, 1987. · Zbl 0614.90082 · doi:10.1287/opre.35.1.45
[20] Williams, H.P., ?Model Building in Mathematical Programming,? Wiley, N.Y., 1978. · Zbl 0384.90079
[21] Wolsey, L.A., ?Tight formulations for mixed integer programming: A survey,?Math. Programming, 45, 173-191, 1989. · Zbl 0674.90072 · doi:10.1007/BF01589102
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.