Toward a Search Strategy for Anytime Search in Linear Space Using Depth-First Branch and Bound Article Swipe

PDF

YOU? · · 2021 · Open Access · · DOI: https://doi.org/10.1609/socs.v5i1.18338

Depth-First Branch and Bound (DFBnB) is an anytime algorithm for solving combinatorial optimization problems. In this paper we present a weighted version of DFBnB, wDFBnB, which incorporates standard techniques for using weights in heuristic search and offers suboptimality guarantees. Our main contribution drawn from a preliminary evaluation is the observation that wDFBnB, used along with automated or hand-crafted weight schedules, can significantly outperform DFBnB both in terms of anytime behavior and convergence to the optimal. We think this small study calls for more research on the design of automated weight schedules that could provide superior anytime performance across a wider range of domains.

Related Topics

Mathematical Analysis

Economic Growth

Economics

Aerospace Engineering

Concepts

Branch and bound Heuristic Range (aeronautics) Convergence (economics) Mathematical optimization Space (punctuation) Computer science Upper and lower bounds Depth-first search Search algorithm Mathematics Algorithm Engineering Operating system Mathematical analysis Economic growth Economics Aerospace engineering

Metadata

Type: article
Language: en
Landing Page: https://doi.org/10.1609/socs.v5i1.18338
PDF: https://ojs.aaai.org/index.php/SOCS/article/download/18338/18129
OA Status: diamond
Cited By: 1
References: 15
Related Works: 10
OpenAlex ID: https://openalex.org/W1570293800

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W1570293800

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.1609/socs.v5i1.18338

Digital Object Identifier
Title: Toward a Search Strategy for Anytime Search in Linear Space Using Depth-First Branch and Bound

Work title
Type: article

OpenAlex work type
Language: en

Primary language
Publication year: 2021

Year of publication
Publication date: 2021-09-01

Full publication date if available
Authors: Carlos Hernández, Jorge A. Baier

List of authors in order
Landing page: https://doi.org/10.1609/socs.v5i1.18338

Publisher landing page
PDF URL: https://ojs.aaai.org/index.php/SOCS/article/download/18338/18129

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: diamond

Open access status per OpenAlex
OA URL: https://ojs.aaai.org/index.php/SOCS/article/download/18338/18129

Direct OA link when available
Concepts: Branch and bound, Heuristic, Range (aeronautics), Convergence (economics), Mathematical optimization, Space (punctuation), Computer science, Upper and lower bounds, Depth-first search, Search algorithm, Mathematics, Algorithm, Engineering, Operating system, Mathematical analysis, Economic growth, Economics, Aerospace engineering

Top concepts (fields/topics) attached by OpenAlex
Cited by: 1

Total citation count in OpenAlex
Citations by year (recent): 2021: 1

Per-year citation counts (last 5 years)
References (count): 15

