Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2306.14661 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913235425296384 |
|---|---|
| author | Chen, Zhongzhu Fampa, Marcia Lee, Jon |
| author_facet | Chen, Zhongzhu Fampa, Marcia Lee, Jon |
| contents | The best practical techniques for exact solution of instances of the constrained maximum-entropy sampling problem, a discrete-optimization problem arising in the design of experiments, are via a branch-and-bound framework, working with a variety of concave continuous relaxations of the objective function. A standard and computationally-important bound-enhancement technique in this context is (ordinary) scaling, via a single positive parameter. Scaling adjusts the shape of continuous relaxations to reduce the gaps between the upper bounds and the optimal value. We extend this technique to generalized scaling, employing a positive vector of parameters, which allows much more flexibility and thus potentially reduces the gaps further. We give mathematical results aimed at supporting algorithmic methods for computing optimal generalized scalings, and we give computational results demonstrating the performance of generalized scaling on benchmark problem instances. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_14661 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Generalized Scaling for the Constrained Maximum-Entropy Sampling Problem Chen, Zhongzhu Fampa, Marcia Lee, Jon Optimization and Control 90C25, 90C27, 90C51, 62K99, 62H11 The best practical techniques for exact solution of instances of the constrained maximum-entropy sampling problem, a discrete-optimization problem arising in the design of experiments, are via a branch-and-bound framework, working with a variety of concave continuous relaxations of the objective function. A standard and computationally-important bound-enhancement technique in this context is (ordinary) scaling, via a single positive parameter. Scaling adjusts the shape of continuous relaxations to reduce the gaps between the upper bounds and the optimal value. We extend this technique to generalized scaling, employing a positive vector of parameters, which allows much more flexibility and thus potentially reduces the gaps further. We give mathematical results aimed at supporting algorithmic methods for computing optimal generalized scalings, and we give computational results demonstrating the performance of generalized scaling on benchmark problem instances. |
| title | Generalized Scaling for the Constrained Maximum-Entropy Sampling Problem |
| topic | Optimization and Control 90C25, 90C27, 90C51, 62K99, 62H11 |
| url | https://arxiv.org/abs/2306.14661 |