DROPS

Document

DOI: 10.4230/LIPIcs.SEA.2020.8

Effect of Initial Assignment on Local Search Performance for Max Sat

Authors: Daniel Berend and Yochai Twitto

Published in: LIPIcs, Volume 160, 18th International Symposium on Experimental Algorithms (SEA 2020)

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.

Cite as

Daniel Berend and Yochai Twitto. Effect of Initial Assignment on Local Search Performance for Max Sat. In 18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{berend_et_al:LIPIcs.SEA.2020.8,
  author =	{Berend, Daniel and Twitto, Yochai},
  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 =	{Faro, Simone and Cantone, Domenico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2020.8},
  URN =		{urn:nbn:de:0030-drops-120823},
  doi =		{10.4230/LIPIcs.SEA.2020.8},
  annote =	{Keywords: Combinatorial Optimization, Maximum Satisfiability, Local Search, Probabilistic Algorithms}
}

Search Results

Documents authored by Berend, Daniel

Effect of Initial Assignment on Local Search Performance for Max Sat

Abstract

Cite as

Thanks for your feedback!

Could not send message