Discrete Lagrangian-Based Search for Solving MAX-SAT Problems
Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence. Constraint Satisfaction. Pages 378-382.
Abstract
Weighted maximum satisfiability problems (MAX-SAT) are difficult to solve due to the large number of local minima in their search space. In this paper we propose a new discrete Lagrangian based search method (DLM) for solving these problems. Instead of restarting from a new point when the search reaches a local minimum, the Lagrange multipliers in DLM provide a force to lead the search out of the local minimum and move it in a direction provided by the multipliers. Since DLM has very few parameters to be tuned, it can be made deterministic and the results, reproducible. We compare DLM with GRASP in solving a large set of test problems, and show that it finds better so lutions and is substantially faster. DLM has a solid theoretical foundation that can be used as a systematic approach for solving general discrete optimization problems.
@inproceedings{ijcai1997p56,
title = {Discrete Lagrangian-Based Search for Solving MAX-SAT Problems},
author = {Wah, Benjamin W. and Shang, Yi},
booktitle = {Proceedings of the Fifteenth International Joint Conference on
Artificial Intelligence, {IJCAI-97}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Martha E. Pollack},
pages = {378--382},
year = {1997},
note = {Constraint Satisfaction},
url = {https://ijcai.org/proceedings/1997/56},
}
TY - CPAPER TI - Discrete Lagrangian-Based Search for Solving MAX-SAT Problems AU - Wah, Benjamin W. AU - Shang, Yi T2 - Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, IJCAI-97 PB - International Joint Conferences on Artificial Intelligence PY - 1997 SP - 378 EP - 382 UR - https://ijcai.org/proceedings/1997/56 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
