License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2020.8
URN: urn:nbn:de:0030-drops-120823
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12082/
Go to the corresponding LIPIcs Volume Portal

Berend, Daniel ; Twitto, Yochai

Effect of Initial Assignment on Local Search Performance for Max Sat

pdf-format:
LIPIcs-SEA-2020-8.pdf (0.7 MB)

Abstract

In this paper, we explore the correlation between the quality of initial assignments provided to local search heuristics and that of the corresponding final assignments. We restrict our attention to the Max r-Sat problem and to one of the leading local search heuristics - Configuration Checking Local Search (CCLS). We use a tailored version of the Method of Conditional Expectations (MOCE) to generate initial assignments of diverse quality.
We show that the correlation in question is significant and long-lasting. Namely, even when we delve deeper into the local search, we are still in the shadow of the initial assignment. Thus, under practical time constraints, the quality of the initial assignment is crucial to the performance of local search heuristics.
To demonstrate our point, we improve CCLS by combining it with MOCE. Instead of starting CCLS from random initial assignments, we start it from excellent initial assignments, provided by MOCE. Indeed, it turns out that this kind of initialization provides a significant improvement of this state-of-the-art solver. This improvement becomes more and more significant as the instance grows.

BibTeX - Entry

@InProceedings{berend_et_al:LIPIcs:2020:12082,
  author =	{Daniel Berend and Yochai Twitto},
  title =	{{Effect of Initial Assignment on Local Search Performance for Max Sat}},
  booktitle =	{18th International Symposium on Experimental Algorithms (SEA 2020)},
  pages =	{8:1--8:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-148-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{160},
  editor =	{Simone Faro and Domenico Cantone},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12082},
  URN =		{urn:nbn:de:0030-drops-120823},
  doi =		{10.4230/LIPIcs.SEA.2020.8},
  annote =	{Keywords: Combinatorial Optimization, Maximum Satisfiability, Local Search, Probabilistic Algorithms}
}

Keywords: Combinatorial Optimization, Maximum Satisfiability, Local Search, Probabilistic Algorithms
Collection: 18th International Symposium on Experimental Algorithms (SEA 2020)
Issue Date: 2020
Date of publication: 12.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI