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

Inferring phylogenetic trees using pseudo-boolean optimization

AI COMMUNICATIONS 2014年第3期27卷 229-243页

作者： Miranda, Miguel Lynce, Ines Manquinho, Vasco Univ Lisbon IST INESC ID P-1699 Lisbon Portugal

Phylogenetic inference concerns the construction of the most probable tree of evolution, taking into account the knowledge about organisms we have at our disposal. There are various inference methods for building a phylogenetic tree, each with its set of assumptions about what can happen in Nature. Assumptions limit the expressiveness of the methods, but are necessary for making them viable to use. More recently, computational methods are being used to validate results obtained from manual methods. Computational methods allow to address problems that require the analysis of larger sets of data in order to construct more complete phylogenies. In this paper we propose the use of pseudo-boolean optimization (PBO), a well known extension of Propositional Satisfiability (SAT), in order to solve the Maximum Compatibility (MC) problem. Assuming that each organism is associated with a set of characteristics, the goal in the MC problem is to find a phylogenetic tree such that the maximum number of characteristics are compatible. Our contribution is a set of new PBO formulations that improve on the performance of the state of the art tool. Comparative results, using real and generated instances, show that the proposed implementations allow the resolution of problem instances with twice the size of the state of the art implementation.

关键词： Phylogenetic inference maximum compatibility pseudo-boolean optimization

来源：评论

学校读者我要写书评

暂无评论

Haplotype inference with pseudo-boolean optimization

引用

ANNALS OF OPERATIONS RESEARCH 2011年第1期184卷 137-162页

作者： Graca, Ana Marques-Silva, Joao Lynce, Ines Oliveira, Arlindo L. Univ Tecn Lisboa IST Lisbon Portugal INESC ID Lisboa Lisbon Portugal Univ Coll Dublin Sch Comp Sci & Informat Complex & Adapt Syst Lab Dublin 2 Ireland

The fast development of sequencing techniques in the recent past has required an urgent development of efficient and accurate haplotype inference tools. Besides being a crucial issue in genetics, haplotype inference is also a challenging computational problem. Among others, pure parsimony is a viable modeling approach to solve the problem of haplotype inference and also an interesting NP-hard problem in itself. Recently, the introduction of SAT-based methods, including pseudo-boolean optimization (PBO) methods, has produced very efficient solvers. This paper provides a detailed description of RPoly, a PBO approach for the haplotype inference by pure parsimony (HIPP) problem. Moreover, an extensive evaluation of existent HIPP solvers, on a comprehensive set of instances, confirms that RPoly is currently the most efficient and robust HIPP approach.

关键词： Haplotype inference Pure parsimony pseudo-boolean optimization

来源：评论

学校读者我要写书评

暂无评论

How Crossover Helps in pseudo-boolean optimization 11

How Crossover Helps in Pseudo-Boolean Optimization

引用

13th Annual Genetic and Evolutionary Computation Conference (GECCO)

作者： Koetzing, Timo Sudholt, Dirk Theile, Madeleine Max Planck Inst Informat D-66123 Saarbrucken Germany Univ Birmingham CERCIA Birmingham B15 2TT W Midlands England Tech Univ Berlin D-10623 Berlin Germany

ISBN: (纸本)9781450305570

Understanding the impact of crossover on performance is a major problem in the theory of genetic algorithms (GAs). We present new insight on working principles of crossover by analyzing the performance of crossover-based GAs on the simple functions OneMax and Jump. First, we assess the potential speedup by crossover when combined with a fitness-invariant bit shuffling operator that simulates a lineage of independent evolution on a function of unitation. Theoretical and empirical results show drastic speedups for both functions. Second, we consider a simple GA without shuffling and investigate the interplay of mutation and crossover on Jump. If the crossover probability is small, subsequent mutations create sufficient diversity, even for very small populations. Contrarily, with high crossover probabilities crossover tends to lose diversity more quickly than mutation can create it. This has a drastic impact on the performance on Jump. We complement our theoretical findings by Monte Carlo simulations on the population diversity.

关键词： Crossover recombination pseudo-boolean optimization runtime analysis

来源：评论

学校读者我要写书评

暂无评论

A pseudo-boolean optimization for multiple criteria decision making in complex systems

A pseudo-boolean optimization for multiple criteria decision...

引用

7th International Conference on Computational Science (ICCS 2007)

作者： Alidaee, Bahram Wang, Haibo Xu, Yaquan Univ Mississippi University MS 38677 USA Texas A& M Inte Univ Laredo 78041 TX USA Virginia State Univ Petersburg VA 23806 USA

