×

On identifying dominant cliques. (English) Zbl 1035.90095

Summary: In this paper we present two graph theory-based approaches for identifying dominant cliques with respect to a given set of cliques. As a consequence, the related 0-1 model can be tightened by replacing the initial set of cliques by the new ones. The first approach that we introduce identifies all dominant cliques; the second one identifies a subset of them, but it usually reduces the computing effort. Computational results are reported on some MIPLIB instances, where the original models have been enlarged by appending inequalities identified by a hybrid algorithm of both approaches and a state-of-the-art optimization package is used for problem solving.

MSC:

90C35 Programming involving graphs or networks
90C10 Integer programming
90C09 Boolean programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Atamtürk, A.; Nemhauser, G. L.; Savelsbergh, M. W.P., Conflict graphs in solving integer programming problems, European Journal of Operational Research, 121, 1, 40-55 (2000) · Zbl 0959.90034
[2] R.E. Bixby, S. Ceria, C.M. McZeal, M.W.P. Savelsbergh, An updated mixed integer programming library: MIPLIB 3.0, Technical Report TR98-03, Department of Computational and Applied Mathematics, Rice University, 1998 (Downloadable from website http://www.caam.rice.edu/ bixby/miplib/miplib.html; R.E. Bixby, S. Ceria, C.M. McZeal, M.W.P. Savelsbergh, An updated mixed integer programming library: MIPLIB 3.0, Technical Report TR98-03, Department of Computational and Applied Mathematics, Rice University, 1998 (Downloadable from website http://www.caam.rice.edu/ bixby/miplib/miplib.html
[3] Bixby, R. E.; Lee, E. K., Solving a truck dispatching scheduling problem using branch-and-cut, Operations Research, 46, 3, 355-367 (1998) · Zbl 0987.90034
[4] Bron, C.; Kerbosch, J., Finding all cliques of an undirected graph, Communications of the ACM, 16, 9, 575-577 (1973) · Zbl 0261.68018
[5] Carraghan, R.; Pardalos, P. M., An exact algorithm for the maximum clique problem, Operations Research Letters, 9, 6, 375-382 (1990) · Zbl 0711.90080
[6] Crowder, H.; Johnson, E. L.; Padberg, M., Solving large-scale zero-one linear programming problems, Operations Research, 31, 5, 803-834 (1983) · Zbl 0576.90065
[7] Dietrich, B. L.; Escudero, L. F.; Chance, F., Efficient reformulation for 0-1 programs-methods and computational results, Discrete Applied Mathematics, 42, 2,3, 147-175 (1993) · Zbl 0776.90056
[8] Dietrich, B. L.; Escudero, L. F.; Garı́n, A.; Pérez, G., \(O(n)\) procedures for identifying maximal cliques and non-dominated extensions of consecutive minimal covers and alternates, Top, 1, 1, 139-160 (1993) · Zbl 0820.90074
[9] Escudero, L. F.; Garı́n, A.; Pérez, G., On using clique overlapping for detecting knapsack constraint redundancy and infeasibility in 0-1 mixed integer programs, Top, 4, 1, 87-98 (1996) · Zbl 0855.90091
[10] Escudero, L. F.; Martello, S.; Toth, P., On tightening 0-1 programs based on extensions of pure 0-1 knapsack and subset-sum problems, Annals of Operations Research, 81, 379-404 (1998) · Zbl 0910.90214
[11] Escudero, L. F.; Muñoz, S., On characterizing tighter formulations for 0-1 programs, European Journal of Operational Research, 106, 1, 172-176 (1998)
[12] Gondran, M.; Minoux, M., Graphs and Algorithms (1984), John Wiley: John Wiley New York · Zbl 1117.06010
[13] Guignard, M.; Spielberg, K., Logical reduction methods in zero-one programming. Minimal preferred variables, Operations Research, 29, 1, 49-74 (1981) · Zbl 0452.90044
[14] ILOG CPLEX 7.0-User’s Manual, France, 2000; ILOG CPLEX 7.0-User’s Manual, France, 2000
[15] Johnson, E. L.; Nemhauser, G. L.; Savelsbergh, M. W.P., Progress in linear programming-based algorithms for integer programming: An exposition, INFORMS Journal on Computing, 12, 1, 2-23 (2000) · Zbl 1052.90048
[16] Muñoz, S., A correction of the justification of the Dietrich-Escudero-Garı́n-Pérez \(O(n)\) procedures for identifying maximal cliques and non-dominated extensions of consecutive minimal covers and alternates, Top, 3, 1, 161-165 (1995) · Zbl 0856.90080
[17] S. Muñoz, Reforzamiento de Modelos en Programación Lineal 0-1, Ph.D. Thesis, Departamento de Estadı́stica e Investigación Operativa I, Universidad Complutense de Madrid, 1999; S. Muñoz, Reforzamiento de Modelos en Programación Lineal 0-1, Ph.D. Thesis, Departamento de Estadı́stica e Investigación Operativa I, Universidad Complutense de Madrid, 1999
[18] Padberg, M. W., On the facial structure of set packing polyhedra, Mathematical Programming, 5, 199-215 (1973) · Zbl 0272.90041
[19] Savelsbergh, M. W.P., Preprocessing and probing techniques for mixed integer programming problems, ORSA Journal on Computing, 6, 4, 445-454 (1994) · Zbl 0814.90093
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.