检索结果-内蒙古大学图书馆

From Linear Separability to Unimodality: A Hierarchy of pseudo-boolean functions

SIAM Journal on Discrete Mathematics 1988年第2期1卷 174-184页

作者： P. L. Hammer B. Simeone Th. M. Liebling D. de Werra

When an injective pseudo-boolean function $f:B^n \to \mathbb{R}$ is minimized, where $B^n = \{ 0,1 \}^n$ is the set of vertices of the unit-hypercube, it is natural to consider so-called greedy vertex-following algorithms. These algorithms construct a sequence of neighbouring (Hamming distance 1) vertices with decreasing f-value. The question arises as to when such algorithms will find the global optimum given any starting point. This paper describes a hierarchy of such classes of functions that are shown to strictly contain each other. These classes are, in increasing order of generality, the threshold, the saddle-free, the pseudomodular, the completely unimodal, the unimodal, and the unimin (respectively, unimax) functions. Some considerations as to the complexity of the above-mentioned class of algorithms are also made.

关键词： 05C pseudo-boolean functions combinatorial optimization local improvement algorithms separability convexity unimodality

来源：评论

学校读者我要写书评

暂无评论

Asymptotic Behavior of Linear Approximations of pseudo-boolean functions

引用

JOURNAL OF ADVANCED COMPUTATIONAL INTELLIGENCE AND INTELLIGENT INFORMATICS 2007年第4期11卷 403-409页

作者： Ding, Guoli Lax, Robert F. Chen, Peter Chen, Jianhua Louisiana State Univ Dept Math Baton Rouge LA 70803 USA Louisiana State Univ Dept Comp Sci Baton Rouge LA 70803 USA

We study the problem of approximating pseudo-boolean functions by linear pseudo-boolean functions. pseudo-boolean functions generalize ordinary boolean functions by allowing the function values to be real numbers instead of just the 0-1 values. pseudo-boolean functions have been used by AI and theorem proving researchers for efficient constraint satisfaction solving. They can also be applied for modeling uncertainty. We investigate the possibility of efficiently computing a linear approximation of a pseudo-boolean function of arbitrary degree. We show some example cases in which a simple (efficiently computable) linear approximating function works just as well as the best linear approximating function, which may require an exponential amount of computation to obtain. We conjecture that for any pseudo-boolean function of fixed degree k > 1 where k is independent of the number of boolean variables, the best linear approximating function works better than simply using the linear part of the target function. We also study the behavior of the expected best linear approximating function when the target pseudo-boolean function to be approximated is random.

关键词： approximation uncertainty pseudo-boolean functions

来源：评论

学校读者我要写书评

暂无评论

Learning and Searching pseudo-boolean Surrogate functions from Small Samples

引用

EVOLUTIONARY COMPUTATION 2020年第2期28卷 317-338页

作者： Swingler, Kevin Univ Stirling Comp Sci & Math Stirling FK9 4LA Scotland

When searching for input configurations that optimise the output of a system, it can be useful to build a statistical model of the system being optimised. This is done in approaches such as surrogate model-based optimisation, estimation of distribution algorithms, and linkage learning algorithms. This article presents a method for modelling pseudo-boolean fitness functions using Walsh bases and an algorithm designed to discover the non-zero coefficients while attempting to minimise the number of fitness function evaluations required. The resulting models reveal linkage structure that can be used to guide a search of the model efficiently. It presents experimental results solving benchmark problems in fewer fitness function evaluations than those reported in the literature for other search methods such as EDAs and linkage learners.

关键词： Fitness function modelling estimation of distribution algorithms pseudo-boolean functions linkage learning Walsh decomposition mixed order hyper networks statistical machine learning

来源：评论

学校读者我要写书评

暂无评论

Generalizations of Swierczkowski's lemma and the arity gap of finite functions

引用

DISCRETE MATHEMATICS 2009年第20期309卷 5905-5912页

作者： Couceiro, Miguel Lehtonen, Erkko Univ Luxembourg Dept Math L-1511 Luxembourg Luxembourg Univ Waterloo Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada Tampere Univ Technol Dept Math FI-33101 Tampere Finland