ISBN: (纸本)9783540725893

In complex system problems, a Decision Maker (DM) is often faced with choosing a subset of alternatives from a bigger set. This process is known as multiple criteria decision making (MCDM). Examples of MCDM include decision making in human resource management, water resource management, environmental management and site selection, energy policy issues, portfolio selection, transportation and routing selection, student admission. In general, there are several criteria that need to be satisfied;however, they are usually at least partly conflicting. In this study, we propose a pseudo-boolean approach for multiple criteria decision making on complex system problems. The computational results illustrate both robustness and attractiveness of this solution approach.

关键词： pseudo-boolean optimization multiple criteria decision making

来源：评论

学校读者我要写书评

暂无评论

Fast 1-flip neighborhood evaluations for large-scale pseudo-boolean optimization using posiform representation

引用

COMPUTERS & OPERATIONS RESEARCH 2023年第1期159卷

作者： Liang, Ricardo N. Anacleto, Eduardo A. J. Meneses, Claudio N. Fed Univ ABC Ctr Math Computat & Cognit Sao Paulo Brazil

We consider the general case of pseudo-boolean optimization (PBO). This problem belongs to the NP-hard class of computational complexity and generalizes the well-known quadratic unconstrained binary optimization (QUBO) problem, which is able to model a wide range of combinatorial optimization problems and also has applications in quantum computing. Several state-of-the-art methods in the literature for solving specific classes of PBO problems rely on the ability to quickly evaluate changes in objective function value upon a flip move, i.e., after changing the value of a boolean variable in a given solution from 0 to 1 or from 1 to 0. In this work, we propose closed-form formulae, and develop algorithms and auxiliary data structures for quickly evaluating 1-flip move neighborhoods in PBO problems. We work with the objective function represented as a posiform, i.e., a sum of terms that may contain boolean variables or negations thereof. This representation is interesting for solving large-scale instances, since converting a posiform to an expression containing no variable negations may take exponential time and space in the number of variables. We also provide implementations of our algorithms and data structures as a library written in C programming language. This library can be used to implement methods with fast flip move evaluations for solving PBO problem instances. We conducted computational experiments with implementations of a Iterated Tabu Search (ITS) metaheuristic, when solving randomly-generated instances, and also instances of the Hypergraph Maximum Cut problem, which can be easily recast as a PBO problem. The results showed that our best evaluation algorithms provided relatively large speedups as instance sizes increased, and became more competitive as a consequence of speedup.

关键词： pseudo-boolean optimization Fast flip moves Heuristics Data structures Computational efficiency

来源：评论

学校读者我要写书评

暂无评论

On Using Cutting Planes in pseudo-boolean optimization

引用

Journal on Satisfiability, boolean Modelling and Computation 2006年第1-4期2卷 209 - 219页

作者： Vasco M. Manquinho João Marques-Silva IST/INESC-ID Technical University of Lisbon Portugal. E-mail: University of Southampton UK. E-mail:

Cutting planes are a well-known, widely used, and very effective technique for Integer Linear Programming (ILP). However, cutting plane techniques are seldom used in pseudo-boolean optimization (PBO) algorithms. This paper addresses the utilization of Gomory mixed-integer and clique cuts, in Satisfiability-based algorithms for PBO, and shows how these cuts can be used for computing lower bounds and for learning new constraints. A side result of learning new constraints is that the utilization of cutting planes enables non-chronological backtracking. Besides cutting planes, the paper also shows that the utilization of search restarts in PBO can be effective in practice, allowing the computation of tighter lower bounds each time the search restarts. The more aggressive lower bounds result from the constraints learned due to the utilization of cutting planes. Experimental results show that the integration of cutting planes and search restarts in a SAT-based algorithm for PBO yields a competitive new solution for PBO.

关键词： pseudo-boolean optimization cutting planes search restarts

来源：评论

学校读者我要写书评

暂无评论

The pseudo-boolean polytope and polynomial-size extended formulations for binary polynomial optimization

引用

MATHEMATICAL PROGRAMMING 2024年 1-45页

作者： Del Pia, Alberto Khajavirad, Aida Univ Wisconsin Inst Discovery Dept Ind & Syst Engn & Wisconsin Madison WI USA Lehigh Univ Dept Ind & Syst Engn Bethlehem PA 18018 USA

