Weakening Cardinality Constraints Creates Harder Satisfiability Benchmarks

For some time, the satisfiability formulae that have been the most difficult to solve for their size have been crafted to be unsatisfiable by the use of cardinality constraints. Recent solvers have introduced explicit checking of such constraints, rendering previously difficult formulae trivial to solve. A family of unsatisfiable formulae is described that is derived from the sgen4 family but cannot be solved using cardinality constraints detection and reasoning alone. These formulae were found to be the most difficult during the SAT2014 competition by a significant margin and include the shortest unsolved benchmark in the competition, sgen6-1200-5-1.cnf.

On the cardinality and complexity of the set of codings for self-similar sets with positive Lebesgue measure

Let λ1,…,λn be real numbers in (0,1) and p1,…,pn be points in Rd. Consider the collection of maps fj:Rd→Rd given by fj(x)=λjx+(1−λj)pj. It is a well known result that there exists a unique nonempty compact set Λ⊂Rd satisfying Λ=∪nj=1fj(Λ). Each x∈Λ has at least one coding, that is a sequence (ϵi)∞i=1 ∈{1,…,n}N that satisfies limN→∞fϵ1…fϵN(0)=x. We study the size and complexity of the set of codings of a generic x∈Λ when Λ has positive Lebesgue measure. In particular, we show that under certain natural conditions almost every x∈Λ has a continuum of codings. We also show that almost every x∈Λ has a universal coding. Our work makes no assumptions on the existence of holes in Λ and improves upon existing results when it is assumed Λ contains no holes.

A group topology on the free abelian group of cardinality c that makes its square countably compact

Under p = c, we prove that it is possible to endow the free abelian group of cardinality c with a group topology that makes its square countably compact. This answers a question posed by Madariaga-Garcia and Tomita and by Tkachenko. We also prove that there exists a Wallace semigroup (i.e., a countably compact both-sided cancellative topological semigroup which is not a topological group) whose square is countably compact. This answers a question posed by Grant.

Finding the optimal cardinality value for information bottleneck method

Information Bottleneck method can be used as a dimensionality reduction approach by grouping “similar” features together [1]. In application, a natural question is how many “features groups” will be appropriate. The dependency on prior knowledge restricts the applications of many Information Bottleneck algorithms. In this paper we alleviate this dependency by formulating the parameter determination as a model selection problem, and solve it using the minimum message length principle. An efficient encoding scheme is designed to describe the information bottleneck solutions and the original data, then the minimum message length principle is incorporated to automatically determine the optimal cardinality value. Empirical results in the documentation clustering scenario indicates that the proposed method works well for the determination of the optimal parameter value for information bottleneck method.

Polyhedral combinatorics of the cardinality constrained quadratic knapsack problem and the quadratic selective travelling salesman problem

This paper considers the Cardinality Constrained Quadratic Knapsack Problem (QKP) and the Quadratic Selective Travelling Salesman Problem (QSTSP). The QKP is a generalization of the Knapsack Problem and the QSTSP is a generalization of the Travelling Salesman Problem. Thus, both problems are NP hard. The QSTSP and the QKP can be solved using branch-and-cut methods. Good bounds can be obtained if strong constraints are used. Hence it is important to identify strong or even facet-defining constraints. This paper studies the polyhedral combinatorics of the QSTSP and the QKP, i.e. amongst others we identify facet-defining constraints for the QSTSP and the QKP, and provide mathematical proofs that they do indeed define facets.

On the minimum cardinality problem in intensity modulated radiotherapy

The thesis examines an optimisation problem that appears in the treatment planning of intensity modulated radiotherapy. An approach is presented which solved the optimisation problem in question while also extending the approach to execute in a massively parallel environment. The performance of the approach presented is among the fastest available.

Computable Diagonalizations and Turing’s Cardinality Paradox

A. N. Turing’s 1936 concept of computability, computing machines, and computable binary digital sequences, is subject to Turing’s Cardinality Paradox. The paradox conjoins two opposed but comparably powerful lines of argument, supporting the propositions that the cardinality of dedicated Turing machines outputting all and only the computable binary digital sequences can only be denumerable, and yet must also be nondenumerable. Turing’s objections to a similar kind of diagonalization are answered, and the implications of the paradox for the concept of a Turing machine, computability, computable sequences, and Turing’s effort to prove the unsolvability of the Entscheidungsproblem, are explained in light of the paradox. A solution to Turing’s Cardinality Paradox is proposed, positing a higher geometrical dimensionality of machine symbol-editing information processing and storage media than is available to canonical Turing machine tapes. The suggestion is to add volume to Turing’s discrete two-dimensional machine tape squares, considering them instead as similarly ideally connected massive three-dimensional machine information cells. Three-dimensional computing machine symbol-editing information processing cells, as opposed to Turing’s two-dimensional machine tape squares, can take advantage of a denumerably infinite potential for parallel digital sequence computing, by which to accommodate denumerably infinitely many computable diagonalizations. A three-dimensional model of machine information storage and processing cells is recommended on independent grounds as better representing the biological realities of digital information processing isomorphisms in the three-dimensional neural networks of living computers.

On the Set of Locally Convex Topologies Compatible with a Given Topology on a Vector Space: Cardinality Aspects

For a topological vector space (X, τ ), we consider the family LCT (X, τ ) of all locally convex topologies defined on X, which give rise to the same continuous linear functionals as the original topology τ . We prove that for an infinite-dimensional reflexive Banach space (X, τ ), the cardinality of LCT (X, τ ) is at least c.

On the kidney exchange problem: cardinality constrained cycle and chain problems on directed graphs: a survey of integer programming approaches

The Kidney Exchange Problem (KEP) is a combinatorial optimization problem and has attracted the attention from the community of integer programming/combinatorial optimisation in the past few years. Defined on a directed graph, the KEP has two variations: one concerns cycles only, and the other, cycles as well as chains on the same graph. We call the former a Cardinality Constrained Multi-cycle Problem (CCMcP) and the latter a Cardinality Constrained Cycles and Chains Problem (CCCCP). The cardinality for cycles is restricted in both CCMcP and CCCCP. As for chains, some studies in the literature considered cardinality restrictions, whereas others did not. The CCMcP can be viewed as an Asymmetric Travelling Salesman Problem that does allow subtours, however these subtours are constrained by cardinality, and that it is not necessary to visit all vertices. In existing literature of the KEP, the cardinality constraint for cycles is usually considered to be small (to the best of our knowledge, no more than six). In a CCCCP, each vertex on the directed graph can be included in at most one cycle or chain, but not both. The CCMcP and the CCCCP are interesting and challenging combinatorial optimization problems in their own rights, particularly due to their similarities to some travelling salesman- and vehicle routing-family of problems. In this paper, our main focus is to review the existing mathematical programming models and solution methods in the literature, analyse the performance of these models, and identify future research directions. Further, we propose a polynomial-sized and an exponential-sized mixed-integer linear programming model, discuss a number of stronger constraints for cardinality-infeasible-cycle elimination for the latter, and present some preliminary numerical results.