Computing a global optimal solution to a design centering problem. (English) Zbl 0751.90071

Summary: We present a method for solving a special three-dimensional design centering problem arising in diamond manufacturing: Find inside a given (not necessarily convex) polyhedral rough stone the largest diamond of prescribed shape and orientation. This problem can be formulated as the one of finding a global maximum of a difference of two convex functions over \(\mathbb{R}^ 3\) and can be solved efficiently by using a global optimization algorithm provided that the objective function of the maximization problem can be easily evaluated. Here we prove that with the information available on the rough stone and on the reference diamond, evaluating the objective function at a point \(x\) amounts to computing the distance, with respect to a Minkowski gauge, from \(x\) to a finite number of planes. We propose a method for finding these planes and we report some numerical results.


90C30 Nonlinear programming
90C90 Applications of mathematical programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
Full Text: DOI


[1] E. Bruton,Diamonds (N.A.G. Press, London, 1978).
[2] A. Groch, L. Vigidal and S. Director, ”A new global optimization method for electronic circuit design,”IEEE Transactions on Circuits and Systems 32 (1985) 160–170.
[3] R. Hillestad and S. Jacobsen, ”Linear programs with an additional reverse convex constraint,”Journal of Applied Mathematics and Optimization 6 (1980) 257–268. · Zbl 0435.90065
[4] J.-B. Hiriart-Urruty, ”Generalized differentiability, duality and optimization for problems dealing with differences of convex functions,” in:Lecture Notes in Economics and Mathematics Systems No. 256 (Springer, Berlin, 1985) pp. 37–70. · Zbl 0591.90073
[5] T. Pham Dinh, J. Chaarani and S. El Bernoussi, ”Global numerical algorithms for solving a class of nonconvex optimization problems,” Laboratoire TIM 3 Technical Report, IMAG, Université de Grenoble (Grenoble, 1988).
[6] R.T. Rockafellar,Convex Analysis (Princeton University Press, NJ, 1970). · Zbl 0193.18401
[7] R. Rubinstein and G. Samorodnitsky, ”Optimal coverage of convex regions,”Journal of Optimization Theory and Applications 51 (1986) 321–343. · Zbl 0581.90074
[8] J.-J. Strodiot and V.H. Nguyen, ”Taille optimale de diamants,” Report 79/5, Department of Mathematics, Facultés Universitaires Notre-Dame de la Paix (Namur, 1979).
[9] J.-J. Strodiot, V.H. Nguyen and N.V. Thoai, ”On an optimum shape design problem,” Report 85/5, Department of Mathematics, Facultés Universitaires Notre-Dame de la Paix (Namur, 1985).
[10] P.T. Thach, ”The design centering problem as a d.c. programming problem,”Mathematical Programming 41 (1988) 229–248. · Zbl 0651.90065
[11] N.V. Thoai, ”A modified version of Tuy’s method for solving d.c. programming problems,” CORE Discussion Paper No. 8528 (Louvain, 1985). · Zbl 0662.90069
[12] H. Tuy, ”A general deterministic approach to global optimization via d.c. programming,” in: J.-B. Hiriart-Urruty, ed.,Fermat Days 85: Mathematics for Optimization (North-Holland, Amsterdam, 1986) pp. 273–303. · Zbl 0623.65067
[13] L. Vigidal and S. Director, ”A design centering algorithm for nonconvex regions of acceptability,”IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (1982) 13–24.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.