A new Branch and Bound method for a discrete truss topology design problem

A. Cerveira, A. Agra, F. Bastos, J.A. Gromicho Dos Santos

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

Our paper considers a classic problem in the field of Truss Topology Design, the goal of which is to determine the stiffest truss, under a given load, with a bound on the total volume and discrete requirements in the cross-sectional areas of the bars. To solve this problem we propose a new two-stage Branch and Bound algorithm. In the first stage we perform a Branch and Bound algorithm on the nodes of the structure. This is based on the following dichotomy study: either a node is in the final structure or not. In the second stage, a Branch and Bound on the bar areas is conducted. The existence or otherwise of a node in this structure is ensured by adding constraints on the cross-sectional areas of its incident bars. In practice, for reasons of stability, free bars linked at free nodes should be avoided. Therefore, if a node exists in the structure, then there must be at least two incident bars on it, unless it is a supported node. Thus, a new constraint is added, which lower bounds the sum of the cross-sectional areas of bars incident to the node. Otherwise, if a free node does not belong to the final structure, then all the bar area variables corresponding to bars incident to this node may be set to zero. These constraints are added during the first stage and lead to a tight model. We report the computational experiments conducted to test the effectiveness of this two-stage approach, enhanced by the rule to prevent free bars, as compared to a classical Branch and Bound algorithm, where branching is only performed on the bar areas. © 2012 Springer Science+Business Media, LLC.
Original languageEnglish
Pages (from-to)163-172
Number of pages9
JournalComputational Optimization and Applications
Volume54
Issue number1
DOIs
Publication statusPublished - 2012

Fingerprint

Branch and bound method
Branch and Bound Method
Topology
Vertex of a graph
Branch and Bound Algorithm
Design
Dichotomy
Branch-and-bound
Computational Experiments
Branching
Lower bound

Cite this

@article{e5c775a34e804f82804288b360fa3607,
title = "A new Branch and Bound method for a discrete truss topology design problem",
abstract = "Our paper considers a classic problem in the field of Truss Topology Design, the goal of which is to determine the stiffest truss, under a given load, with a bound on the total volume and discrete requirements in the cross-sectional areas of the bars. To solve this problem we propose a new two-stage Branch and Bound algorithm. In the first stage we perform a Branch and Bound algorithm on the nodes of the structure. This is based on the following dichotomy study: either a node is in the final structure or not. In the second stage, a Branch and Bound on the bar areas is conducted. The existence or otherwise of a node in this structure is ensured by adding constraints on the cross-sectional areas of its incident bars. In practice, for reasons of stability, free bars linked at free nodes should be avoided. Therefore, if a node exists in the structure, then there must be at least two incident bars on it, unless it is a supported node. Thus, a new constraint is added, which lower bounds the sum of the cross-sectional areas of bars incident to the node. Otherwise, if a free node does not belong to the final structure, then all the bar area variables corresponding to bars incident to this node may be set to zero. These constraints are added during the first stage and lead to a tight model. We report the computational experiments conducted to test the effectiveness of this two-stage approach, enhanced by the rule to prevent free bars, as compared to a classical Branch and Bound algorithm, where branching is only performed on the bar areas. {\circledC} 2012 Springer Science+Business Media, LLC.",
author = "A. Cerveira and A. Agra and F. Bastos and {Gromicho Dos Santos}, J.A.",
year = "2012",
doi = "10.1007/s10589-012-9487-6",
language = "English",
volume = "54",
pages = "163--172",
journal = "Computational Optimization and Applications",
issn = "0926-6003",
publisher = "Springer Netherlands",
number = "1",

}

A new Branch and Bound method for a discrete truss topology design problem. / Cerveira, A.; Agra, A.; Bastos, F.; Gromicho Dos Santos, J.A.

In: Computational Optimization and Applications, Vol. 54, No. 1, 2012, p. 163-172.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

T1 - A new Branch and Bound method for a discrete truss topology design problem

AU - Cerveira, A.

AU - Agra, A.

AU - Bastos, F.

AU - Gromicho Dos Santos, J.A.

PY - 2012

Y1 - 2012

N2 - Our paper considers a classic problem in the field of Truss Topology Design, the goal of which is to determine the stiffest truss, under a given load, with a bound on the total volume and discrete requirements in the cross-sectional areas of the bars. To solve this problem we propose a new two-stage Branch and Bound algorithm. In the first stage we perform a Branch and Bound algorithm on the nodes of the structure. This is based on the following dichotomy study: either a node is in the final structure or not. In the second stage, a Branch and Bound on the bar areas is conducted. The existence or otherwise of a node in this structure is ensured by adding constraints on the cross-sectional areas of its incident bars. In practice, for reasons of stability, free bars linked at free nodes should be avoided. Therefore, if a node exists in the structure, then there must be at least two incident bars on it, unless it is a supported node. Thus, a new constraint is added, which lower bounds the sum of the cross-sectional areas of bars incident to the node. Otherwise, if a free node does not belong to the final structure, then all the bar area variables corresponding to bars incident to this node may be set to zero. These constraints are added during the first stage and lead to a tight model. We report the computational experiments conducted to test the effectiveness of this two-stage approach, enhanced by the rule to prevent free bars, as compared to a classical Branch and Bound algorithm, where branching is only performed on the bar areas. © 2012 Springer Science+Business Media, LLC.

AB - Our paper considers a classic problem in the field of Truss Topology Design, the goal of which is to determine the stiffest truss, under a given load, with a bound on the total volume and discrete requirements in the cross-sectional areas of the bars. To solve this problem we propose a new two-stage Branch and Bound algorithm. In the first stage we perform a Branch and Bound algorithm on the nodes of the structure. This is based on the following dichotomy study: either a node is in the final structure or not. In the second stage, a Branch and Bound on the bar areas is conducted. The existence or otherwise of a node in this structure is ensured by adding constraints on the cross-sectional areas of its incident bars. In practice, for reasons of stability, free bars linked at free nodes should be avoided. Therefore, if a node exists in the structure, then there must be at least two incident bars on it, unless it is a supported node. Thus, a new constraint is added, which lower bounds the sum of the cross-sectional areas of bars incident to the node. Otherwise, if a free node does not belong to the final structure, then all the bar area variables corresponding to bars incident to this node may be set to zero. These constraints are added during the first stage and lead to a tight model. We report the computational experiments conducted to test the effectiveness of this two-stage approach, enhanced by the rule to prevent free bars, as compared to a classical Branch and Bound algorithm, where branching is only performed on the bar areas. © 2012 Springer Science+Business Media, LLC.

U2 - 10.1007/s10589-012-9487-6

DO - 10.1007/s10589-012-9487-6

M3 - Article

VL - 54

SP - 163

EP - 172

JO - Computational Optimization and Applications

JF - Computational Optimization and Applications

SN - 0926-6003

IS - 1

ER -