Logical and Inequality Implications for Reducing the Size and Complexity of Quadratic Unconstrained Binary Optimization Problems
The quadratic unconstrained binary optimization (QUBO) problem arises in diverse optimization applications ranging from Ising spin problems to classical problems in graph theory and binary discrete optimization. The use of preprocessing to transform the graph representing the QUBO problem into a smaller equivalent graph is important for improving solution quality and time for both exact and metaheuristic algorithms and is a step towards mapping large scale QUBO to hardware graphs used in quantum annealing computers. In an earlier paper (Lewis and Glover, 2016) a set of rules was introduced that achieved significant QUBO reductions as verified through computational testing. Here this work is extended with additional rules that provide further reductions that succeed in exactly solving 10% of the benchmark QUBO problems. An algorithm and associated data structures to efficiently implement the entire set of rules is detailed and computational experiments are reported that demonstrate their efficacy.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Unveiling Biases in AI: ChatGPT's Political Economy Perspectives and Human Comparisons
We explore the political and ideological positioning of ChatGPT, a leading large language model (LLM), by comparing its responses to political economy questions from the European Social Survey (ESS). The questions concer…
Language ModelingLanguage ModellingLarge Language ModelInformation-Theoretic Guarantees for Recovering Low-Rank Tensors from Symmetric Rank-One Measurements
In this paper, we investigate the sample complexity of recovering tensors with low symmetric rank from symmetric rank-one measurements. This setting is particularly motivated by the study of higher-order interactions and…
What is the Contribution of Intra-household Inequality to Overall Income Inequality? Evidence from Global Data, 1973-2013
Intra-household inequality continues to remain a neglected corner despite renewed focus on income and wealth inequality. Using the LIS micro data, we present evidence that this neglect is equivalent to ignoring up to a t…
A Fundamental Inequality Governing the Rate Coding Response of Sensory Neurons
A fundamental inequality governing the spike activity of peripheral neurons is derived and tested against auditory data. This inequality states that the steady-state firing rate must lie between the arithmetic and geomet…
Syntactic Simplification of OWL Class Expressions
Class expression learning often produces complex OWL class expressions that are difficult to interpret and reason over. However, by following theoretically grounded simplification principles, this complexity can be reduc…