On Dual-Rail Based MaxSAT Solving

Title:On Dual-Rail Based MaxSAT Solving

Authors:Maria Lluïsa Bonet, Sam Buss, Alexey Ignatiev, Joao Marques-Silva and Antonio Morgado

Conference:PC 2018

Tags:dual-rail encoding, MaxSAT resolution, MaxSAT solving, polynomial simulation and polynomial upper bounds

Abstract:

This work overviews recent results on the dual-rail based MaxSAT solving, including polynomial upper bounds on the refutation of PHP and 2PHP formulae with core-guided MaxSAT solvers and MaxSAT resolution as well as their relative efficiency compared to general resolution and cutting planes.

On Dual-Rail Based MaxSAT Solving

1

3

5

7

9

11

13

15

17

19

21

23

25

27

29

31

33

35

37

39

41

43

45

47

49

51

53

55

57

59

61

63

65

67

69

71

73

75

77

79

81

83

84

1of84

1

2

3

4