Solving continuous set covering problems by means of semi-infinite optimization
Open Access
- 29 March 2022
- journal article
- research article
- Published by Springer Nature in Mathematical Methods of Operations Research
- Vol. 96 (1) , 39-82
Abstract
This article introduces the new class of continuous set covering problems. These optimization problems result, among others, from product portfolio design tasks with products depending continuously on design parameters and the requirement that the product portfolio satisfies customer specifications that are provided as a compact set. We show that the problem can be formulated as semi-infinite optimization problem (SIP). Yet, the inherent non-smoothness of the semi-infinite constraint function hinders the straightforward application of standard methods from semi-infinite programming. We suggest an algorithm combining adaptive discretization of the infinite index set and replacement of the non-smooth constraint function by a two-parametric smoothing function. Under few requirements, the algorithm converges and the distance of a current iterate can be bounded in terms of the discretization and smoothing error. By means of a numerical example from product portfolio optimization, we demonstrate that the proposed algorithm only needs relatively few discretization points and thus keeps the problem dimensions small.Keywords
Funding Information
- Fraunhofer-Institut für Techno- und Wirtschaftsmathematik ITWM
This publication has 37 references indexed in Scilit:
- Joint optimization of product family configuration and scaling design by Stackelberg gameEuropean Journal of Operational Research, 2014
- Smoothing methods for nonsmooth, nonconvex minimizationMathematical Programming, 2012
- John and Loewner EllipsoidsDiscrete & Computational Geometry, 2011
- Optimization of multiple covering of a bounded set with circlesComputational Mathematics and Mathematical Physics, 2010
- Data-Driven Decision Tree Classification for Product Portfolio Design OptimizationJournal of Computing and Information Science in Engineering, 2009
- Solution of continuous problems of optimal covering with spheres using optimal set-partition theoryCybernetics and Systems Analysis, 2009
- Covering a rectangle with six and seven circlesDiscrete Applied Mathematics, 2000
- On the entropic regularization method for solving min-max problems with applicationsMathematical Methods of Operations Research, 1997
- ON ENTROPY-BASED METHODS FOR NONLINEAR PROGRAMMING PROBLEMSEngineering Optimization, 1995
- A continuous set covering problem as a quasidifferentiable optimization problemOptimization, 1988