Some Generic Algorithmic Ideas

The performance of an algorithm/solver can be impacted by various factors, but the most essential factor is the algorithmic ideas in it. These ideas (can be called methods, strategies, heuristics) are usually on a higher level than concrete algorithms, and may find applications in other algorithms and other problems.

I have proposed some generic algorithmic ideas, which are mainly used in local search algorithms, and some can also be applied to other types of algorithms.

Configuration Checking

• Configuration Checking (CC) strategy is a simple yet effective idea for local search. The basic idea: for a solution component (such as a variable in SAT or a vertex in graph problems), if its configuration (some circumstance information) remains the same as the last time it changed assignment, then it is forbidden to change its assignment back. CC is an interesting alternative of the Tabu method.
• One can get different CC strategies by defining configuration and checking mechanism in different ways.
• CC has been successfully applied to several problems. Especially, it has been widely used in local search algorithms for SAT and MaxSAT, including quite a few awarded solvers in recent SAT Competitions and MaxSAT Evaluations. A typical CC strategy for SAT is to forbid flipping a variable if since the last time it was flipped, none of its neighboring variables has been flipped.
• Paper List on CC

Second Level Score

• In combinatorial optimization, given the object function or evaluation function f, which measures the quality of solutions, we can define the score of an operation as the change of the f value by the operation, where an operation usually refers to changing the assignment of a solution component such as a variable. Most local search algorithms choose the variable to operate according to their scores. As the score indicates how much benefit can this operation bring, variables with bigger score are considered better.
• However, this is not necessarily the case. Consider a variable with a great score, but its operation will decrease other variables' scores significantly; then, another variable which has a slightly smaller score but its operation will increase other variables' score should be a better choice.
• The second level score measures the benefit (or damage) of an operation of a variable on other variables' scores, and can be regarded as a look-ahead information. We have shown that, besides variables' scores, it is useful to also consider second level score when choosing the variable to operate.
• Selected papers on second level score:
  S. Cai, K. Su, Local search for Boolean Satisfiability with configuration checking and subscore, Artificial Intelligence (AIJ) 204, pp.75-98 (2013).
  S. Cai, K. Su, C. Luo, Improving WalkSAT for Random k-Satisfiability Problem with k>3, Proc. of AAAI 2013, pp.145-151.
  

Best from Multiple Selections

• Best from Multiple Selections (BMS) is a probabilistic method for choosing a good-quality element from a large set.
• For a set S, the BMS strategy works as follows: Choose k elements randomly with replacement from the set S, and then return the best one (w.r.t. some comparison function f), where k is a parameter.
• Calculations show that, for a real number p in (0, 1), the probability of the event E = {the quality of the element returned by BMS is not worse than p|S| elements in the set S} is greater than 1-p^k.
• Selected papers on BMS:
  S Cai, Balance between Complexity and Quality: Local Search for Minimum Vertex Cover in Massive Graphs, Proc. of IJCAI 2015, pp.747-753.
  Y. Wang, S. Cai, M. Yin, Two Efficient Local Search Algorithms for Maximum Weight Clique Problem, Proc. of AAAI 2016, pp.805-811