This paper presents new methods of encoding the multiplication of a binary encoded integer variable with a constant value for Boolean Satisfiability (SAT) solvers. This problem, known as the Single Constant Multiplica...
详细信息
ISBN:
(数字)9783031605970
ISBN:
(纸本)9783031605963;9783031605970
This paper presents new methods of encoding the multiplication of a binary encoded integer variable with a constant value for Boolean Satisfiability (SAT) solvers. This problem, known as the Single Constant Multiplication (SCM) problem, is widely studied for its application in hardware design, but its techniques are currently not employed for SAT encodings. Considering the smaller and variable bit sizes and the different cost of operations in SAT, we propose further improvements to existing methods by minimizing the number of full/half adders, rather than the number of ripple carry adders. We compare our methods to simple encodings into adders, currently employed by SAT encoders, and direct Boolean encoding using logic minimization tools. We show that our methods result in improved solve-time for problems involving integer linear constraints. A library of optimal recipes for each method to encode SCM for SAT is made available as part of this publication.
Communication over a random-parameter quantum channel when the decoder is required to reconstruct the parameter sequence is considered. We study scenarios that include either strictly-causal, causal, or non-causal cha...
详细信息
Communication over a random-parameter quantum channel when the decoder is required to reconstruct the parameter sequence is considered. We study scenarios that include either strictly-causal, causal, or non-causal channel side information (CSI) available at the encoder, and also when CSI is not available. This model can be viewed as a form of quantum metrology, and as the quantum counterpart of the classical rate-and-state channel with state estimation at the decoder. Regularized formulas for the capacity-distortion regions are derived. In the special case of measurement channels, single-letter characterizations are derived for the strictly-causal and causal settings. Furthermore, in the more general case of entanglement-breaking channels, a single-letter characterization is derived when CSI is not available. As a consequence, we obtain regularized formulas for the capacity of random-parameter quantum channels with CSI, generalizing previous results by Boche et al., 2016, on classical-quantum channels. Bosonic dirty paper coding is introduced as a consequence, where we demonstrate that the optimal coefficient is not necessarily that of minimum mean-square error estimation as in the classical setting.
encoding feasible solutions is one of the most important aspects to be taken into account in the field of evolutionary computation in order to solve search or optimization problems. This paper proposes a new encoding ...
详细信息
encoding feasible solutions is one of the most important aspects to be taken into account in the field of evolutionary computation in order to solve search or optimization problems. This paper proposes a new encoding scheme for real-coded evolutionary algorithms. It is called partition based encoding scheme, and satisfies two restrictions. Firstly, each of the components of a decoded vector that conforms a candidate solution to a problem at hand belongs to a predefined interval. Secondly, the sum of the components of each of these decoded vectors is always equal to a predefined constant. The proposed encoding scheme inherently guarantees these constraints for all the individuals that are generated within the evolution process as a consequence of applying the genetic operators. Partition based encoding scheme is successfully applied to learning conditional probability tables for a given discrete Bayesian network topology, where each row of the tables must exactly add up to one, and the components of each row belong to the interval [0,1] as they are probability values. The results given by the proposed encoding system for this learning problem is compared to a deterministic algorithm and another evolutionary approach. Better results are shown in terms of accuracy with respect to the former one, and accuracy and convergence speed with respect to the later one.
暂无评论