nach oben

Soft Computing

Erschienen in:

28.01.2019 | Focus

Computational study of separation algorithms for clique inequalities

verfasst von: Francesca Marzi, Fabrizio Rossi, Stefano Smriglio

Erschienen in: Soft Computing | Ausgabe 9/2019

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Clique inequalities appear in linear descriptions of many combinatorial optimisation problems. In general, they form an exponential family and, in addition, the associated separation problem is strongly NP-hard, being equivalent to a maximum weight clique problem. Therefore, most of the known (both exact and heuristic) separation procedures follow the decomposition scheme of a maximum clique algorithm. We introduce a new heuristic, aimed at constructing a collection of (violated) clique inequalities covering all the edges of the underlying graph. We present an extensive computational experience showing that this closely approximates the results of an exact separation oracle while being faster than standard heuristics.

Vorheriger Artikel Multi-objective stable matching and distributional constraints

Nächster Artikel Implementation of an intelligent hybrid simulation systems for WMNs based on particle swarm optimization and simulated annealing: performance evaluation for different replacement methods

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Atamtürk A, Nemhauser GL, Savelsbergh MWP (2000) Conflict graphs in solving integer programming problems. Eur J Oper Res 121(1):40–55MathSciNetCrossRefMATH

Avella P, Boccia M, Mannino C, Vasilyev I (2017) Time-indexed formulations for the runway scheduling problem. Transp Sci 51(4):1196–1209CrossRef

Balas E, Padberg MW (1976) Set partitioning: a survey. Management sciences research report, Graduate School of Industrial Administration, Carnegie-Mellon University

Borndörfer R (1998) Aspects of set packing, partitioning, and covering. Ph. D. thesis, TU Berlin

Borndörfer R, Kormos Z (1997) An algorithm for maximum cliques. Unpublished working paper, Konrad-Zuse-Zentrum für Informationstechnik

Borndörfer R, Weismantel R (2000) Set packing relaxations of some inte]ger programs. Math Program 88(3):425–450MathSciNetCrossRefMATH

Caprara A, Salazar González JJ (1999) Separating lifted odd-hole inequalities to solve the index selection problem. Discret Appl Math 92(2):111–134MathSciNetCrossRefMATH

Carraghan R, Pardalos PM (1990) An exact algorithm for the maximum clique problem. Oper Res Lett 9(6):375–382CrossRefMATH

Corrêa RC, Delle Donne D, Koch I, Marenco J (2017) General cut-generating procedures for the stable set polytope. Discret Appl Math 245:28–41MathSciNetCrossRefMATH

de Givry S, Katsirelos G (2017) Clique cuts in weighted constraint satisfaction. In: Beck JC (ed) Principles and practice of constraint programming. Springer International Publishing, Cham, pp 97–113CrossRef

Escudero LF, Landete M, Marín A (2009) A branch-and-cut algorithm for the winner determination problem. Decis Support Syst 46(3):649–659CrossRef

Groiez M, Desaulniers G, Marcotte O (2014) Valid inequalities and separation algorithms for the set partitioning problem. INFOR: Inf Syst Oper Res 52(4):185–196MathSciNet

Grötschel M, Lovász L, Schrijver A (1988) Geometric algorithms and combinatorial optimization. Springer, BerlinCrossRefMATH

Grötschel M, Lovász L, Schrijver A (1981) The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2):169–197MathSciNetCrossRefMATH

Håstad J (1999) Clique is hard to approximate within \(n^{(1-\epsilon )}\). Acta Math 182(1):105–142MathSciNetCrossRefMATH

Hoffman K, Padberg M (1993) Solving airline crew scheduling problems by branch-and-cut. Manag Sci 39(6):657–682CrossRefMATH

Intel distribution for Python (2018) https://software.intel.com/en-us/distribution-for-python

Johnson DJ, Trick MA (eds) (1996) Cliques, coloring, and satisfiability: second DIMACS implementation challenge, Workshop, October 11–13, 1993. American Mathematical Society, Boston, MA

Letchford AN, Rossi F, Smriglio S (2018) The stable set problem: clique and nodal inequalities revisited. Optimization Online, http://www.optimization-online.org/DB_HTML/2018/05/6612.html

Nemhauser GL, Sigismondi G (1992) A strong cutting plane/branch-and-bound algorithm for node packing. J Oper Res Soc 43(5):443–457CrossRefMATH

Niskanen S, Östergård PRJ (2002) Routines for clique searching. http://users.aalto.fi/~pat/cliquer.html

Padberg MW (1973) On the facial structure of set packing polyhedra. Math Program 5(1):199–215MathSciNetCrossRefMATH

Pardalos P, Rappe J, Resende MGC (1998) An exact parallel algorithm for the maximum clique problem. In: De Leone R et al (eds) High performance algorithms and software in nonlinear optimization. Springer, Boston, pp 279–300CrossRef

Rossi F, Smriglio S (2001) A set packing model for the ground holding problem in congested networks. Eur J Oper Res 131(2):400–416MathSciNetCrossRefMATH

Spoorendonk S, Desaulniers G (2010) Clique inequalities applied to the vehicle routing problem with time windows. INFOR J 48(1):53–67MathSciNet

SCIP Optimization Suite (2018). http://scip.zib.de/

Waterer H, Johnson EL, Nobili P, Savelsbergh MWP (2002) The relation of time indexed formulations of single machine scheduling problems to the node packing problem. Math Program 93(3):477–494MathSciNetCrossRefMATH

Titel: Computational study of separation algorithms for clique inequalities
verfasst von: Francesca Marzi
Fabrizio Rossi
Stefano Smriglio
Publikationsdatum: 28.01.2019
Verlag: Springer Berlin Heidelberg
Erschienen in: Soft Computing / Ausgabe 9/2019
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-019-03769-y

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 9/2019

Novel soft fuzzy rough rings (ideals) of rings and their application in decision making

A configurational approach based on geographic information systems to support decision-making process in real estate domain

Global optimization in machine learning: the design of a predictive analytics application

Patch-based fuzzy clustering for image segmentation

A vegetable category recognition system: a comparison study for caffe and Chainer DNN frameworks

Implementation of an intelligent hybrid simulation systems for WMNs based on particle swarm optimization and simulated annealing: performance evaluation for different replacement methods