TY - JOUR

T1 - lsmear

T2 - a variable selection strategy for interval branch and bound solvers

AU - Araya, Ignacio

AU - Neveu, Bertrand

N1 - Publisher Copyright:
© 2017, Springer Science+Business Media, LLC.

PY - 2018/7/1

Y1 - 2018/7/1

N2 - Smear-based variable selection strategies are well-known and commonly used by branch-and-prune interval-based solvers. They estimate the impact of the variables on each constraint of the system by using the partial derivatives and the sizes of the variable domains. Then they aggregate these values, in some way, to estimate the impact of each variable on the whole system. The variable with the greatest impact is then selected. A problem of these strategies is that they, generally, consider all constraints equally important. In this work, we propose a new variable selection strategy which first weights the constraints by using the optimal Lagrangian multipliers of a linearization of the original problem. Then, the impact of the variables is computed with a typical smear-based function but taking into account the weights of the constraints. The strategy isg tested on a set of well-known benchmark instances outperforming significantly the classical variable selection strategies.

AB - Smear-based variable selection strategies are well-known and commonly used by branch-and-prune interval-based solvers. They estimate the impact of the variables on each constraint of the system by using the partial derivatives and the sizes of the variable domains. Then they aggregate these values, in some way, to estimate the impact of each variable on the whole system. The variable with the greatest impact is then selected. A problem of these strategies is that they, generally, consider all constraints equally important. In this work, we propose a new variable selection strategy which first weights the constraints by using the optimal Lagrangian multipliers of a linearization of the original problem. Then, the impact of the variables is computed with a typical smear-based function but taking into account the weights of the constraints. The strategy isg tested on a set of well-known benchmark instances outperforming significantly the classical variable selection strategies.

KW - Branch and bound

KW - Interval-based solver

KW - Lagrangian multipliers

KW - Variable selection

UR - http://www.scopus.com/inward/record.url?scp=85029153750&partnerID=8YFLogxK

U2 - 10.1007/s10898-017-0569-y

DO - 10.1007/s10898-017-0569-y

M3 - Article

AN - SCOPUS:85029153750

SN - 0925-5001

VL - 71

SP - 483

EP - 500

JO - Journal of Global Optimization

JF - Journal of Global Optimization

IS - 3

ER -