Swierczkowski's lemma - as it is usually formulated - asserts that if f . A(n) -> A is an operation on a finite set A, n >= 4, and every operation obtained from f by identifying a pair of variables is a projection. then f is a semiprojection We generalize this lemma in various ways. First. it is extended to B-valued functions on A instead of operations oil A and to essentially at most unary functions instead of projections. Then we characterize the arity gap of functions of small arities in terms of quasi-arity, which in turn provides a further generalization of Swierczkowski's lemma. Moreover, we explicitly classify all pseudo-boolean functions according to their arity gap. Finally, we present a general characterization of the arity gaps of B-valued functions oil arbitrary finite sets A (C) 2009 Elsevier E.V. All rights reserved.

关键词： Finite functions boolean functions pseudo-boolean functions Variable substitution Variable identification minors Essential variables Arity gap Semiprojection

来源：评论

学校读者我要写书评

暂无评论

Quadratization of Gray Coded Representations, Long Path Problems and Needle functions

Quadratization of Gray Coded Representations, Long Path Prob...

引用

2nd Genetic and Evolutionary Computation Conference (GECCO)

作者： Whitley, Darrell Chicano, Francisco Aguirre, Hernan Colorado State Univ Ft Collins CO 80523 USA Univ Malaga Malaga Spain Shinshu Univ Nagano Japan

ISBN: (纸本)9781450383509

In Evolutionary Computation, it is informative to ask what happens when well known benchmarks and bit representations are transformed into quadratic pseudo-boolean optimization problems. Such transforms are commonly used in quantum computing in order to reduce nonlinearity to k-bounded interactions. First we show that Gray code representations are transformed into linear encodings with quadratic constraints. Next we look at Long Path problems which are constructed so that bit flip local search requires exponential time to converge to a global or local optimum. We show that Long Path problems are similar to reflected Gray codes in both construction and complexity. Finally, a basic form of the "Needle in a haystack" problem is transformed into a problem that can be optimally solved in linear time.

关键词： Quadratization pseudo-boolean functions Representations Gray Codes

来源：评论

学校读者我要写书评

暂无评论

Complexity of local search for the p-median problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2008年第3期191卷 736-752页

作者： Alekseeva, Ekaterina Kochetov, Yuri Plyasunov, Alexander Sobolev Inst Math Novosibirsk Russia

We study the complexity of finding local minima for the p-median problem. The relationship between Swap local optima, 0-1 local saddle points, and classical Karush-Kuhn-Tucker conditions is presented. It is shown that the local search problems with some neighborhoods are tight PLS-complete. Moreover, the standard local descent algorithm takes exponential number of iterations in the worst case regardless of the tie-breaking and pivoting rules used. To illustrate this property, we present a family of instances where some local minima may be hard to find. Computational results with different pivoting rules for random and Euclidean test instances are discussed. These empirical results show that the standard local descent algorithm is polynomial in average for some pivoting rules. (C) 2007 Elsevier B.V. All rights reserved.

关键词： local search PLS-completeness pivoting rules Karush-Kuhn-Tucker conditions 0-1 local saddle points pseudo-boolean functions

来源：评论

学校读者我要写书评

暂无评论

Minimization of ordered, symmetric half-products

引用

DISCRETE APPLIED MATHEMATICS 2005年第3期146卷 287-300页

作者： Kubiak, W Mem Univ Newfoundland Fac Business Adm St Johns NF A1B 3X5 Canada

We introduce a class of pseudo-boolean functions called ordered, symmetric half-products. The class includes a number of well known scheduling problems. We study sets of dominating solutions for minimization of the half-products, and we show their fully polynomial time approximation schemes that use a natural rounding scheme to obtain epsilon-solutions in O(n(2)/epsilon) time. (C) 2004 Elsevier B.V. All rights reserved.

关键词： pseudo-boolean functions scheduling fully polynomial time approximation schemes half-products optimization

来源：评论

学校读者我要写书评

暂无评论

Exact and heuristic approaches to input vector control for leakage power reduction

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 2006年第11期25卷 2564-2571页

作者： Gao, Feng Hayes, John P. Adv Micro Devices Inc Boxboro MA 01719 USA Univ Michigan Adv Comp Architecture Lab Ann Arbor MI 48109 USA

