Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Soft Computing
Published in: Soft Computing 9/2019

28-01-2019 | Focus

Computational study of separation algorithms for clique inequalities

Authors: Francesca Marzi, Fabrizio Rossi, Stefano Smriglio

Published in: Soft Computing | Issue 9/2019

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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.
previous article Multi-objective stable matching and distributional constraints
next article Implementation of an intelligent hybrid simulation systems for WMNs based on particle swarm optimization and simulated annealing: performance evaluation for different replacement methods

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
Literature
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
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
Hoffman K, Padberg M (1993) Solving airline crew scheduling problems by branch-and-cut. Manag Sci 39(6):657–682CrossRefMATH
Johnson DJ, Trick MA (eds) (1996) Cliques, coloring, and satisfiability: second DIMACS implementation challenge, Workshop, October 11–13, 1993. American Mathematical Society, Boston, MA
Nemhauser GL, Sigismondi G (1992) A strong cutting plane/branch-and-bound algorithm for node packing. J Oper Res Soc 43(5):443–457CrossRefMATH
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
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
Metadata
Title
Computational study of separation algorithms for clique inequalities
Authors
Francesca Marzi
Fabrizio Rossi
Stefano Smriglio
Publication date
28-01-2019
Publisher
Springer Berlin Heidelberg
Published in
Soft Computing / Issue 9/2019
Print ISSN: 1432-7643
Electronic ISSN: 1433-7479
DOI
https://doi.org/10.1007/s00500-019-03769-y

Other articles of this Issue 9/2019

Soft Computing 9/2019 Go to the issue

Focus

Sparse analytic hierarchy process: an experimental analysis

Focus

The Minimum Routing Cost Tree Problem

Methodologies and Application

Patch-based fuzzy clustering for image segmentation

Methodologies and Application

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

Focus

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

Methodologies and Application

A survey on handling computationally expensive multiobjective optimization problems with evolutionary algorithms

Premium Partner

    Image Credits