A Pseudo-Boolean (PB) constraint is a linear in-equality constraint over Boolean literals. One of the popular, efficient ideas used to solve PB-problems (a set of PB-constraints) is to translate them to SAT instances (encodings) via, for example, sorting networks, then to process those instances using state-of-the-art SAT-solvers. In this paper we show an improvement of such technique. By using a variation of a greedy set cover algorithm, when adding constraints to our encoding, we reuse parts of the already encoded PB-instance in order to decrease the size (the number of variables and clauses) of the resulting SAT instance. The experimental evaluation shows that the proposed method increases the number of solved instances.

UWrMaxSat is a quite new solver for MaxSAT and pseudo-Boolean problems. It has been created at the University of Wroclaw and can be characterized as a complete solver for partial weighted MaxSAT instances, and, independently, for linear pseudo-Boolean optimizing and decision ones. The solver incrementally uses COMiniSatPS by Chanseok Oh (2016) as an underlying SAT solver, but may be compiled with other MiniSat-like solvers as well. It was developed on the top of our PB solver (called KP-MiniSat+) that was presented at Pragmatics of SAT 2018 and which is an extension of the well-known MiniSat+ solver. In its main configuration, UWrMaxSat applies a core-guided OLL procedure and uses the KP-MiniSat+ sorter-based pseudo-Boolean constraint encoding to translate cardinality constraints into CNF. The solver participated in MaxSAT Evaluation 2019, where it ranked second places in both main tracks (weighted and unweighted). The novel techniques applied in the solver are as follows: (1) a new encoding of cardinality and pseudo-Boolean constraints by 4-Way Merge Selection Networks, (2) a fast search algorithm for mixed-radix bases needed in the encoding, and (3) a combination of selected other optimization heuristics for weighted instances. Moreover, MaxPre preprocessor has been recently integrated with the solver.

We consider the problem of merging two sorted sequences on a comparator network that is used repeatedly, that is, if the output is not sorted, the network is applied again using the output as input. The challenging task is to construct such networks of small depth (called a period in this context). The first constructions of merging networks with a constant period were described by Kuty{l}owski et al. They gave 3-periodic network that merges two sorted sequences of N numbers in time 12log N and a similar network of period 4 that works in 5.67log N. We present a new family of 3-periodic merging networks with merging time upper-bounded by 6log N. The construction can be easily generalized to larger constant periods with decreasing running time, for example, to 4-periodic ones that work in time upper-bounded by 4log N.

We study the problem of constructing a sorting network that is tolerant to faults and whose running time (i.e., depth) is as small as possible. We consider the scenario of worst-case comparator faults and follow the model of passive comparator failure proposed by Yao and Yao SIAM J. Comput., 14 (1985), pp. 120--128], in which a faulty comparator outputs its inputs directly without comparison. Our main result is the first construction of an N-input k-fault-tolerant sorting network with an asymptotically optimal depth $\theta$(log N + k). That improves over the result of Leighton and Ma [Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, Velen, Germany, 1993, ACM, New York, pp. 30--41], whose network is of depth O(log N + klog\frac{log N}{log k})$. Actually, we present a fault-tolerant correction network that can be added after any N-input sorting network to correct its output in the presence of at most k faulty comparators. Since the depth of the network is O(log N + k) and the constants hidden behind the "O" notation are small, the construction can be of practical use. Developing the techniques necessary to show the main result, we construct a fault-tolerant network for the insertion problem. As a by-product, we get an N-input O(log N)-depth INSERT-network that is tolerant to random faults, thereby answering a question posed by Ma in his Ph.D. thesis [Fault-Tolerant Sorting Network, Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA, 1994]. The results are based on a new notion of constant delay comparator networks, that is, networks in which each register is used (compared) only in a period of time of a constant length. Copies of such networks can be pipelined with only a constant increase in the total depth per copy.

We study the problem of sorting sequences of N-keys that can be obtained from sorted ones by changing values of s, 0 < s ⪇ N, keys at unknown positions. Such s-disturbed sequences can appear as outputs of a sorting network that contains faulty comparators. We present a simple comparator network of depth 4 that sorts 1-disturbed sequences in logarithmic time, where the network is used repeatedly, i.e. if its output is not sorted, the network is run again taking the output as input. Then we analyze the passive-fault model of comparator networks introduced by Yao and Yao, where a faulty comparator outputs directly its input without making a comparison. In this context, we give a construction of N-input, f-fault-tolerant comparator networks of depth 6 that sort 1-disturbed sequences in time Ο(logN + f). Finally, we prove that choosing f = Ο(logN) one can make such networks random-fault-tolerant. In the last two results the constructions and their analysis are simpler as the previous non-periodic ones, and still their runtimes are asymptotically optimal.

We consider the problem of constructing reliable comparator networks built from unreliable comparators. In case of a faulty comparator inputs are directly output without comparison. A trivial lower bound of Ω(logn + k) on the depth of n-input k-fault tolerant sorting network is well known. We are interested in establishing exact lower bounds on the depth of such networks. To this end we consider fairly simple minimum-finding networks. Our main result is the first nontrivial lower bound on depths of networks computing minimum among n > 2 items in the presence of k > 0 faulty comparators. We prove that the depth of any such network is at least max([logn] + 2k, logn + klog logn/k+1). We also describe a network whose depth nearly matches the lower bound.

We consider the problem of sorting sequences obtained from a sorted sequence of n keys by changing the values of at most k keys at some unknown positions. Since even for k=1 a lower bound /spl Omega/(log n) on the number of parallel comparison steps applies, any comparator network solving this problem cannot be asymptotically faster than the AKS sorting network. We design a comparator network which sorts the sequences considered for a large range of k's, has a simple architecture and achieves a runtime c/spl middot/log n, for a small constant c. We present such networks of depth 4 log n+O(log/sup 2/ k log log n) with a small constant hidden behind the big "Oh". In particular, for k=o(2/spl radic/(log n/log log n)) the networks are of depth 4 log n+o(log n).