Local search versus linear programming to detect monotonicity in simplicial branch and bound

L. G. Casado (), B. G.-Tóth (), E. M. T. Hendrix () and F. Messine ()
Additional contact information
L. G. Casado: University of Almería
B. G.-Tóth: University of Szeged
E. M. T. Hendrix: Universidad de Málaga and Wageningen University
F. Messine: University of Toulouse

Journal of Global Optimization, 2025, vol. 91, issue 2, No 4, 330 pages

Abstract: Abstract This study focuses on exhaustive global optimization algorithms over a simplicial feasible set with simplicial partition sets. Bounds on the objective function value and its partial derivative are based on interval automatic differentiation over the interval hull of a simplex. A monotonicity test may be used to decide to either reject a simplicial partition set or to reduce its simplicial dimension to a relative border (at the boundary of the feasible set) facet (or face) by removing one (or more) vertices. A monotonicity test is more complicated for a simplicial sub-set than for a box, because its orientation does not coincide with the components of the gradient. However, one can focus on directional derivatives (DD). In a previous study, we focused on either basic directions, such as centroid to vertex or vertex to vertex directions, or finding the best directional derivative by solving an LP or MIP. The research question of this paper refers to using local search (LS) based sampling of directions from vertex to facet. Results show that most of the monotonic DD found by LP are also found by LS, but with much less computational cost. Notice that finding a monotone direction does not require to find the direction in which a derivative bound is the steepest.

Keywords: Simplex; Branch and bound; Interval arithmetic; Linear programming; Local search (search for similar items in EconPapers)
Date: 2025
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-023-01310-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:91:y:2025:i:2:d:10.1007_s10898-023-01310-y

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-023-01310-y

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().