In pursuit of industrial like MAXSAT with reduced MAX-3SAT random generation

Abstract

In the modern landscape of MAXSAT, there are two broad classifications of problems: Random MAX-3SAT and Industrial SAT. Random MAX-3SAT problems by randomly sampling variables with a uniform probability and randomly assigning signs to the variable, one clause at a time. Industrial MAX-SAT consists of MAX-3SAT problems as encountered in the real world, and generally have a lower nonlinearity than random MAX-3SAT instances. One of the goals of recent research has been to figure out which rules and structures these industrial problems follow and how to replicate them randomly. This paper builds off of the paper" Reduction-Based MAX-3SAT with Low Nonlinearity and Lattices Under Recombination", implementing its approach to MAX-3SAT clause generation and determining what it can reveal about industrial MAX-13SAT and random MAX-3SAT. This builds off of the transformation from SAT to MAX-SAT problems and hopes to create random MAXSAT problems that are more representative of industrial MAXSAT problems. All this would be in the pursuit of random MAX-3SAT that more accurately maps onto real-world MAX-3SAT instances so that more efficient MAX-3SAT solvers can be produced.