A platform for research: civil engineering, architecture and urbanism
A platform for research: civil engineering, architecture and urbanism
Comparison of mixed-integer relaxations with linear and logarithmic partitioning schemes for quadratically constrained problems
https://orcid.org/http://orcid.org/0000-0002-4898-8922
Piecewise relaxations are powerful techniques to compute strong dual bounds for (mixed-integer) quadratically constrained problems and provide starting points that can be used by local nonlinear solvers to generate high-quality primal solutions. They work by first partitioning the domain of one of the variables in every quadratic or bilinear term and then selecting the optimal interval in the partition through binary variables. A variety of formulations have been proposed that can be distinguished based on how the number of binary variables scales with the number of intervals. In this paper, we compare linear and logarithmic partitioning schemes that can be derived from the piecewise McCormick relaxation (PCM) or the multiparametric disaggregation technique (MDT). Specifically, we propose MDT for a generic numeric representation system, showing that it becomes a linear partitioning scheme when considering a single digit and varying the basis, and a logarithmic partitioning scheme when fixing the basis and varying the number of digits. Through the solution of 25 benchmark instances for the pooling problem, considering relaxations for the p-, q- and tp-formulations, we show that it is better to rely on the linear scheme from PCM for a small number of intervals and on the logarithmic scheme from base-2 MDT when the number is large. The results also show that significantly stronger dual bounds can be obtained compared to commercial global optimization solvers BARON and GloMIQO.
Comparison of mixed-integer relaxations with linear and logarithmic partitioning schemes for quadratically constrained problems
https://orcid.org/http://orcid.org/0000-0002-4898-8922
Piecewise relaxations are powerful techniques to compute strong dual bounds for (mixed-integer) quadratically constrained problems and provide starting points that can be used by local nonlinear solvers to generate high-quality primal solutions. They work by first partitioning the domain of one of the variables in every quadratic or bilinear term and then selecting the optimal interval in the partition through binary variables. A variety of formulations have been proposed that can be distinguished based on how the number of binary variables scales with the number of intervals. In this paper, we compare linear and logarithmic partitioning schemes that can be derived from the piecewise McCormick relaxation (PCM) or the multiparametric disaggregation technique (MDT). Specifically, we propose MDT for a generic numeric representation system, showing that it becomes a linear partitioning scheme when considering a single digit and varying the basis, and a logarithmic partitioning scheme when fixing the basis and varying the number of digits. Through the solution of 25 benchmark instances for the pooling problem, considering relaxations for the p-, q- and tp-formulations, we show that it is better to rely on the linear scheme from PCM for a small number of intervals and on the logarithmic scheme from base-2 MDT when the number is large. The results also show that significantly stronger dual bounds can be obtained compared to commercial global optimization solvers BARON and GloMIQO.
Comparison of mixed-integer relaxations with linear and logarithmic partitioning schemes for quadratically constrained problems
https://orcid.org/http://orcid.org/0000-0002-4898-8922
Piecewise relaxations are powerful techniques to compute strong dual bounds for (mixed-integer) quadratically constrained problems and provide starting points that can be used by local nonlinear solvers to generate high-quality primal solutions. They work by first partitioning the domain of one of the variables in every quadratic or bilinear term and then selecting the optimal interval in the partition through binary variables. A variety of formulations have been proposed that can be distinguished based on how the number of binary variables scales with the number of intervals. In this paper, we compare linear and logarithmic partitioning schemes that can be derived from the piecewise McCormick relaxation (PCM) or the multiparametric disaggregation technique (MDT). Specifically, we propose MDT for a generic numeric representation system, showing that it becomes a linear partitioning scheme when considering a single digit and varying the basis, and a logarithmic partitioning scheme when fixing the basis and varying the number of digits. Through the solution of 25 benchmark instances for the pooling problem, considering relaxations for the p-, q- and tp-formulations, we show that it is better to rely on the linear scheme from PCM for a small number of intervals and on the logarithmic scheme from base-2 MDT when the number is large. The results also show that significantly stronger dual bounds can be obtained compared to commercial global optimization solvers BARON and GloMIQO.
Comparison of mixed-integer relaxations with linear and logarithmic partitioning schemes for quadratically constrained problems
Optim Eng
Castro, Pedro M. (author) / Liao, Qi (author) / Liang, Yongtu (author)
Optimization and Engineering ; 23 ; 717-747
2022-06-01
31 pages
Article (Journal)
Electronic Resource
English
Bilinear program , Discretization , Disjunctive programming , Quadratic optimization , Global optimization , Pooling problem Mathematics , Optimization , Engineering, general , Systems Theory, Control , Environmental Management , Operations Research/Decision Theory , Financial Engineering , Mathematics and Statistics
Stable relaxations of stochastic stress-constrained weight minimization problems
| British Library Online Contents | 2003
A mixed-integer approximation of robust optimization problems with mixed-integer adjustments
| Springer Verlag | 2024
A mixed-integer approximation of robust optimization problems with mixed-integer adjustments
| Springer Verlag | 2024
Mixed-Integer Chance-Constrained Models for Ground-Water Remediation
| Online Contents | 1998
Mixed-Integer Chance-Constrained Models for Ground-Water Remediation
| British Library Online Contents | 1998