Number of works referenced by this work
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W1570293800
doi	https://doi.org/10.1609/socs.v5i1.18338
ids.doi	https://doi.org/10.1609/socs.v5i1.18338
ids.mag	1570293800
ids.openalex	https://openalex.org/W1570293800
fwci	0.14110358
type	article
title	Toward a Search Strategy for Anytime Search in Linear Space Using Depth-First Branch and Bound
biblio.issue	1
biblio.volume	5
biblio.last_page	199
biblio.first_page	198
topics[0].id	https://openalex.org/T10906
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9995999932289124
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1702
topics[0].subfield.display_name	Artificial Intelligence
topics[0].display_name	AI-based Problem Solving and Planning
topics[1].id	https://openalex.org/T11596
topics[1].field.id	https://openalex.org/fields/17
topics[1].field.display_name	Computer Science
topics[1].score	0.9976000189781189
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/1705
topics[1].subfield.display_name	Computer Networks and Communications
topics[1].display_name	Constraint Satisfaction and Optimization
topics[2].id	https://openalex.org/T10586
topics[2].field.id	https://openalex.org/fields/17
topics[2].field.display_name	Computer Science
topics[2].score	0.9968000054359436
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/1707
topics[2].subfield.display_name	Computer Vision and Pattern Recognition
topics[2].display_name	Robotic Path Planning Algorithms
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C93693863
concepts[0].level	2
concepts[0].score	0.7714716196060181
concepts[0].wikidata	https://www.wikidata.org/wiki/Q897659
concepts[0].display_name	Branch and bound
concepts[1].id	https://openalex.org/C173801870
concepts[1].level	2
concepts[1].score	0.6564031839370728
concepts[1].wikidata	https://www.wikidata.org/wiki/Q201413
concepts[1].display_name	Heuristic
concepts[2].id	https://openalex.org/C204323151
concepts[2].level	2
concepts[2].score	0.6337875127792358
concepts[2].wikidata	https://www.wikidata.org/wiki/Q905424
concepts[2].display_name	Range (aeronautics)
concepts[3].id	https://openalex.org/C2777303404
concepts[3].level	2
concepts[3].score	0.5719970464706421
concepts[3].wikidata	https://www.wikidata.org/wiki/Q759757
concepts[3].display_name	Convergence (economics)
concepts[4].id	https://openalex.org/C126255220
concepts[4].level	1
concepts[4].score	0.5660499334335327
concepts[4].wikidata	https://www.wikidata.org/wiki/Q141495
concepts[4].display_name	Mathematical optimization
concepts[5].id	https://openalex.org/C2778572836
concepts[5].level	2
concepts[5].score	0.5280131697654724
concepts[5].wikidata	https://www.wikidata.org/wiki/Q380933
concepts[5].display_name	Space (punctuation)
concepts[6].id	https://openalex.org/C41008148
concepts[6].level	0
concepts[6].score	0.513969361782074
concepts[6].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[6].display_name	Computer science
concepts[7].id	https://openalex.org/C77553402
concepts[7].level	2
concepts[7].score	0.46284741163253784
concepts[7].wikidata	https://www.wikidata.org/wiki/Q13222579
concepts[7].display_name	Upper and lower bounds
concepts[8].id	https://openalex.org/C62692426
concepts[8].level	3
concepts[8].score	0.41520678997039795
concepts[8].wikidata	https://www.wikidata.org/wiki/Q816319
concepts[8].display_name	Depth-first search
concepts[9].id	https://openalex.org/C125583679
concepts[9].level	2
concepts[9].score	0.39854177832603455
concepts[9].wikidata	https://www.wikidata.org/wiki/Q755673
concepts[9].display_name	Search algorithm
concepts[10].id	https://openalex.org/C33923547
concepts[10].level	0
concepts[10].score	0.39176061749458313
concepts[10].wikidata	https://www.wikidata.org/wiki/Q395
concepts[10].display_name	Mathematics
concepts[11].id	https://openalex.org/C11413529
concepts[11].level	1
concepts[11].score	0.34523916244506836
concepts[11].wikidata	https://www.wikidata.org/wiki/Q8366
concepts[11].display_name	Algorithm
concepts[12].id	https://openalex.org/C127413603
concepts[12].level	0
concepts[12].score	0.07301133871078491
concepts[12].wikidata	https://www.wikidata.org/wiki/Q11023
concepts[12].display_name	Engineering
concepts[13].id	https://openalex.org/C111919701
concepts[13].level	1
concepts[13].score	0.0
concepts[13].wikidata	https://www.wikidata.org/wiki/Q9135
concepts[13].display_name	Operating system
concepts[14].id	https://openalex.org/C134306372
concepts[14].level	1
concepts[14].score	0.0
concepts[14].wikidata	https://www.wikidata.org/wiki/Q7754
concepts[14].display_name	Mathematical analysis
concepts[15].id	https://openalex.org/C50522688
concepts[15].level	1
concepts[15].score	0.0
concepts[15].wikidata	https://www.wikidata.org/wiki/Q189833
concepts[15].display_name	Economic growth
concepts[16].id	https://openalex.org/C162324750
concepts[16].level	0
concepts[16].score	0.0
concepts[16].wikidata	https://www.wikidata.org/wiki/Q8134
concepts[16].display_name	Economics
concepts[17].id	https://openalex.org/C146978453
concepts[17].level	1
concepts[17].score	0.0
concepts[17].wikidata	https://www.wikidata.org/wiki/Q3798668
concepts[17].display_name	Aerospace engineering
keywords[0].id	https://openalex.org/keywords/branch-and-bound
keywords[0].score	0.7714716196060181
keywords[0].display_name	Branch and bound
keywords[1].id	https://openalex.org/keywords/heuristic
keywords[1].score	0.6564031839370728
keywords[1].display_name	Heuristic
keywords[2].id	https://openalex.org/keywords/range
keywords[2].score	0.6337875127792358
keywords[2].display_name	Range (aeronautics)
keywords[3].id	https://openalex.org/keywords/convergence
keywords[3].score	0.5719970464706421
keywords[3].display_name	Convergence (economics)
keywords[4].id	https://openalex.org/keywords/mathematical-optimization
keywords[4].score	0.5660499334335327
keywords[4].display_name	Mathematical optimization
keywords[5].id	https://openalex.org/keywords/space
keywords[5].score	0.5280131697654724
keywords[5].display_name	Space (punctuation)
keywords[6].id	https://openalex.org/keywords/computer-science
keywords[6].score	0.513969361782074
keywords[6].display_name	Computer science
keywords[7].id	https://openalex.org/keywords/upper-and-lower-bounds
keywords[7].score	0.46284741163253784
keywords[7].display_name	Upper and lower bounds
keywords[8].id	https://openalex.org/keywords/depth-first-search
keywords[8].score	0.41520678997039795
keywords[8].display_name	Depth-first search
keywords[9].id	https://openalex.org/keywords/search-algorithm
keywords[9].score	0.39854177832603455
keywords[9].display_name	Search algorithm
keywords[10].id	https://openalex.org/keywords/mathematics
keywords[10].score	0.39176061749458313
keywords[10].display_name	Mathematics
keywords[11].id	https://openalex.org/keywords/algorithm
keywords[11].score	0.34523916244506836
keywords[11].display_name	Algorithm
keywords[12].id	https://openalex.org/keywords/engineering
keywords[12].score	0.07301133871078491
keywords[12].display_name	Engineering
language	en
locations[0].id	doi:10.1609/socs.v5i1.18338
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4387284494
locations[0].source.issn	2832-9163, 2832-9171
locations[0].source.type	journal
locations[0].source.is_oa	True
locations[0].source.issn_l	2832-9163
locations[0].source.is_core	True
locations[0].source.is_in_doaj	False
locations[0].source.display_name	Proceedings of the International Symposium on Combinatorial Search
locations[0].source.host_organization
locations[0].source.host_organization_name
locations[0].license
locations[0].pdf_url	https://ojs.aaai.org/index.php/SOCS/article/download/18338/18129
locations[0].version	publishedVersion
locations[0].raw_type	journal-article
locations[0].license_id
locations[0].is_accepted	True
locations[0].is_published	True
locations[0].raw_source_name	Proceedings of the International Symposium on Combinatorial Search
locations[0].landing_page_url	https://doi.org/10.1609/socs.v5i1.18338
indexed_in	crossref
authorships[0].author.id	https://openalex.org/A5007629410
authorships[0].author.orcid	https://orcid.org/0000-0001-7947-3684
authorships[0].author.display_name	Carlos Hernández
authorships[0].countries	CL
authorships[0].affiliations[0].institution_ids	https://openalex.org/I38685851
authorships[0].affiliations[0].raw_affiliation_string	Universidad Católica de la Santísima Concepción
authorships[0].institutions[0].id	https://openalex.org/I38685851
authorships[0].institutions[0].ror	https://ror.org/03y6k2j68
authorships[0].institutions[0].type	education
authorships[0].institutions[0].lineage	https://openalex.org/I38685851
authorships[0].institutions[0].country_code	CL
authorships[0].institutions[0].display_name	Universidad Católica de la Santísima Concepción
authorships[0].author_position	first
authorships[0].raw_author_name	Carlos Hernandez
authorships[0].is_corresponding	False
authorships[0].raw_affiliation_strings	Universidad Católica de la Santísima Concepción
authorships[1].author.id	https://openalex.org/A5030967950
authorships[1].author.orcid	https://orcid.org/0000-0002-6280-5619
authorships[1].author.display_name	Jorge A. Baier
authorships[1].countries	CL
authorships[1].affiliations[0].institution_ids	https://openalex.org/I162148367
authorships[1].affiliations[0].raw_affiliation_string	Pontificia universidad catolica de chile
authorships[1].institutions[0].id	https://openalex.org/I162148367
authorships[1].institutions[0].ror	https://ror.org/04teye511
authorships[1].institutions[0].type	education
authorships[1].institutions[0].lineage	https://openalex.org/I162148367
authorships[1].institutions[0].country_code	CL
authorships[1].institutions[0].display_name	Pontificia Universidad Católica de Chile
authorships[1].author_position	last
authorships[1].raw_author_name	Jorge Baier
authorships[1].is_corresponding	False
authorships[1].raw_affiliation_strings	Pontificia universidad catolica de chile
has_content.pdf	True
has_content.grobid_xml	True
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://ojs.aaai.org/index.php/SOCS/article/download/18338/18129
open_access.oa_status	diamond
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Toward a Search Strategy for Anytime Search in Linear Space Using Depth-First Branch and Bound
has_fulltext	True
is_retracted	False
updated_date	2025-11-06T03:46:38.306776
primary_topic.id	https://openalex.org/T10906
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9995999932289124
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1702
primary_topic.subfield.display_name	Artificial Intelligence
primary_topic.display_name	AI-based Problem Solving and Planning
related_works	https://openalex.org/W2389899617, https://openalex.org/W1931020284, https://openalex.org/W4319942994, https://openalex.org/W2182290077, https://openalex.org/W2376570066, https://openalex.org/W3098335909, https://openalex.org/W2037710955, https://openalex.org/W4302010637, https://openalex.org/W2354057059, https://openalex.org/W2115576180
cited_by_count	1
counts_by_year[0].year	2021
counts_by_year[0].cited_by_count	1
locations_count	1
best_oa_location.id	doi:10.1609/socs.v5i1.18338
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4387284494
best_oa_location.source.issn	2832-9163, 2832-9171
best_oa_location.source.type	journal
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l	2832-9163
best_oa_location.source.is_core	True
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	Proceedings of the International Symposium on Combinatorial Search
best_oa_location.source.host_organization
best_oa_location.source.host_organization_name
best_oa_location.license
best_oa_location.pdf_url	https://ojs.aaai.org/index.php/SOCS/article/download/18338/18129
best_oa_location.version	publishedVersion
best_oa_location.raw_type	journal-article
best_oa_location.license_id
best_oa_location.is_accepted	True
best_oa_location.is_published	True
best_oa_location.raw_source_name	Proceedings of the International Symposium on Combinatorial Search
best_oa_location.landing_page_url	https://doi.org/10.1609/socs.v5i1.18338
primary_location.id	doi:10.1609/socs.v5i1.18338
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4387284494
primary_location.source.issn	2832-9163, 2832-9171
primary_location.source.type	journal
primary_location.source.is_oa	True
primary_location.source.issn_l	2832-9163
primary_location.source.is_core	True
primary_location.source.is_in_doaj	False
primary_location.source.display_name	Proceedings of the International Symposium on Combinatorial Search
primary_location.source.host_organization
primary_location.source.host_organization_name
primary_location.license
primary_location.pdf_url	https://ojs.aaai.org/index.php/SOCS/article/download/18338/18129
primary_location.version	publishedVersion
primary_location.raw_type	journal-article
primary_location.license_id
primary_location.is_accepted	True
primary_location.is_published	True
primary_location.raw_source_name	Proceedings of the International Symposium on Combinatorial Search
primary_location.landing_page_url	https://doi.org/10.1609/socs.v5i1.18338
publication_date	2021-09-01
publication_year	2021
referenced_works	https://openalex.org/W6636375679, https://openalex.org/W1591988133, https://openalex.org/W2293009092, https://openalex.org/W6683620479, https://openalex.org/W6659469833, https://openalex.org/W2165946530, https://openalex.org/W2171440583, https://openalex.org/W2324108981, https://openalex.org/W2150470619, https://openalex.org/W2161076907, https://openalex.org/W2144931885, https://openalex.org/W1622225657, https://openalex.org/W2035601288, https://openalex.org/W2242756877, https://openalex.org/W4248795023
referenced_works_count	15
abstract_inverted_index.a	19, 44, 98
abstract_inverted_index.In	14
abstract_inverted_index.We	75
abstract_inverted_index.an	6
abstract_inverted_index.in	32, 65
abstract_inverted_index.is	5, 47
abstract_inverted_index.of	22, 67, 87, 101
abstract_inverted_index.on	84
abstract_inverted_index.or	56
abstract_inverted_index.to	72
abstract_inverted_index.we	17
abstract_inverted_index.Our	39
abstract_inverted_index.and	2, 35, 70
abstract_inverted_index.can	60
abstract_inverted_index.for	9, 29, 81
abstract_inverted_index.the	48, 73, 85
abstract_inverted_index.both	64
abstract_inverted_index.from	43
abstract_inverted_index.main	40
abstract_inverted_index.more	82
abstract_inverted_index.that	50, 91
abstract_inverted_index.this	15, 77
abstract_inverted_index.used	52
abstract_inverted_index.with	54
abstract_inverted_index.Bound	3
abstract_inverted_index.DFBnB	63
abstract_inverted_index.along	53
abstract_inverted_index.calls	80
abstract_inverted_index.could	92
abstract_inverted_index.drawn	42
abstract_inverted_index.paper	16
abstract_inverted_index.range	100
abstract_inverted_index.small	78
abstract_inverted_index.study	79
abstract_inverted_index.terms	66
abstract_inverted_index.think	76
abstract_inverted_index.using	30
abstract_inverted_index.which	25
abstract_inverted_index.wider	99
abstract_inverted_index.Branch	1
abstract_inverted_index.DFBnB,	23
abstract_inverted_index.across	97
abstract_inverted_index.design	86
abstract_inverted_index.offers	36
abstract_inverted_index.search	34
abstract_inverted_index.weight	58, 89
abstract_inverted_index.(DFBnB)	4
abstract_inverted_index.anytime	7, 68, 95
abstract_inverted_index.present	18
abstract_inverted_index.provide	93
abstract_inverted_index.solving	10
abstract_inverted_index.version	21
abstract_inverted_index.wDFBnB,	24, 51
abstract_inverted_index.weights	31
abstract_inverted_index.behavior	69
abstract_inverted_index.domains.	102
abstract_inverted_index.optimal.	74
abstract_inverted_index.research	83
abstract_inverted_index.standard	27
abstract_inverted_index.superior	94
abstract_inverted_index.weighted	20
abstract_inverted_index.algorithm	8
abstract_inverted_index.automated	55, 88
abstract_inverted_index.heuristic	33
abstract_inverted_index.problems.	13
abstract_inverted_index.schedules	90
abstract_inverted_index.evaluation	46
abstract_inverted_index.outperform	62
abstract_inverted_index.schedules,	59
abstract_inverted_index.techniques	28
abstract_inverted_index.Depth-First	0
abstract_inverted_index.convergence	71
abstract_inverted_index.guarantees.	38
abstract_inverted_index.observation	49
abstract_inverted_index.performance	96
abstract_inverted_index.preliminary	45
abstract_inverted_index.contribution	41
abstract_inverted_index.hand-crafted	57
abstract_inverted_index.incorporates	26
abstract_inverted_index.optimization	12
abstract_inverted_index.combinatorial	11
abstract_inverted_index.significantly	61
abstract_inverted_index.suboptimality	37
cited_by_percentile_year.max	93
cited_by_percentile_year.min	89
countries_distinct_count	1
institutions_distinct_count	2
citation_normalized_percentile.value	0.50436683
citation_normalized_percentile.is_in_top_1_percent	False
citation_normalized_percentile.is_in_top_10_percent	False