Leakage power consumption is an increasingly serious problem in very large-scale integration circuits, especially for portable applications. Two novel approaches to leakage power minimization in static complementary metal-oxide-semiconductor circuits that employ input vector control (IVC) are investigated. The authors model leakage effects by means of pseudo-boolean functions. These functions are linearized and incorporated into an exact (optimal) integer linear programming (ILP) model, called virtual-gate ILP, which analyzes leakage variation with respect to a circuit's input vectors. A heuristic mixed-integer linear programming (MLP) method is also proposed, which has several advantages: it is faster, its accuracy can be quickly estimated, and tradeoffs between runtime and optimality can easily be made. Furthermore, the MLP model also provides a way to estimate a lower bound on circuit leakage current. The proposed methods are used to generate an extensive set of experimental results on leakage reduction. It is shown that average leakage currents are usually 1.25 times the minimum, confirming the effectiveness of IVC. The heuristic MLP approach is shown to be approximately 13.6 times faster than the exact ILP method, whereas finding input vectors whose power consumption is only a few percent above the optimum. In addition, the lower bound estimated by the MLP model is also within a few percent of the optimal value.

关键词： input vector control integer linear programming leakage current minimization pseudo-boolean functions

来源：评论

学校读者我要写书评

暂无评论

Optimal testing and repairing a failed series system

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2006年第3期12卷 279-295页

作者： Kovalyov, Mikhail Y. Portmann, Marie-Claude Oulamara, Ammar Ecole Mines Nancy MACSI Project LORIA INRIA F-540042 Nancy France Natl Acad Sci Belarus United Inst Informat Problems Minsk 220050 BELARUS Belarusian State Univ Fac Econ F-540042 Nancy France

We consider a series repairable system that includes n components and assume that it has just failed because exactly one of its components has failed. The failed component is unknown. Probability of each component to be responsible for the failure is given. Each component can be tested and repaired at given costs. Both testing and repairing operations are assumed to be perfect, that is, the result of testing a component is a true information that this component is failed or active (not failed), and the result of repairing is that the component becomes active. The problem is to find a sequence of testing and repairing operations over the components such that the system is always repaired and the total expected cost of testing and repairing the components is minimized. We show that this problem is equivalent to minimizing a quadratic pseudo-boolean function. Polynomially solvable special cases of the latter problem are identified and a fully polynomial time approximation scheme (FPTAS) is derived for the general case. Computer experiments are provided to demonstrate high efficiency of the proposed FPTAS. In particular, it is able to find a solution with relative error epsilon = 0.1 for problems with more than 4000 components within 5 minutes on a standard PC with 1.2 Mhz processor.

关键词： test and repair policies failure diagnosis optimization pseudo-boolean functions fully polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

EFFICIENT REDUCTION OF POLYNOMIAL ZERO-ONE OPTIMIZATION TO THE QUADRATIC CASE

引用

SIAM JOURNAL ON OPTIMIZATION 2008年第4期18卷 1398-1413页

作者： Buchheim, Christoph Rinaldi, Giovanni Univ Cologne Inst Informat D-50969 Cologne Germany CNR Ist Anal Sistemi Informat Antonio Ruberti I-00185 Rome Italy

We address the problem of optimizing a polynomial with real coefficients over binary variables. We show that a complete polyhedral description of the linearization of such a problem can be derived in a simple way from the polyhedral description of the linearization of some quadratic optimization problem. The number of variables in the latter linearization is only slightly larger than in the former. If polynomial constraints are present in the original problem, then their linearized counterparts carry over to the linearized quadratic problem unchanged. If the original problem formulation does not contain any constraints, we obtain a reduction to unconstrained quadratic zero-one optimization, which is equivalent to the well-studied max-cut problem. The separation problem for general unconstrained polynomial zero-one optimization thus reduces to the separation problem for the cut polytope. This allows us to transfer the entire knowledge gained for the latter polytope by intensive research and, in particular, the sophisticated separation techniques that have been developed. We report preliminary experimental results obtained with a straightforward implementation of this approach.

关键词： polynomial zero-one optimization integer nonlinear programming pseudo-boolean functions max-cut problem multilinear function optimization

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：