Packing circles within ellipses
E. G. Birgin, L. H. Bustamante, H. F. Callisaya, and J. M. Martínez
submitted.
Abstract: The problem of packing circles within ellipses is considered in the present paper. A new parametrization is employed by means of which the ellipse is represented by a rectangle. Algorithms with global convergence properties are presented. Numerical experiments are exhibited.
Keywords: Packing, ellipses, circles, global optimization.
Full text: [pdf]
Deterministic and stochastic global optimization techniques for planar covering with ellipses problems
M. Andretta and E. G. Birgin
submitted.
Abstract: Problems of planar covering with ellipses are tackled in this work. Ellipses can have a fixed angle or each of them can be freely rotated. Deterministic global optimization methods are developed for both cases, while a stochastic version of the method is also proposed for large instances of the latter case. Numerical results show the effectiveness and efficiency of the proposed methods.
Keywords: Planar covering with ellipses, deterministic global optimization, algorithms.
Full text: [pdf]
Evaluating bound-constrained minimization software
E. G. Birgin and J. M. Gentil
Computational Optimization and Applications, to appear.
Abstract: Bound-constrained minimization is a subject of active research. To assess the performance of existent solvers, numerical evaluations and comparisons are carried on. Arbitrary decisions that may have a crucial effect on the conclusions of numerical experiments are highlighted in the present work. As a result, a detailed evaluation based on performance profiles is applied to the comparison of bound-constrained minimization solvers. Extensive numerical results are presented and analyzed.
Keywords: Bound-constrained minimization, benchmarking, numerical evaluation, performance profiles.
Full text: [pdf]
Symmetry-breaking constraints for packing identical orthogonal rectangles within polyhedra
R. Andrade and E. G. Birgin
Optimization Letters, to appear.
Abstract: Two problems related to packing identical orthogonal rectangles within a polyhedron are tackled in the present work. The first problem consists in packing as many identical rectangles as possible within a given polyhedron, while the second problem consists in finding the smallest polyhedron of a given type that accommodates a fixed number of identical rectangles. Both problems are modeled as mixed integer programming problems. Symmetry-breaking constraints that facilitate the solution of the MIP models are introduced. Numerical results are presented.
Keywords: Packing of rectangles, MIP models, symmetry-breaking constraints, algorithms.
Full text: [pdf]
Heuristic methods for the single machine scheduling problem with different ready times and a common due date
E. G. Birgin and D. P. Ronconi
Engineering Optimization, to appear.
Abstract: The single machine scheduling problem with a common due date and non-identical ready times for the jobs is examined in this work. Performance is measured by the minimization of the weighted sum of earliness and tardiness penalties of the jobs. Since this problem is NP-hard, we investigate the application of constructive heuristics that exploit specific characteristics of the problem to improve their performance. The proposed approaches are examined through a computational comparative study on a set of 280 benchmark test problems with up to 1000 jobs.
Keywords: Scheduling, single machine, earliness and tardiness, heuristic methods.
Full text: [pdf]
Augmented Lagrangian method with nonmonotone penalty parameters for constrained optimization
E. G. Birgin and J. M. Martínez
Computational Optimization and Applications, to appear.
Abstract: At each outer iteration of standard Augmented Lagrangian methods one tries to solve a box-constrained optimization problem with some prescribed tolerance. In the continuous world, using exact arithmetic, this subproblem is always solvable. Therefore, the possibility of finishing the subproblem resolution without satisfying the theoretical stopping conditions is not contemplated in usual convergence theories. However, in practice, one might not be able to solve the subproblem up to the required precision. This may be due to different reasons. One of them is that the presence of an excessively large penalty parameter could impair the performance of the box-constraint optimization solver. In this paper a practical strategy for decreasing the penalty parameter in situations like the one mentioned above is proposed. More generally, the different decisions that may be taken when, in practice, one is not able to solve the Augmented Lagrangian subproblem will be discussed. As a result, an improved Augmented Lagrangian method is presented, which takes into account numerical difficulties in a satisfactory way, preserving suitable convergence theory. Numerical experiments are presented involving all the CUTEr collection test problems.
Keywords: Nonlinear Programming, Augmented Lagrangian methods, Penalty parameters, Numerical experiments.
Full text: [pdf]
On the boundedness of penalty parameters in an Augmented Lagrangian method with lower level constraints
E. G. Birgin, D. Fernandez and J. M. Martínez
Optimization Methods and Software, to appear.
Abstract: Augmented Lagrangian methods are effective tools for solving large-scale nonlinear programming problems. At each outer iteration a minimization subproblem with simple constraints, whose objective function depends on updated Lagrange multipliers and penalty parameters, is approximately solved. When the penalty parameter becomes very large the subproblem is difficult, therefore the effectiveness of this approach is associated with boundedness of penalty parameters. In this paper it is proved that, under more natural assumptions than the ones up to now employed, penalty parameters are bounded. For proving the new boundedness result, the original algorithm has been slightly modified. Numerical consequences of the modifications are discussed and computational experiments are presented.
Keywords: Nonlinear Programming, Augmented Lagrangian methods, Penalty parameters, Numerical experiments.
Full text: [pdf]
Generating unconstrained two-dimensional non-guillotine cutting patterns by a recursive partitioning algorithm
E. G. Birgin, R. D. Lobato and R. Morabito
Journal of the Operational Research Society, Vol. 63 No. 2 (February 2012), Pages 183-200.
Abstract: In this study, a dynamic programming approach to deal with the unconstrained two-dimensional non-guillotine cutting problem is presented. The method extends the recently introduced recursive partitioning approach for the manufacturer's pallet loading problem. The approach involves two phases and uses bounds based on unconstrained two-staged and non-staged guillotine cutting. The method is able to find the optimal cutting pattern of a large number of problem instances of moderate sizes known in the literature and a counterexample for which the approach fails to find known optimal solutions was not found. For the instances that the required computer runtime is excessive, the approach is combined with simple heuristics to reduce its running time. Detailed numerical experiments show the reliability of the method.
Keywords: Cutting and packing, two-dimensional non-guillotine cutting pattern, dynamic programming, recursive approach, distributor's pallet loading problem.
Full text: [pdf]
Mixed-integer programming models for flowshop scheduling problems minimizing the total earliness and tardiness
D. P. Ronconi and E. G. Birgin
in Just-in-Time Systems, R. Z. Ríos-Mercado and Y. A. Ríos-Solís (Eds.), Springer Series on Optimization and its Applications 60 (2012), Pages 91-105.
Abstract: Scheduling problems involving both earliness and tardiness costs have received significant attention in recent years. This type of problem became important with the advent of the just-in-time (JIT) concept, where early or tardy deliveries are highly discouraged. In this work we examine the flowshop scheduling problem with no storage constraints and with blocking in-process. In this latter environment, there are no buffers between successive machines; therefore intermediate queues of jobs waiting in the system for their next operations are not allowed. Performance is measured by the minimization of the sum of earliness and tardiness of the jobs. Mixed-integer models that represent these scheduling flowshop problems are presented. The models are evaluated and compared in several problems using commercial known software.
Keywords: Flowshop scheduling, earliness and tardiness, blocking in-process, mixed-integer programming formulations.
Full text: [pdf]
Low Order-Value approach for solving VaR-constrained optimization problems
E. G. Birgin, L. F. Bueno, N. Krejic and J. M. Martínez
Journal of Global Optimization Vol. 51 No. 4 (December 2011), Pages 715-742.
Abstract: In Low Order-Value Optimization (LOVO) problems the sum of the r smallest values of a finite sequence of q functions is involved as the objective to be minimized or as a constraint. The latter case is considered in the present paper. Portfolio optimization problems with a constraint on the admissible Value at Risk (VaR) can be modeled in terms of a LOVO problem with constraints given by Low Order-Value functions. Different algorithms for practical solution of this problem will be presented. Using these techniques, portfolio optimization problems with transaction costs will be solved.
Keywords: Optimization, Augmented Lagrangian, Order-Value Optimization, Low Order-Value Optimization, Value at Risk, Numerical algorithms.
Full text: [pdf]
Outer Trust-Region method for Constrained Optimization
E. G. Birgin, E. V. Castelani, A. L. M. Martinez and J. M. Martínez
Journal of Optimization Theory and Applications Vol. 150 No. 1 (July 2011), Pages 142-155.
Abstract: Given an algorithm A for solving some mathematical problem based on the iterative solution of simpler subproblems, an Outer Trust-Region (OTR) modification of A is the result of adding a trust-region constraint to each subproblem. The trust-region size is adaptively updated according to the behavior of crucial variables. The new subproblems should not be more complex than the original ones and the convergence properties of the OTR algorithm should be the same as those of Algorithm A. In the present work, the OTR approach is exploited in connection with the "greediness phenomenon" of Nonlinear Programming. Convergence results for an OTR version of an Augmented Lagrangian method for nonconvex constrained optimization are proved and numerical experiments are presented.
Keywords: Nonlinear programming, Augmented Lagrangian method, trust regions.
Full text: [pdf]
Orthogonal packing of identical rectangles within isotropic convex regions
E. G. Birgin and R. D. Lobato
Computers & Industrial Engineering Vol. 59 No. 4 (November 2010), Pages 595-602.
Abstract: A mixed integer continuous nonlinear model and a solution method for the problem of orthogonally packing identical rectangles within an arbitrary convex region are introduced in the present work. The convex region is assumed to be made of an isotropic material in such a way that arbitrary rotations of the items, preserving the orthogonality constraint, are allowed. The solution method is based on a combination of branch and bound and active-set strategies for bound-constrained minimization of smooth functions. Numerical results show the reliability of the presented approach.
Keywords: Packing and cutting of rectangles, orthogonal packing, isotropic convex regions, feasibility problems, nonlinear programming, models.
Full text: [pdf]
Continuous GRASP with a local active-set method for bound-constrained global optimization
E. G. Birgin, E. M. Gozzi, M.G.C. Resende and R.M.A. Silva
Journal of Global Optimization Vol. 48 No. 2 (October 2010), Pages 289-310.
Abstract: Global optimization seeks a minimum or maximum of a multimodal function over a discrete or continuous domain. In this paper, we propose a hybrid heuristic -- based on the CGRASP and GENCAN methods -- for finding approximate solutions for continuous global optimization problems subject to box constraints. Experimental results illustrate the relative effectiveness of CGRASP-GENCAN on a set of benchmark multimodal test functions.
Keywords: Global optimization, stochastic methods, active-set methods, heuristic, CGRASP, GENCAN.
Full text: [pdf]
Global minimization using an Augmented Lagrangian method
with variable lower-level constraints
E. G. Birgin, C. A. Floudas and J. M. Martínez
Mathematical Programming Vol. 125 No. 1 (September 2010), Pages 139-162.
Abstract: A novel global optimization method based on an Augmented Lagrangian framework is introduced for continuous constrained nonlinear optimization problems. At each outer iteration the method requires the $\varepsilon$-global minimization of the Augmented Lagrangian with simple constraints. Global convergence to an $\varepsilon$-global minimizer of the original problem is proved. The subproblems are solved using the $\alpha$BB method. Numerical experiments are presented.
Keywords: Deterministic global optimization, Augmented Lagrangians, nonlinear programming, algorithms, numerical experiments.
Using sentinels to detect intersections of convex and nonconvex polygons
W. F. Mascarenhas and E. G. Birgin
Computational & Applied Mathematics Vol. 29 No. 2 (June 2010), Pages 247-267.
Abstract: We describe finite sets of points, called sentinels, which allow us to decide if isometric copies of polygons, convex or not, intersect. As an example of the applicability of the concept of sentinel, we explain how they can be used to formulate an algorithm based on the optimization of differentiable models to pack polygons in convex sets.
Keywords: Sentinels, polygons, intersection, packing, nonlinear programming.
Full text: [pdf]
Second-order negative-curvature methods for box-constrained and general constrained optimization
R. Andreani, E. G. Birgin, J. M. Martínez and M. L. Schuverdt
Computational Optimization and Applications Vol. 45 No. 2 (March 2010), Pages 209-236.
Abstract: A Nonlinear Programming algorithm that converges to second-order stationary points is introduced in this paper. The main tool is a second-order negative-curvature method for box-constrained minimization of a certain class of functions that do not possess continuous second derivatives. This method is used to define an Augmented Lagrangian algorithm of PHR (Powell-Hestenes-Rockafellar) type. Convergence proofs under weak constraint qualifications are given. Numerical examples showing that the new method converge to second-order stationary points in situations in which first-order methods fail are exhibited.
Keywords: Nonlinear programming, Augmented Lagrangians, global convergence, optimality conditions, second-order conditions, constraint qualifications.
Full text: [pdf]
An effective recursive partitioning approach for the packing of identical rectangles in a rectangle
E. G. Birgin, R. D. Lobato and R. Morabito
Journal of the Operational Research Society Vol. 61 No. 2 (February 2010), Pages 306-320.
Abstract: In this work, we deal with the problem of packing (orthogonally and without overlapping) identical rectangles in a rectangle. This problem appears in different logistics settings, such as the loading of boxes on pallets, the arrangements of pallets in trucks and the stowing of cargo in ships. We present a recursive partitioning approach combining improved versions of a recursive five-block heuristic and an $L$-approach for packing rectangles into larger rectangles and $L$-shaped pieces. The combined approach is able to rapidly find the optimal solutions of all instances of the pallet loading problem sets Cover I and II (more than 50 thousand instances). It is also effective for solving the instances of problem set Cover III (almost 100 thousand instances) and practical examples of a woodpulp stowage problem, if compared to other methods from the literature. Some theoretical results are also discussed and, based on them, efficient computer implementations are introduced. The computer implementation and the data sets are available for benchmark purposes at http://www.ime.usp.br/~egbirgin/packing/.
Keywords: Cutting and packing, manufacturer's pallet loading problem, woodpulp stowage problem, non-guillotine cutting pattern, recursive algorithms.
New and improved results for packing identical unitary radius circles within triangles, rectangles and strips
E. G. Birgin and J. M. Gentil
Computers & Operations Research Vol. 37 No. 7 (July 2010), Pages 1318-1327.
Abstract: The focus of study in this paper is the class of packing problems. More specifically, it deals with the placement of a set of N circular items of unitary radius inside an object with the aim of minimizing its dimensions. Differently shaped containers are considered, namely circles, squares, rectangles, strips and triangles. By means of the resolution of nonlinear equations systems through the Newton-Raphson method, the herein presented algorithm succeeds in improving the accuracy of previous results attained by continuous optimization approaches up to numerical machine precision. The computer implementation and the data sets are available at http://www.ime.usp.br/~egbirgin/packing/.
Keywords: Packing, nonlinear equations system, Newton's method, nonlinear programming.
Full text: [pdf]
Partial Spectral Projected Gradient Method with Active-Set Strategy for Linearly Constrained Optimization
M. Andretta, E. G. Birgin and J. M. Martínez
Numerical Algorithms, Vol. 53 No. 1 (January 2010), Pages 23-52.
Abstract: A method for linearly constrained optimization which modifies and generalizes recent box-constraint optimization algorithms is introduced. The new algorithm is based on a relaxed form of Spectral Projected Gradient iterations. Intercalated with these projected steps, internal iterations restricted to faces of the polytope are performed, which enhance the efficiency of the algorithms. Convergence proofs are given and numerical experiments are included and commented. Software supporting this paper is available through the TANGO Project web page.
Keywords: Linearly constrained optimization, spectral projected gradient method, active set methods.
Full text: [pdf]
PACKMOL: A package for building initial configurations for molecular dynamics simulations
L. Martínez, R. Andrade, E. G. Birgin and J. M. Martínez
Journal of Computational Chemistry, Vol. 30 No. 13 (October 2009), Pages 2157-2164.
Abstract: Adequate initial configurations for molecular dynamics simulations consist of arrangements of molecules distributed in space in such a way to approximately represent the system's overall structure. In order that the simulations are not disrupted by large Van der Waals repulsive interactions, atoms from different molecules must keep safe pairwise distances. Obtaining such a molecular arrangement can be considered a packing problem: Each type molecule must satisfy spatial constraints related to the geometry of the system, and the distance between atoms of different molecules must be greater than some specified tolerance. We have developed a code able to pack millions of atoms, grouped in arbitrarily complex molecules, inside a variety of three-dimensional regions. The regions may be intersections of spheres, ellipses, cylinders, planes or boxes. The user must provide only the structure of one molecule of each type and the geometrical constraints that each type of molecule must satisfy. Building complex mixtures, interfaces, solvating biomolecules in water or other solvents, or mixtures of solvents is straightforward. In addition, different atoms belonging to the same molecule may also be restricted to different spacial regions, in such a way that more ordered molecular arrangements can be built, as micelles, lipid double-layers, etc. The packing time for state-of-the-art molecular dynamics systems varies from a few seconds to a few minutes in a personal computer. The input files are simple and currently compatible with PDB, Tinker, Molden or Moldy coordinate files. The package is distributed as free software and can be downloaded from http://www.ime.unicamp.br/~martinez/packmol/.
Keywords: Initial configuration, molecular dynamics, packing, large-scale optimization, PACKMOL.
Full text: [pdf]
Estimation of the thickness and the optical parameters of several superimposed thin films using optimization
R. Andrade, E. G. Birgin, I. Chambouleyron, J. M. Martínez and S. D. Ventura
Applied Optics, Vol. 47 No. 28 (October 2008), Pages 5208-5220.
Abstract: The Reverse Engineering problem addressed in the present research consists in estimating the thicknesses and the optical parameters of two thin films deposited on a transparent substrate using only transmittance data through the whole stack. To the present author's knowledge this is the first report on the retrieval of the optical constants and the thickness of multiple film structures using transmittance data only. The same methodology may be used if the available data correspond to normal reflectance. The software used in this work is freely available through the PUMA Project web page (http://www.ime.usp.br/~egbirgin/puma/).
Keywords: Optical constants, thin films, optimization, numerical algorithms, Reverse Engineering.
Improving ultimate convergence of an Augmented Lagrangian method
E. G. Birgin and J. M. Martínez
Optimization Methods and Software, Vol. 23 No. 2 (April 2008), Pages 177-195.
Abstract: Optimization methods that employ the classical Powell-Hestenes-Rockafellar Augmented Lagrangian are useful tools for solving Nonlinear Programming problems. Their reputation decreased in the last ten years due to the comparative success of Interior-Point Newtonian algorithms, which are asymptotically faster. In the present research a combination of both approaches is evaluated. The idea is to produce a competitive method, being more robust and efficient than its "pure" counterparts for critical problems. Moreover, an additional hybrid algorithm is defined, in which the Interior Point method is replaced by the Newtonian resolution of a KKT system identified by the Augmented Lagrangian algorithm. The software used in this work is freely available through the TANGO Project web page.
Keywords: Nonlinear programming, Augmented Lagrangian methods, Interior-Point methods, Newton's method, experiments.
Structured minimal-memory inexact quasi-Newton method and secant preconditioners for Augmented Lagrangian Optimization
E. G. Birgin and J. M. Martínez
Computational Optimization and Applications, Vol. 39 No. 1 (January 2008), Pages 1-16.
Abstract: Augmented Lagrangian methods for large-scale optimization usually require efficient algorithms for minimization with box constraints. On the other hand, active-set box-constraint methods employ unconstrained optimization algorithms for minimization inside the faces of the box. Several approaches may be employed for computing internal search directions in the large-scale case. In this paper a minimal-memory quasi-Newton approach with secant preconditioners is proposed, taking into account the structure of Augmented Lagrangians that come from the popular Powell-Hestenes-Rockafellar scheme. A combined algorithm, that uses the quasi-Newton formula or a truncated-Newton procedure, depending of the presence of active constraints in the penalty-Lagrangian function, is also suggested. Numerical experiments using the CUTE collection are presented.
Keywords: Nonlinear programming, Augmented Lagrangian methods, box constraints, quasi-Newton, truncated-Newton.
Minimizing the object dimensions in circle and sphere packing problems
E. G. Birgin and F. N. C. Sobral
Computers & Operations Research, Vol. 35 No. 7 (July 2008), Pages 2357-2375.
Abstract: Given a fixed set of identical or different-sized circular items, the problem we deal with consists on finding the smallest object within which the items can be packed. Circular, triangular, squared, rectangular and also strip objects are considered. Moreover, 2D and 3D problems are treated. Twice-differentiable models for all these problems are presented. A strategy to reduce the complexity of evaluating the models is employed and, as a consequence, instances with a large number of items can be considered. Numerical experiments show the flexibility and reliability of the new unified approach.
Keywords: Packing of circles and spheres, models, algorithms, nonlinear programming.
Augmented Lagrangian methods under the Constant Positive Linear Dependence constraint qualification
R. Andreani, E. G. Birgin, J. M. Martínez and M. L. Schuverdt
Mathematical Programming, Vol. 111 No. 1-2 (January 2008), Pages 5-32.
Abstract: Two Augmented Lagrangian algorithms for solving KKT systems are introduced. The algorithms differ in the way in which penalty parameters are updated. Possibly infeasible accumulation points are characterized. It is proved that feasible limit points that satisfy the Constant Positive Linear Dependence constraint qualification are KKT solutions. Boundedness of the penalty parameters is proved under suitable assumptions. Numerical experiments are presented.
Keywords: Nonlinear programming, Augmented Lagrangian methods, KKT systems, numerical experiments.
On Augmented Lagrangian methods with general lower-level constraints
R. Andreani, E. G. Birgin, J. M. Martínez and M. L. Schuverdt
SIAM Journal on Optimization, Vol. 18 No. 4 (November 2007), Pages 1286-1309.
Abstract: Augmented Lagrangian methods with general lower-level constraints are considered in the present research. These methods are useful when efficient algorithms exist for solving subproblems where the constraints are only of the lower-level type. Two methods of this class are introduced and analyzed. Inexact resolution of the lower-level constrained subproblems is considered. Global convergence is proved using the Constant Positive Linear Dependence constraint qualification. Conditions for boundedness of the penalty parameters are discussed. The reliability of the approach is tested by means of an exhaustive comparison against Lancelot. All the problems of the Cute collection are used in this comparison. Moreover, the resolution of location problems in which many constraints of the lower-level set are nonlinear is addressed, employing the Spectral Projected Gradient method for solving the subproblems. Problems of this type with more than $3 \times 10^6$ variables and $14 \times 10^6$ constraints are solved in this way, using moderate computer time.
Keywords: Nonlinear programming, Augmented Lagrangian methods, global convergence, constraint qualifications, numerical experiments.
Method of Sentinels for Packing Items within Arbitrary Convex Regions
E. G. Birgin, J. M. Martínez, W. F. Mascarenhas and D. P. Ronconi
Journal of the Operational Research Society, Vol. 57 No. 6 (June 2006), Pages 735-746.
Abstract: A new method is introduced for packing objects in convex regions of the Euclidian n-dimensional space. By means of this approach the packing problem becomes a global finite-dimensional continuous optimization problem. The strategy is based on the new concept of sentinels sets. Sentinels sets are finite subsets of the objects to be packed such that when two objects are superposed at least one sentinel of one object is in the interior of the other. Minimal sets of sentinels are found in simple 2-dimensional cases. Numerical experiments and pictures showing the potentiality of the new technique are presented.
Keywords: Sentinels, packing problems, cutting problems, models, nonlinear programming.
Orthogonal packing of rectangular items within arbitrary convex regions by nonlinear optimization
E. G. Birgin, J. M. Martínez, F. H. Nishihara and D. P. Ronconi
Computers & Operations Research, Vol. 33 No. 12 (December 2006), Pages 3535-3548.
Abstract: The orthogonal packing of rectangular items in an arbitrary convex region is considered in this work. The packing problem is modeled as the problem of deciding for the feasibility or infeasibility of a set of nonlinear equality and inequality constraints. A procedure based on nonlinear programming is introduced and numerical experiments which show that the new procedure is reliable are exhibited.
Keywords: Packing of rectangles, orthogonal packing, feasibility problems, models, nonlinear programming.
Local Convergence of an Inexact-Restoration method and Numerical Experiments
E. G. Birgin and J. M. Martínez
Journal of Optimization Theory and Applications, Vol. 127 No. 2 (November 2005), Pages 229-247.
Abstract: Local convergence of an inexact-restoration method for nonlinear programming is proved. Numerical experiments are performed with the objective of evaluating the behavior of the purely local method against a globally convergent nonlinear-programming algorithm.
Keywords: Inexact-restoration method, nonlinear programming, local convergence, numerical experiments.
See also the Technical Report (extended version of the published article) [pdf] [ps]
A note on an L-approach for solving the manufacturer's pallet loading problem
E. G. Birgin, R. Morabito and F. H. Nishihara
Journal of the Operational Research Society, Vol. 56 No. 12 (December 2005), Pages 1448-1451.
Abstract: An L-approach for packing (l,w)-rectangles into an (L,W)-rectangle was introduced in [L. Lins, S. Lins and R. Morabito, An L-approach for packing (l,w)-rectangles into rectangular and L-shaped pieces, Journal of the Operational Research Society 54, pp. 777-789, 2003]. The authors of that paper conjecture that the L-approach is exact and point out its runtime requirements as the main drawback. In this note it is shown that, by simply using a different data structure, the runtime is considerably reduced in spite of larger (but affordable) memory requirements. This reduction is important for practical purposes since it makes the algorithm much more acceptable for supporting actual decisions in pallet loading. Intensive numerical experiments showing the efficiency and effectiveness of the algorithm are presented.
Keywords: Cutting and packing, pallet and container loading, recursive algorithm, implementation.
Optimization techniques for the estimation of the thickness and the optical parameters of thin films using reflectance data
S. Ventura, E. G. Birgin, J. M. Martínez and I. Chambouleyron
Journal of Applied Physics, Vol. 97 043512 (February 2005).
Abstract: The present work considers the problem of estimating the thickness and the optical constants (extinction coefficient and refractive index) of thin films from the spectrum of normal reflectance R. This is an ill-conditioned highly underdetermined inverse problem. The estimation is done in the spectral range where the film is not opaque. The idea behind the choice of this particular spectral range is to compare the film characteristics retrieved from transmittance T and from reflectance data. In the first part of the paper a compact formula for R is deduced. The approach to deconvolute the R data is to use well known information on the dependence of the optical constants on photon energy of semiconductors and dielectrics and to formulate the estimation as a nonlinear optimization problem. Previous publications of the group on the subject provide guidelines for designing the new procedures. The consistency of the approach is tested with computer generated thin films and also with measured R and T spectral data of an a-Si:H film deposited onto glass. The results on gedanken films and onto a-Si:H indicate a very good agreement between expected and retrieved values.
Keywords: Optical constants, thin films, reflectance, optimization, numerical algorithms.
Practical active-set Euclidian trust-region method with spectral projected gradients for bound-constrained minimization
M. Andretta, E. G. Birgin and J. M. Martínez
Optimization, Vol. 54 No. 3 (June 2005), Pages 305-325.
Abstract: A practical active-set method for bound-constrained minimization is introduced. Within the current face the classical Euclidian trust-region method is employed. Spectral projected gradient directions are used to abandon faces. Numerical results are presented.
Keywords: Bound-constrained optimization, projected gradient, spectral gradient, trust regions.
Numerical comparison of Augmented Lagrangian algorithms for nonconvex problems
E. G. Birgin, R. Castillo and J. M. Martínez
Computational Optimization and Applications, Vol. 31 No. 1 (May 2005), Pages 31-55.
Abstract: Augmented Lagrangian algorithms are very popular tools for solving nonlinear programming problems. At each outer iteration of these methods a simpler optimization problem is solved, for which efficient algorithms can be used, especially when the problems are large. The most famous Augmented Lagrangian algorithm for minimization with inequality constraints is known as Powell-Hestenes-Rockafellar (PHR) method. The main drawback of PHR is that the objective function of the subproblems is not twice continuously differentiable. This is the main motivation for the introduction of many alternative Augmented Lagrangian methods. Most of them have interesting interpretations as proximal point methods for solving the dual problem, when the original nonlinear programming problem is convex. In this paper a numerical comparison between many of these methods is performed using all the suitable problems of the CUTE collection.
Keywords: Nonlinear programming, Augmented Lagrangian methods, inequality constraints, benchmarking, algorithms.
Robust stopping criteria for Dykstra's algorithm
E. G. Birgin and M. Raydan
SIAM Journal on Scientific Computing, Vol. 26 No. 4 (March 2005), Pages 1405-1414.
Abstract: Dykstra's algorithm is a suitable alternating projection scheme for solving the optimization problem of finding the closest point to a given one onto the intersection of a finite number of closed and convex sets. It has been recently used in a wide variety of applications. However, in practice, the commonly used stopping criteria are not robust and could stop the iterative process prematurely at a point that does not solve the optimization problem. In this work we present a counter example to illustrate the weakness of the commonly used criteria, and then we develop full-proof stopping rules. Additional experiments are shown to illustrate the advantages of this new stopping criteria, including their associated computational cost.
Keywords: Convex optimization, alternating projection methods, Dykstra's algorithm, stopping criteria.
Spectral projected gradient and variable metric methods for optimization with linear inequalities
R. Andreani, E. G. Birgin, J. M. Martínez and J. Yuan
IMA Journal of Numerical Analysis, Vol. 25 No. 2 (April 2005), Pages 221-252.
Abstract: A family of variable metric methods for convex constrained optimization was introduced recently by Birgin, Martínez and Raydan. One of the members of this family is the Inexact Spectral Projected Gradient (ISPG) method for minimization with convex constraints. At each iteration of these methods a strictly convex quadratic function with convex constraints must be (inexactly) minimized. In the case of ISPG it was shown that, in some important applications, iterative projection methods can be used for this minimization. In this paper the particular case in which the convex domain is a polytope described by a finite set of linear inequalities is considered. For solving the linearly constrained convex quadratic subproblem a dual approach is adopted, by means of which subproblems become (not necessarily strictly) convex quadratic minimization problems with box constraints. For solving this problem, we use an active-set box-constraint quadratic optimizer with a proximal-point type unconstrained algorithm for minimization within the current faces. Convergence results and numerical experiments are presented.
Keywords: Linearly-constrained optimization, projected gradient, nonmonotone line search, spectral gradient.
Optimizing the Packing of Cylinders into a Rectangular Container: A Nonlinear Approach
E. G. Birgin, J. M. Martínez and D. P. Ronconi
European Journal of Operational Research, Vol. 160 No 1 (January 2005), Pages 19-33.
Abstract: The container loading problem has important industrial and commercial applications. An increase in the number of items in a container leads to a decrease in cost. For this reason the related optimization problem is of economic importance. In this work, a procedure based on a nonlinear decision problem to solve the cylinder packing problem with identical diameters is presented. This formulation is based on the fact that the centers of the cylinders have to be inside the rectangular box defined by the base of the container (a radius far from the frontier) and far from each other at least one diameter. With this basic premise the procedure tries to find the maximum number of cylinder centers that satisfy these restrictions. The continuous nature of the problem is one of the reasons that motivated this study. A comparative study with other methods of the literature is presented and better results are achieved.
Keywords: Cylinder packing, rectangular container, circular container, nonlinear programming, bound-constrained minimization, convex-constrained minimization.
Inexact Spectral Projected Gradient Methods on Convex Sets
E. G. Birgin, J. M. Martínez and M. Raydan
IMA Journal of Numerical Analysis, Vol. 23 No 4 (October 2003), Pages 539-559.
Abstract: A new method is introduced for large scale convex constrained optimization. The general model algorithm involves, at each iteration, the approximate minimization of a convex quadratic on the feasible set of the original problem and global convergence is obtained by means of nonmonotone line searches. A specific algorithm, the Inexact Spectral Projected Gradient method (ISPG), is implemented using inexact projections computed by Dykstra's alternating projection method and generates interior iterates. The ISPG method is a generalization of the Spectral Projected Gradient method (SPG), but can be used when projections are difficult to compute. Numerical results for constrained least-squares rectangular matrix problems are presented.
Keywords: Convex constrained optimization, Projected gradient, nonmonotone line search, spectral gradient, Dykstra's algorithm.
Estimation of optical parameters of very thin films
E. G. Birgin, I. Chambouleyron, J. M. Martínez and S. D. Ventura
Applied Numerical Mathematics, Vol. 47 No 2 (November 2003), Pages 109-119.
Abstract: In recent papers, the problem of estimating the thickness and the optical constants (refractive index and absorption coefficient) of thin films using only transmittance data has been addressed by means of optimization techniques. Models were proposed for solving this problem using linearly constrained optimization and unconstrained optimization. However, the optical parameters of ``very thin'' films could not be recovered with methods that are successful in other situations. Here we introduce an optimization technique that seems to be efficient for recovering the parameters of very thin films.
Keywords: Optical constants, thin films, optimization, numerical algorithms.
Globally convergent inexact quasi-Newton methods for solving nonlinear systems
E. G. Birgin, N. Krejic and J. M. Martínez
Numerical Algorithms, Vol. 32 No 2-4 (April 2003), Pages 249-260.
Abstract: Large scale nonlinear systems of equations can be solved by means of inexact quasi-Newton methods. A global convergence theory is introduced that guarantees that, under reasonable assumptions, the algorithmic sequence converges to a solution of the problem. Under additional standard assumptions, superlinear convergence is preserved.
Keywords: Nonlinear systems, inexact Newton methods, global convergence, superlinear convergence, quasi-Newton methods.
Optimization problems in the estimation or parameters of thin films and the elimination of the influence of the substrate
E. G. Birgin, I. Chambouleyron and J. M. Martínez
Journal of Computational and Applied Mathematics, Vol. 152 No. 1 (March 2003), Pages 35-50.
Abstract: In a recent paper, the authors introduced a method to estimate optical parameters of thin films using transmission data. The associated model assumes that the film is deposited on a completely transparent substrate. It has been observed, however, that small absorption of substrates affect in a nonnegligible way the transmitted energy. The question arises of the reliability of the estimation method to retrieve optical parameters in the presence of substrates of different thicknesses and absorption degrees. In this paper, transmission spectra of thin films deposited on non-transparent substrates are generated and, as a first approximation, the method based on transparent substrates is used to estimate the optical parameters. As expected, the method is good when the absorption of the substrate is very small, but fails when one deals with less transparent substrates. To overcome this drawback, an iterative procedure is introduced, that allows one to approximate the transmittance with transparent substrate, given the transmittance with absorbent substrate. The updated method turns out to be almost as efficient in the case of absorbent substrates as it was in the case of transparent ones.
Keywords: Optimization, estimation of parameters, unconstrained minimization, constrained optimization, thin films, optical constants, transmittance.
Solution of bounded nonlinear systems of equations using homotopies with inexact restoration
E. G. Birgin, N. Krejic and J. M. Martínez
International Journal of Computer Mathematics, Vol. 80 No. 2 (February 2003), Pages 211-222.
Abstract: Nonlinear systems of equations often represent mathematical models of chemical production processes and other engineering problems. Homotopic techniques (in particular, the bounded homotopies introduced by Paloschi) are used for enhancing convergence to solutions, especially when a good initial estimate is not available. In this paper, the homotopy curve is considered as the feasible set of a mathematical programming problem, where the objective is to find the optimal value of the homotopic parameter. Inexact restoration techniques can then be used to generate approximations in a neighborhood of the homotopy, the size of which is theoretically justified. Numerical examples are given.
Keywords: Nonlinear programming, nonlinear systems, homotopies, bounded homotopies, homotopy methods, inexact restoration.
Minimization subproblems and heuristics for an applied clustering problem
E. G. Birgin, J.M. Martínez and D. P. Ronconi
European Journal of Operational Research, Vol. 146 No. 1 (April 1, 2003), Pages 19-34.
Abstract: A practical problem that requires the classification of a set of points of Rn using a criterion not sensitive to bounded outliers is studied in this paper. A fixed-point (k-means) algorithm is defined that uses an arbitrary distance function. Finite convergence is proved. A robust distance defined by Boente, Fraiman and Yohai is selected for applications. Smooth approximations of this distance are defined and suitable heuristics are introduced to enhance the probability of finding global optimizers. A real-life example is presented and commented.
Keywords: Nonlinear programming, heuristics, clustering, classification, fixed points.
Optical constants and thickness determination of very thin amorphous semiconductor films
I. Chambouleyron, S. D. Ventura, E. G. Birgin and J. M. Martínez,
Journal of Applied Physics, Vol. 92 No. 6 (September 15, 2002), Pages 3093-3102.
Abstract: This contribution addresses the relevant question of retrieving, from transmittance data, the optical constants and thickness of very thin semiconductor and dielectric films. The retrieval process looks for a thickness that, subject to the physical input of the problem, minimizes the difference between the measured and the theoretical spectra. This is a highly underdetermined problem but, the use of approximate - though simple - functional dependences of the index of refraction and of the absorption coefficient on photon energy, used as an a priori information, allows surmounting the ill-posedness of the problem. The method is illustrated with the analysis of transmittance data of very thin amorphous silicon films. The method allows retrieving physically meaningful solutions for films as thin as 300 A. The estimated parameters agree well with known data or with optical parameters measured by independent methods. The limitations of the adopted model and the shortcomings of the optimization algorithm are presented and discussed.
Keywords: Optical constants, thin films, optimization, numerical algorithms.
Large-scale active-set box-constrained optimization method with spectral projected gradients
E. G. Birgin and J. M. Martínez
Computational Optimization and Applications, Vol. 23 No. 1 (October 2002), Pages 101-125.
Abstract: A new active-set method for smooth box-constrained minimization is introduced. The algorithm combines an unconstrained method, including a new line-search which aims to add many constraints to the working set at a single iteration, with a recently introduced technique (spectral projected gradient) for dropping constraints from the working set. Global convergence is proved. A computer implementation is fully described and a numerical comparison assesses the reliability of the new algorithm.
Keywords: Box-constrained minimization, numerical methods, active-set strategies, Spectral Projected Gradient.
Algorithm 813: SPG - software for convex-constrained optimization
E. G. Birgin, J. M. Martínez and M. Raydan
ACM Transactions on Mathematical Software, Vol. 27 No. 3 (September 2001), Pages 340-349.
Abstract: A Fortran 77 software which implements the SPG method is introduced. SPG is a nonmonotone projected gradient algorithm for solving large-scale convex-constrained optimization problems. It combines the classical projected gradient method with the spectral gradient choice of steplength and a nonmonotone line search strategy. Implementation details are presented and the usage of the software is described. Some new numerical tests that have been recently performed are reported. The main conclusion is that SPG compares favorably with existing software.
Keywords: Projected gradients, nonmonotone line search, large-scale problems, bound constrained problems, spectral gradient method.
A box-constrained optimization algorithm with negative curvature directions and spectral projected gradients
E. G. Birgin and J. M. Martínez
Computing [Suppl], Vol. 15 (2001), Pages 49-60.
Abstract: A practical algorithm for box-constrained optimization is introduced. The algorithm combines an active-set strategy with spectral projected gradient iterations. In the interior of each face a strategy that deals efficiently with negative curvature is employed. Global convergence results are given. Numerical results are presented.
Keywords: Box constrained minimization, active set methods, spectral projected gradients, dogleg path methods.
A Spectral Conjugate Gradient method for unconstrained optimization
E. G. Birgin and J. M. Martínez
Applied Mathematics and Optimization, Vol. 43 No. 2 (2001), Pages 117-118.
Abstract: A family of scaled conjugate-gradient algorithms for large-scale unconstrained minimization is defined. The Perry, the Polak-Ribièere and the Fletcher-Reeves formulae are compared using a spectral scaling derived from Raydan's spectral gradient optimization method. The best combination of formula, scaling and initial choice of step-length is compared against well known algorithms using a classical set of problems. An additional comparison involving an ill-conditioned estimation problem in Optics is presented.
Keywords: Unconstrained minimization, spectral gradient method, conjugate gradients.
Determination of thickness and optical constants of a-Si:H films from transmittance data
M. Mulato, I. Chambouleyron, E. G. Birgin and J. M. Martínez
Applied Physics Letters, Vol. 77 No. 14 (2000), Pages 2133-2135.
Abstract: This work presents the first application of a recently developed numerical method to determine the thickness and the optical constants of thin films using experimental transmittance data only. The new method may be applied to films not displaying a fringe pattern and is shown to work for a-Si:H layers as thin as 100 nm. The performance and limitations of the method are discussed on the basis of experiments performed on a series of six a-Si:H samples grown under identical conditions, but with thickness varying from 98 nm to 1.2 mu m.
Keywords: Thin films, optical constants, a-Si:H films, unconstrained minimization.
Nonmonotone Spectral Projected Gradient Methods on Convex Sets
E. G. Birgin, J. M. Martínez and M. Raydan
SIAM Journal on Optimization, Vol. 10 No. 4 (2000), Pages 1196-1211.
Abstract: Nonmonotone projected gradient techniques are considered for the minimization of differentiable functions on closed convex sets. The classical projected gradient schemes are extended to include a nonmonotone steplength strategy that is based on the Grippo-Lampariello-Lucidi nonmonotone line search. In particular, the nonmonotone strategy is combined with the spectral gradient choice of steplength to accelerate the convergence process. In addition to the classical projected gradient nonlinear path, the feasible spectral projected gradient is used as a search direction to avoid additional trial projections during the one-dimensional search process. Convergence properties and extensive numerical results are presented.
Keywords: Projected gradients, nonmonotone line search, large scale problems, bound constrained problems, spectral gradient method.
Restricted optimization: a clue to a fast and accurate implementation of the Common Reflection Surface Stack method
E. G. Birgin, R. Biloti, M. Tygel and L. T. Santos
Journal of Applied Geophysics, Vol. 42 No. 3-4 (December 1999), Pages 143-155.
Abstract: For a fixed, central ray in an isotropic elastic or acoustic media, traveltime moveouts of rays in its vicinity can be described in terms of a certain number of parameters that refer to the central ray only. The determination of these parameters out of multi-coverage data leads to very powerful algorithms that can be used for several imaging and inversion processes. Assuming two-dimensional propagation, the traveltime expressions depend on three parameters directly related to the geometry of the unknown model in the vicinity of the central ray. We present a new method to extract these parameters out of coherency analysis applied directly to the data. It uses (a) fast one-parameter searches on different sections extracted from the multi-coverage data to derive initial values of the sections parameters, and (b) the application of a recently introduced Spectral Projected Gradient optimization algorithm for the final parameter estimation. Application of the method on a synthetic example shows an excellent performance of the algorithm both in accuracy and efficiency. The results obtained so far indicate that the algorithm may be a feasible option to solve the corresponding, harder, full three-dimensional problem, in which eight parameters, instead of three, are required.
Keywords: Multi-coverage data, Common Reflection Surface method, hyperbolic traveltime, coherency function, optimization, Spectral Projected Gradient method.
Estimation of the optical constants and the thickness of thin films using unconstrained optimization
E. G. Birgin, I. Chambouleyron and J. M. Martínez
Journal of Computational Physics, Vol. 151, No. 2 (May 1999), Pages 862-880.
Abstract: The problem of estimating the thickness and the optical constants of thin films using transmission data only is very challenging from the mathematical point of view, and has a technological and an economic importance. In many cases it represents a very ill-conditioned inverse problem with many local-nonglobal solutions. In a recent publication we proposed nonlinear programming models for solving this problem.Well-known software for linearly constrained optimization was used with success for this purpose. In this paper we introduce an unconstrained formulation of the nonlinear programming model and we solve the estimation problem using a method based on repeated calls to a recently introduced unconstrained minimization algorithm. Numerical experiments on computer-generated films show that the new procedure is reliable.
Keywords: Unconstrained minimization, spectral gradient method, optical constants, thin films.
Automatic differentiation for optimal control problems
E. G. Birgin and Y. G. Evtushenko
in Dynamics of Non-homogeneous System, edited by Y. S. Popkov, Proceedings of ISA RAS, Institute of System Analysis of the Russian Academy of Science, Moscow, Vol. 2 (1999), Pages 53-62.
Abstract: Automatic differentiation is used for the solution of optimal control problems. The original problem is reduced to a nonlinear programming problem using general Runge-Kutta integration formulas. Canonical formulas which use a fast automatic differentiation strategy are given to compute derivatives of the goal function.
Keywords: Automatic differentiation, optimal control problem, Runge-Kutta integration methods.
Automatic differentiation and Spectral Projected Gradient methods for optimal control problems
E. G. Birgin and Y. G. Evtushenko
Optimization Methods & Software, Vol. 10 No. 2 (December 1998), Pages 125-146.
Abstract: Automatic differentiation and nonmonotone spectral projected gradient techniques are used for solving optimal control problems. The original problem is reduced to a nonlinear programming one using general Runge-Kutta integration formulas. Canonical formulas which use a fast automatic differentiation strategy are given to compute derivatives of the objective function. On the basis of this approach, codes for solving optimal control problems are developed and some numerical results are presented.
Keywords: Automatic differentiation, Spectral Projected Gradient, nonmonotone line search, optimal control problem, software for optimal control problems, Runge-Kutta integration methods.