About: Comparing Integer Linear Programming to SAT-Solving for Hard Problems in Computational and Systems Biology

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Comparing Integer Linear Programming to SAT-Solving for Hard Problems in Computational and Systems Biology Goto Sponge NotDistinct Permalink

An Entity of Type : schema:ScholarlyArticle, within Data Space : covidontheweb.inria.fr associated with source document(s)

Attributes	Values
type	Academic Article research paper schema:ScholarlyArticle
isDefinedBy	Covid-on-the-Web dataset
title	Comparing Integer Linear Programming to SAT-Solving for Hard Problems in Computational and Systems Biology
Creator	Brown, Hannah Zuo, Lei Gusfield, Dan
source	PMC
abstract	It is useful to have general-purpose solution methods that can be applied to a wide range of problems, rather than relying on the development of clever, intricate algorithms for each specific problem. Integer Linear Programming is the most widely-used such general-purpose solution method. It is successful in a wide range of problems. However, there are some problems in computational biology where integer linear programming has had only limited success. In this paper, we explore an alternate, general-purpose solution method: SAT-solving, i.e., constructing Boolean formulas in conjunctive normal form (CNF) that encode a problem instance, and using a SAT-solver to determine if the CNF formula is satisfiable or not. In three hard problems examined, we were very surprised to find the SAT-solving approach was dramatically better than the ILP approach in two problems; and a little slower, but more robust, in the third problem. We also re-examined and confirmed an earlier result on a fourth problem, using current ILP and SAT-solvers. These results should encourage further efforts to exploit SAT-solving in computational biology.
has issue date	2020-02-01(xsd:dateTime)
bibo:doi	10.1007/978-3-030-42266-0_6
has license	no-cc
sha1sum (hex)	26d0d89f55a03ae3837fe225fd2ed10f676e5805
schema:url	https://doi.org/10.1007/978-3-030-42266-0_6
resource representing a document's title	Comparing Integer Linear Programming to SAT-Solving for Hard Problems in Computational and Systems Biology
has PubMed Central identifier	PMC7197060
schema:publication	Algorithms for Computational Biology
resource representing a document's body	covid:26d0d89f55a03ae3837fe225fd2ed10f676e5805#body_text
is schema:about of	named entity 'solution' named entity 'CNF' named entity 'integer linear programming' named entity 'current' named entity 'limited' »more»

Faceted Search & Find service v1.13.91 as of Mar 24 2020

Alternative Linked Data Documents: Sponger | ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3229 as of Jul 10 2020, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (94 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software