With the goal of obtaining strong relaxations for binary polynomial optimization problems, we introduce the pseudo-boolean polytope defined as the set of binary points z is an element of {0, 1}(V boolean OR S) satisfying a collection of equalities of the form z(s) = Pi(v is an element of s) sigma(s)(z(v)), for all s is an element of S, where sigma(s) (z(v)) is an element of {z(v), 1 - z(v)}, and where S is a multiset of subsets of V. By representing the pseudo-boolean polytope via a signed hypergraph, we obtain sufficient conditions under which this polytope has a polynomial-size extended formulation. Our new framework unifies and extends all prior results on the existence of polynomial-size extended formulations for the convex hull of the feasible region of binary polynomial optimization problems of degree at least three.

关键词： Binary polynomial optimization pseudo-boolean optimization pseudo-boolean polytope Signed hypergraph Polynomial-size extended formulation

来源：评论

学校读者我要写书评

暂无评论

Simple Max-Min Ant Systems and the optimization of Linear pseudo-boolean Functions 11

Simple Max-Min Ant Systems and the Optimization of Linear Ps...

引用

11th Foundations of Genetic Algorithms Workshop

作者： Koetzing, Timo Neumann, Frank Sudholt, Dirk Wagner, Markus Max Planck Inst Informat D-66123 Saarbrucken Germany

ISBN: (纸本)9781450306331

With this paper, we contribute to the understanding of ant colony optimization (ACO) algorithms by formally analyzing their runtime behavior. We study simple MAX-MIN ant systems on the class of linear pseudo-boolean functions defined on binary strings of length n. Our investigations point out how the progress according to function values is stored in the pheromones. We provide a general upper bound of O((n(3) log n)/rho) on the running time for two ACO variants on all linear functions, where p determines the pheromone update strength. Furthermore, we show improved bounds for two well-known linear pseudo-boolean functions called ONEMAx and BINVAL and give additional insights using an experimental study.

关键词： Ant colony optimization MMAS runtime analysis pseudo-boolean optimization theory

来源：评论

学校读者我要写书评

暂无评论

Combinatorial optimization Solutions for the Maximum Quartet Consistency Problem

引用

FUNDAMENTA INFORMATICAE 2010年第3-4期102卷 363-389页

作者： Morgado, Antonio Marques-Silva, Joao Univ Coll Dublin Complex & Adapt Syst Lab Sch Comp Sci & Informat Dublin Ireland

Phylogenetic analysis is a widely used technique, for example in biology and biomedical sciences. The construction of phylogenies can be computationally hard. A commonly used solution for construction of phylogenies is to start from a set of biological species and relations among those species. This work addresses the case where the relations among species are specified as quartet topologies. Moreover, the problem to be solved consists of computing a phylogeny that satisfies the maximum number of quartet topologies. This is referred to as the Maximum Quartet Consistency (MQC) problem, and represents an NP-hard optimization problem. MQC has been solved both heuristically and exactly. Exact solutions forMQC include those based on Constraint Programming, Answer Set Programming, pseudo-booleanoptimization (PBO), and Satisfiability Modulo Theories (SMT). This paper provides a comprehensive overview of the use of PBO and SMT for solving MQC, and builds on recent work in this area. Moreover, the paper provides new insights on how to use SMT for solving optimization problems, by focusing on the concrete case of MQC. The solutions based on PBO and SMT were experimentally compared with other exact solutions. The results show that for instances with small percentage of quartet errors, the models based on SMT can be competitive, whereas for instances with higher number of quartet errors the PBO models are more efficient.

关键词： maximum quartet consistency optimization algorithms pseudo-boolean optimization satisfiability modulo theories

来源：评论

学校读者我要写书评

暂无评论

A class of valid inequalities for multilinear 0-1 optimization problems

引用

DISCRETE optimization 2017年 25卷 28-47页

作者： Crama, Yves Rodriguez-Heck, Elisabeth Univ Liege HEC Management Sch QuantOM Liege Belgium

This paper investigates the polytope associated with the classical standard linearization technique for the unconstrained optimization of multilinear polynomials in 0-1 variables. A new class of valid inequalities, called 2-links, is introduced to strengthen the LP relaxation of the standard linearization. The addition of the 2-links to the standard linearization inequalities provides a complete description of the convex hull of integer solutions for the case of functions consisting of at most two nonlinear monomials. For the general case, various computational experiments show that the 2-links improve both the standard linearization bound and the computational performance of exact branch & cut methods. The improvements are especially significant for a class of instances inspired from the image restoration problem in computer vision. The magnitude of this effect is rather surprising in that the 2-links are in relatively small number (quadratic in the number of terms of the objective function). (C) 2017 Elsevier B.V. All rights reserved.

关键词： Multilinear binary optimization pseudo-boolean optimization Integer nonlinear programming Standard linearization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：