Mixed Integer Linear Programming and Constraint Programming Models for the Online Printing Shop Scheduling Problem

W. T. Lunardi, E. G. Birgin, P. Laborie, D. P. Ronconi, and H. Voos

Submitted.

Abstract: In this work, the online printing shop scheduling problem is considered. The problem, that appears in the nowadays printing industry, can be seen as an extended flexible job shop scheduling problem with several particularities such as operations' release times, operations' precedence constraints given by an arbitrary acyclic graph, partial overlapping among operations with precedence constraints, sequence-dependent setup times, fixed operations, and machines' unavailability periods. In the present work, mixed integer programming and constraint programming models for the minimization of the makespan are presented. Modeling the problem is twofold. On the one hand, the problem is precisely defined. On the other hand, small- and medium-sized instances are optimally solved. Extensive numerical experiments show the capabilities and limitations of a commercial software for solving the models.

Keywords: Flexible job shop scheduling, Mixed integer linear programming, Constraint programming.

Full text: [pdf]

On the solution of linearly constrained optimization problems by means of barrier algorithms

E. G. Birgin, J. L. Gardenghi, J. M. Martínez, and S. A. Santos

Submitted.

Abstract: Many practical problems require the solution of large-scale constrained optimization problems for which preserving feasibility is a key issue and the evaluation of the objective function is very expensive. In these cases it is mandatory to start with a feasible approximation of the solution, the obtention of which should not require objective function evaluations. The necessity of solving this type of problems motivated us to revisit the classical barrier approach for nonlinear optimization, providing a careful implementation of a modern version of this method. This is the main objective of the present paper. For completeness, we provide global convergence results and comparative numerical experiments with one of the state-of-the-art interior-point solvers for continuous optimization.

Keywords: Linearly constrained optimization, feasible barrier methods, convergence, numerical experiments.

Full text: [pdf]

On constrained optimization with nonconvex regularization

E. G. Birgin, J. M. Martínez, and A. Ramos

Submitted.

Abstract: In many engineering applications it is necessary to minimize smooth functions plus penalty (or regularization) terms that violate smoothness and convexity. Specific algorithms for this type of problems are available in recent literature. Here a smooth reformulation is proposed and equivalence with the original problem is proved both from the point of view of global and local optimization. Moreover, for the cases in which the objective function is much more expensive than the constraints, model-intensive algorithms, accompanied by their convergence and complexity theories, are introduced. Finally, numerical experiments are presented.

Keywords: Constrained non-Lipschitz nonsmooth optimization, complexity analysis, optimality conditions.

Full text: [pdf]

Complexity and performance of an Augmented Lagrangian algorithm

E. G. Birgin and J. M. Martínez

Submitted.

Abstract: Algencan is a well established safeguarded Augmented Lagrangian algorithm introduced in [R. Andreani, E. G. Birgin, J. M. Martínez and M. L. Schuverdt, On Augmented Lagrangian methods with general lower-level constraints, SIAM Journal on Optimization 18, pp. 1286-1309, 2008]. Complexity results that report its worst-case behavior in terms of iterations and evaluations of functions and derivatives that are necessary to obtain suitable stopping criteria are presented in this work. In addition, the computational performance of a new version of the method is presented, which shows that the updated software is a useful tool for solving large-scale constrained optimization problems.

Keywords: Nonlinear programming, Augmented Lagrangian methods, complexity, numerical experiments.

Full text: [pdf]

On the complexity of solving feasibility problems with quadratically regularized models

E. G. Birgin, L. F. Bueno, and J. M. Martínez

Submitted.

Abstract: The complexity of solving feasibility problems is considered in this work. It is assumed that the constraints that define the problem can be divided into two sets, namely, expensive and cheap constraints. It is also assumed that the set of solutions of the cheap constraints is non-empty and bounded and that minimizing a quadratic function subject to the cheap constraints is an affordable task. At each iteration, the introduced method minimizes a two-norm regularized quadratic approximation of the sum of squares of the expensive constraints subject to the cheap constraints. Under a H\"older continuity property with constant $\beta \in (0,1]$ on the gradients of the expensive constraints, it is shown that finding a feasible point with precision~$\varepsilon > 0$ or an infeasible point that is stationary with tolerance~$\gamma > 0$ of minimizing the Euclidean norm of the expensive constraints residual subject to the cheap constraints has iterations complexity~$O\left(|\log(\varepsilon)| \; \gamma^{-(1+\beta)/\beta} \; \varepsilon^{(\beta-1)/(2\beta)}\right)$ and evaluations complexity (of the expensive constraints) $O\left(|\log(\varepsilon)|\left[ \gamma^{-(1+\beta)/\beta} \varepsilon^{(\beta-1)/(2\beta)}+ ((1-\beta)/\beta) | \log(\gamma \sqrt{\varepsilon})| \right] \right)$. When the gradients of the expensive constraints satisfy a Lipschitz condition, both complexities reduce to $O(|\log(\varepsilon)| \gamma^{-2})$. Still under the H\"older continuity property on the gradients of the expensive constraints, and under a stronger regularity assumption with constant~$\kappa$, that avoids KKT points of minimizing the sum of squares of the expensive constraints subject to the cheap constraints of being infeasible, the iterations complexity is shown to be $O\left(|\log(\varepsilon)| \; \kappa^{-(1+\beta)/\beta} \; \varepsilon^{(\beta-1)/(2\beta)}\right)$ while the evaluation complexity is given by $O\left(|\log(\varepsilon)|\left[ \kappa^{-(1+\beta)/\beta} \varepsilon^{(\beta-1)/(2\beta)}+ ((1-\beta)/\beta) |\log(\kappa \sqrt{\varepsilon})| \right] \right)$. When the gradients of the expensive constraints satisfy a Lipschitz condition, both complexities reduce to $O(|\log(\varepsilon)| \kappa^{-2})$. The results introduced in the present work complement, by analyzing the case $p=1$, the results obtained for $p$ even in [C. Cartis, N. I. M. Gould, and Ph. L. Toint, Improved worst-case evaluation complexity for potentially rank-deficient nonlinear least-Euclidean-norm problems using higher-order regularized models, Technical Report NA 15-17, University of Oxford, 2015], where~$p$ is the order of the underlying $(p+1)$-regularized Taylor's model of the sum of squares of the expensive constraints.

Keywords: Complexity, feasibility problem, first order methods.

Full text: [pdf]

An Augmented Lagrangian algorithm for nonlinear semidefinite programming applied to the covering problem

E. G. Birgin, W. Gómez, G. Haeser, L. M. Mito, and D. S. Viana

Computational and Applied Mathematics, to appear.

Abstract: In this work we present an Augmented Lagrangian algorithm for nonlinear semidefinite problems (NLSDPs), which is a natural extension of its consolidated counterpart in nonlinear programming. This method works with two levels of constraints; one that is penalized and other that is kept within the subproblems. This is done in order to allow exploiting the subproblem structure while solving it. The global convergence theory is based on recent results regarding approximate Karush-Kuhn-Tucker optimality conditions for NLSDPs, which are stronger than the usually employed Fritz John optimality conditions. Additionally, we approach the problem of covering a given object with a fixed number of balls with a minimum radius, where we exploit some convex algebraic geometry tools, such as Stengle's Positivstellensatz and its variations, which allows for a much more general model. Preliminary numerical experiments are presented.

Keywords: Augmented Lagrangian, Nonlinear Semidefinite Programming, Covering Problem, Convex Algebraic Geometry.

Full text: [pdf]

A filtered beam search method for the m-machine permutation flowshop scheduling problem minimizing the earliness and tardiness penalties and the waiting time of the jobs

E. G. Birgin, J. E. Ferreira, and D. P. Ronconi

Computers & Operations Research, to appear.

Abstract: This paper addresses the minimization of the absolute deviation of job completion times from a common due date in a flowshop scheduling problem. Besides this main objective, the minimization of the waiting time of the jobs in the production environment is also considered. Initially, a mixed integer programming model for this problem is proposed and, due to its complexity, heuristic approaches are developed. A list-scheduling algorithm for the approached problem is introduced. Moreover, a filtered beam search method that explores specific characteristics of the considered environment is proposed. Numerical experiments show that the presented methods can be successfully applied to this problem.

Keywords: Scheduling, flowshop, earliness and tardiness, common due date, waiting time, heuristics, beam search.

Full text: [pdf]

The multiperiod two-dimensional non-guillotine cutting stock problem with usable leftovers

E. G. Birgin, O. C. Romão, and D. P. Ronconi

International Transactions in Operational Research, to appear.

Abstract: A mixed integer linear programming model for the two-dimensional non-guillotine cutting problem with usable leftovers was recently introduced in Andrade et al. [Journal of the Operational Research Society 65, pp. 1649-1663, 2014]. The problem consists in cutting a set of ordered items using a set of objects of minimum cost and, within the set of solutions of minimum cost, maximizing the value of the usable leftovers. Since the concept of usable leftovers assumes they can potentially be used to attend new arriving orders, the problem is extended to the multiperiod framework in this work. In this way, the decision at each instant does not minimize in a myopic way the cost of the objects required to attend the orders of the current instant; but it aims to minimize the overall cost of the objects up to the considered time horizon. Some variants of the proposed model are analyzed and numerical results are presented.

Keywords: Two-dimensional cutting with usable leftovers, MIP models, non-guillotine cutting and packing, multiperiod scenario.

Full text: [pdf]

On the use of third-order models with fourth-order regularization for unconstrained optimization

E. G. Birgin, J. L. Gardenghi, J. M. Martínez, and S. A. Santos

Optimization Letters, to appear.

Abstract: In a recent paper [E. G. Birgin, J. L. Gardenghi, J. M. Martínez, S. A. Santos, and Ph. L. Toint, Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models, Mathematical Programming 163(1), 359-368, 2017], it was shown that, for the smooth unconstrained optimization problem, worst-case evaluation complexity $O(\epsilon^{-(p+1)/p})$ may be obtained by means of algorithms that employ sequential approximate minimizations of $p$-th order Taylor models plus $(p+1)$-th order regularization terms. The aforementioned result, which assumes Lipschitz continuity of the $p$-th partial derivatives, generalizes the case $p=2$, known since 2006, which has already motivated efficient implementations. The present paper addresses the issue of defining a reliable algorithm for the case $p=3$. With that purpose, we propose a specific algorithm and we show numerical experiments.

Keywords: Unconstrained minimization, third-order models, regularization, complexity.

Full text: [pdf]

Models for the two-dimensional rectangular single large placement problem with guillotine cuts and constrained pattern

M. P. Martins, E. G. Birgin, R. D. Lobato, R. Morabito, and P. Munari

International Transactions in Operational Research Vol. 27 No. 2 (March 2020), pages 767-793.

Abstract: In this paper, we address the Constrained Two-dimensional Rectangular Guillotine Single Large Placement Problem (2D R CG SLOPP). This problem involves cutting a rectangular object to produce smaller rectangular items from orthogonal guillotine cuts.In addition, there is an upper limit on the number of copies that can be produced of each item type. To model this problem, we propose a new compact integer non-linear programming (INLP) formulation and obtain an equivalent integer linear programming (ILP) formulation from it. Additionally, we developed a procedure to reduce the numbers of variables and constraints of the ILP formulation, without loss of optimality. From the ILP formulation, we derive two new compact models for particular cases of the 2D R CG SLOPP, which consider only 2-staged or 1-group patterns. Finally, as a specific solution method for the 2D R CG SLOPP, we apply Benders decomposition to the proposed ILP formulation and develop a branch-and-Benders-cut algorithm. All proposed approaches are evaluated through computational experiments using benchmark instances and compared with other formulations available in the literature. The results show that the new formulations are appropriate in scenarios characterized by few item types that are large with respect to the objecti's dimensions.

Keywords: Cutting and packing problems, Constrained two-dimensional guillotine cuts, Integer programming models, branch-and-Benders-cut algorithm.

Full text: [pdf]

Iteration and evaluation complexity for the minimization of functions whose computation is intrinsically inexact

E. G. Birgin, N. Krejic, and J. M. Martínez

Mathematics of Computations Vol. 89 No. 321 (January 2020), pages 253-278.

Abstract: In many cases in which one wishes to minimize a complicated or expensive function, it is convenient to employ cheap approximations, at least when the current approximation to the solution is far from the solution. Adequate strategies for deciding the accuracy desired at each stage of optimization are crucial for the global convergence and overall efficiency of the process. A recently introduced procedure [E. G. Birgin, N. Krejić, and J. M. Martínez, On the employment of Inexact Restoration for the minimization of functions whose evaluation is subject to errors, Mathematics of Computation 87, pp. 1307-1326, 2018] based on Inexact Restoration is revisited, modified, and analyzed from the point of view of worst-case evaluation complexity in this work.

Keywords: Inexact Restoration, global convergence, worst-case evaluation complexity.

Full text: [pdf]

A Newton-like method with mixed factorizations and cubic regularization for unconstrained minimization

E. G. Birgin and J. M. Martínez

Computational Optimization and Applications Vol. 73 No. 3 (July 2019), pages 707-753.

Abstract: A Newton-like method for unconstrained minimization is introduced in the present work. While the computer work per iteration of the best-known implementations may need several factorizations per iteration or may use rather expensive matrix decompositions, the proposed method uses a single cheap factorization per iteration. Convergence and complexity and results, even in the case in which the subproblems' Hessians are far from being Hessians of the objective function, are presented. Moreover, when the Hessian is Lipschitz-continuous, the proposed method enjoys $O(\varepsilon^{-3/2})$ evaluation complexity for first-order optimality and $O(\varepsilon^{-3})$ for second-order optimality as other recently introduced Newton method for unconstrained optimization based on cubic regularization or special trust-region procedures. Fairly successful and fully reproducible numerical experiments are presented and the developed corresponding software is freely available.

Keywords: Smooth unconstrained minimization, Bunch-Parlett-Kaufman factorizations, regularization, Newton-type methods.

Full text: [pdf]

A matheuristic approach with nonlinear subproblems for large-scale packing of ellipsoids

E. G. Birgin and R. D. Lobato

European Journal of Operational Research Vol 272 No. 2 (January 2019), pages 447-464.

Abstract: The problem of packing ellipsoids in the three-dimensional space is considered in the present work. The proposed approach combines heuristic techniques with the resolution of recently introduced nonlinear programming models in order to construct solutions with a large number of ellipsoids. The introduced approach is able to pack identical and non-identical ellipsoids within a variety of containers. Moreover, it allows the inclusion of additional positioning constraints. This fact makes the proposed approach suitable for constructing large-scale solutions with specific positioning constraints in which density may not be the main issue. Numerical experiments illustrate that the introduced approach delivers good quality solutions with a computational cost that scales linearly with the number of ellipsoids; and solutions with more than a million ellipsoids are exhibited.

Keywords: Packing, ellipsoids, nonlinear programming, algorithms, matheuristic.

Full text: [pdf]

On regularization and active-set methods with complexity for constrained optimization

E. G. Birgin and J. M. Martínez

SIAM Journal on Optimization Vol 28 No. 2 (May 2018), pages 1367-1395.

Abstract: The main objective of this research is to introduce a practical method for smooth bound-constrained optimization that possesses worst-case evaluation complexity $O(\varepsilon^{-3/2})$ for finding an $\varepsilon$-approximate first-order stationary point when the Hessian of the objective function is Lipschitz-continuous. As other well established algorithms for optimization with box constraints, the algorithm proceeds visiting the different faces of the domain aiming to reduce the norm of an internal projected gradient and abandoning active constraints when no additional progress is expected in the current face. The introduced method emerges as a particular case of a method for minimization with linear constraints. Moreover, the linearly-constrained minimization algorithm is an instance of a minimization algorithm with general constraints whose implementation may be unaffordable when the constraints are complicated. As a procedure for leaving faces, it is employed a different method that may be regarded as an independent device for constrained optimization. Such independent algorithm may be employed to solve linearly-constrained optimization problem on its own, without relying on the active-set strategy. A careful implementation and numerical experiments shows that the algorithm that combines active sets with leaving-face iterations is more effective than the independent algorithm on which leaving-face iterations are based, although both exhibits similar complexities $O(\varepsilon^{-3/2})$.

Keywords: Nonlinear programming, bound-constrained minimization, active-set strategies, regularization, complexity.

Full text: [pdf]

On the employment of Inexact Restoration for the minimization of functions whose evaluation is subject to errors

E. G. Birgin, N. Krejic, and J. M. Martínez

Mathematics of Computation Vol. 87 No. 311 (May 2018), pages 1307-1326.

Abstract: Inexact Restoration is a well established technique for continuous minimization problems with constraints. Recently, it has been used by Krejic and Martínez for optimization of functions whose evaluation is necessarily inexact and comes from an iterative process. This technique will be generalized in the present paper and it will be applied to stochastic optimization and related problems. New convergence results will be given and numerical results will be presented.

Keywords: Inexact Restoration, stochastic programming, global convergence, numerical experiments.

Full text: [pdf]

Augmented Lagrangians with constrained subproblems and convergence to second-order stationary points

E. G. Birgin, G. Haeser, and A. Ramos

Computational Optimization and Applications Vol. 69 No. 1 (January 2018), pages 51-75.

Abstract: Augmented Lagrangian methods with convergence to second-order stationary points in which any constraint can be penalized or carried out to the subproblems are considered in this work. The resolution of each subproblem can be done by any numerical algorithm able to return approximate second-order stationary points. The developed global convergence theory is stronger than the ones known for current algorithms with convergence to second-order points in the sense that, besides the flexibility introduced by the general lower-level approach, it includes a loose requirement for the resolution of subproblems. The proposed approach relies on a weak constraint qualification, that allows Lagrange multipliers to be unbounded at the solution. It is also shown that second-order resolution of subproblems increases the chances of finding a feasible point, in the sense that limit points are second-order stationary for the problem of minimizing the squared infeasibility. The applicability of the proposed method is illustrated in numerical examples with ball-constrained subproblems.

Keywords: Augmented Lagrangian methods, nonlinear programming, second-order stationary points, algorithms.

Full text: [pdf]

On the minimization of possibly discontinuous functions by means of pointwise approximations

E. G. Birgin, N. Krejic, and J. M. Martínez

Optimization Letters Vol. 11 No. 8 (December 2017), pages 1623-1637.

Abstract: A general approach for the solution of possibly discontinuous optimization problems by means of pointwise (perhaps smooth) approximations will be proposed. It will be proved that sequences generated by pointwise approximation techniques eventually satisfy well justified stopping criteria. Numerical examples will be given.

Keywords:Discontinuous functions, pointwise approximations, smoothing, minimization.

Full text: [pdf]

A nonlinear programming model with implicit variables for packing ellipsoids

E. G. Birgin, R. D. Lobato, and J. M. Martínez

Journal of Global Optimization Vol. 68 No. 3 (July 2017), pages 467-499.

Abstract: The problem of packing ellipsoids is considered in the present work. Usually, the computational effort associated with numerical optimization methods devoted to packing ellipsoids grows quadratically with respect to the number of ellipsoids being packed. The reason is that the number of variables and constraints of ellipsoids' packing models is associated with the requirement that every pair of ellipsoids must not overlap. As a consequence, it is hard to solve the problem when the number of ellipsoids is large. In this paper, we present a nonlinear programming model for packing ellipsoids that contains a linear number of variables and constraints. The proposed model finds its basis in a transformation-based non-overlapping model recently introduced by Birgin, Lobato, and Martínez [Journal of Global Optimization (2015), DOI: 10.1007/s10898-015-0395-z]. Numerical experiments show the efficiency and effectiveness of the proposed model.

Keywords: Cutting and packing ellipsoids, optimization, nonlinear programming, models, numerical experiments.

Full text: [pdf]

The use of quadratic regularization with a cubic descent condition for unconstrained optimization

E. G. Birgin and J. M. Martínez

SIAM Journal on Optimization Vol. 27 No. 2 (June 2017), pages 1049-1074.

Abstract: Cubic-regularization and trust-region methods with worst-case first-order complexity $O(\varepsilon^{-3/2})$ and worst-case second-order complexity $O(\varepsilon^{-3})$ have been developed in the last few years. In this paper it is proved that the same complexities are achieved by means of a quadratic-regularization method with a cubic sufficient-descent condition instead of the more usual predicted-reduction based descent. Asymptotic convergence and order of convergence results are also presented. Finally, some numerical experiments comparing the new algorithm with a well-established quadratic regularization method are shown.

Keywords: Nonlinear programming, unconstrained minimization, quadratic regularization, cubic descent, complexity.

Full text: [pdf]

Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models

E. G. Birgin, J. L. Gardenghi, J. M. Martínez, S. A. Santos, and Ph. L. Toint

Mathematical Programming Vol. 163 No. 1 (May 2017), pages 359-368.

Abstract: The worst-case evaluation complexity for smooth (possibly nonconvex) unconstrained optimization is considered. It is shown that, if one is willing to use derivatives of the objective function up to order $p$ (for $p \geq 1$) and to assume Lipschitz continuity of the $p$-th derivative, then an $\epsilon$-approximate first-order critical point can be computed in at most $O(\epsilon^{-(p+1)/p})$ evaluations of the problem's objective function and its derivatives. This generalizes and subsumes results known for $p = 1$ and $p = 2$.

Keywords: Unconstrained minimization, worst-case complexity.

Full text: [pdf]

Sequential equality-constrained optimization for nonlinear programming

E. G. Birgin, L. F. Bueno, and J. M. Martínez

Computational Optimization and Applications Vol. 65 No. 3 (December 2016), pages 699-721.

Abstract: A new method is proposed for solving optimization problems with equality constraints and bounds on the variables. In the spirit of Sequential Quadratic Programming and Sequential Linearly-Constrained Programming, the new method approximately solves, at each iteration, an equality-constrained optimization problem. The bound constraints are handled in outer iterations by means of an Augmented Lagrangian scheme. Global convergence of the method follows from well-established non-linear programming theories. Numerical experiments are presented.

Keywords:Nonlinear programming, Sequential Equality-Constrained Optimization, Augmented Lagrangian, numerical experiments.

Full text: [pdf]

Constrained optimization with integer and continuous variables using inexact restoration and projected gradients

E. G. Birgin, R. D. Lobato, and J. M. Martínez

Bulletin of Computational Applied Mathematics Vol. 4 No. 2 (2016), pages 55-70.

Abstract: Inexact restoration (IR) is a well established technique for continuous minimization prob- lems with constraints that can be applied to constrained optimization problems with specific structures. When some variables are restricted to be integer, an IR strategy seems to be appropriate. The IR strategy employs a restoration procedure in which one solves a standard nonlinear programming problem and an optimization procedure in which the constraints are linearized and techniques for mixed-integer (linear or quadratic) programming can be em- ployed.

Keywords: Inexact restoration, mixed-integer nonlinear programming (MINLP), projected gradients.

Full text: [pdf]

Packing ellipsoids by nonlinear optimization

E. G. Birgin, R. D. Lobato, and J. M. Martínez

Journal of Global Optimization Vol. 65 No. 4 (August 2016), pages 709-743.

Abstract: In this paper, continuous and dierentiable nonlinear programming models and algorithms for packing ellipsoids in the n-dimensional space are introduced. Two dierent models for the non-overlapping and models for the inclusion of ellipsoids within half-spaces and ellipsoids are presented. By applying a simple multi-start strategy combined with a clever choice of starting guesses and a nonlinear programming local solver, illustrative numerical experiments are presented.

Keywords: Cutting and packing ellipsoids, nonlinear programming, models, numerical experiments.

Full text: [pdf]

Evaluation complexity for nonlinear constrained optimization using unscaled KKT conditions and high-order models

E. G. Birgin, J. L. Gardenghi, J. M. Martínez, S. A. Santos, and Ph. L. Toint

SIAM Journal on Optimization Vol. 26 No. 2 (April, 2016), pages 951-967.

Abstract: The evaluation complexity of general nonlinear, possibly nonconvex, constrained optimization is analyzed. It is shown that, under suitable smoothness conditions, an $\epsilon$-approximate first-order critical point of the problem can be computed in order $O(\epsilon^{1-2(p+1)/p})$ evaluations of the problem's function and their first p derivatives. This is achieved by using a two-phases algorithm inspired by Cartis, Gould, and Toint [8, 11]. It is also shown that strong guarantees (in terms of handling degeneracies) on the possible limit points of the sequence of iterates generated by this algorithm can be obtained at the cost of increased complexity. At variance with previous results, the -approximate first-order criticality is defined by satisfying a version of the KKT conditions with an accuracy that does not depend on the size of the Lagrange multipliers.

Keywords: Nonlinear programming, complexity, approximate KKT point.

Full text: [pdf]

On the application of an Augmented Lagrangian algorithm to some portfolio problems

E. G. Birgin and J. M. Martínez

EURO Journal on Computational Optimization Vol. 4 No. 1 (February 2016), pages 79-92.

Abstract: Algencan is a freely available piece of software that aims to solve smooth large-scale constrained optimization problems. When applied to specific problems, obtaining a good performance in terms of efficacy and efficiency may depend on careful choices of options and parameters. In the present paper the application of Algencan to four portfolio optimization problems is discussed and numerical results are presented and evaluated.

Keywords: Constrained optimization, Augmented Lagrangian, Portfolios, Generalized Order-Value Optimization, Conditional Value-at-Risk.

Full text: [pdf]

Applications of nonlinear programming to packing problems

E. G. Birgin

in Applications + Practical Conceptualization + Mathematics = fruitful Innovation, Proceedings of the Forum of Mathematics for Industry 2014, R. S. Anderssen, P. Broadbridge, Y. Fukumoto, K. Kajiwara, T. Takagi, E. Verbitskiy, and M. Wakayama (Eds.), Springer Series Mathematics for Industry 11, pp. 31-39, 2016.

Abstract: The problem of packing items within bounded regions in the Euclidean space has multiple applications in a variety of areas, such as, Physics, Chemistry, and Engineering. Problems of this type exhibit various levels of complexity. Nonlinear programming formulations and methods had been successfully applied to a wide range of packing problems. In this review paper, a brief description of the state-of-the-art and an illustrated overview of packing nonlinear programming techniques and applications will be presented.

Full text: [pdf]

Two-stage two-dimensional guillotine cutting stock problems with usable leftovers

R. Andrade, E. G. Birgin, and R. Morabito

International Transactions in Operational Research Vol. 23 No. 1-2 (January-March, 2016), pages 121-145.

Abstract: In this study we are concerned with the non-exact two-stage two-dimensional guillotine cutting problem considering usable leftovers, in which stock plates remainders of the cutting patterns (non-used material or trim loss) can be used in the future, if they are large enough to fulfill future demands of items (ordered smaller plates). This cutting problem can be characterized as a residual bin-packing problem because of the possibility of creating new residual pieces, as the trim loss of each cutting/packing pattern does not necessarily represent waste of material and, depending on its size, it can be put back into stock. Two bilevel mathematical programming models to represent this non-exact two-stage two-dimensional residual bin-packing problem are presented. The models basically consist on cutting/packing the ordered items using a set of plates of minimum cost and, among all possible solutions of minimum cost, choosing one that maximizes the value of the generated usable leftovers. Because of special characteristics of these bilevel models, they can be reformulated as one-level mixed integer programming models. Results of some numerical experiments are presented to show that the models represent appropriately the problem and to illustrate their performances.

Keywords: Two-stage two-dimensional guillotine cutting, residual bin-packing problem, bilevel programming, MIP models, leftovers.

Full text: [pdf]

An inner-outer nonlinear programming approach for constrained quadratic matrix model updating

M. Andretta, E. G. Birgin, and M. Raydan

Mechanical Systems and Signal Processing Vol. 66-67 (January, 2016), pages 78-88.

Abstract: The Quadratic Finite Element Model Updating Problem (QFEMUP) concerns with updating a symmetric second-order finite element model so that it remains symmetric and the updated model reproduces a given set of desired eigenvalues and eigenvectors by replacing the corresponding ones from the original model. Taking advantage of the special structure of the constraint set, it is first shown that the QFEMUP can be formulated as a suitable constrained nonlinear programming problem. Using this formulation, a method based on successive optimizations is then proposed and analyzed. To avoid that spurious modes (eigenvectors) appear in the frequency range of interest (eigenvalues) after the model has been updated, additional constraints based on a quadratic Rayleigh quotient are dynamically included in the constraint set. A distinct practical feature of the proposed method is that it is implementable computing only a few eigenvalues and eigenvectors of the associated quadratic matrix pencil. The results of our numerical experiments on illustrative problems show that the algorithm works well in practice.

Full text: [pdf]

List scheduling and beam search methods for an extended version of the flexible job shop scheduling problem

E. G. Birgin, J. E. Ferreira, and D. P. Ronconi

European Journal of Operational Research, Vol. 247 No. 2 (December, 2015), pages 421-440.

Abstract: An extended version of the flexible job shop problem is tackled in this work. The considered extension to the classical flexible job shop problem allows the precedences between the operations to be given by an arbitrary directed acyclic graph instead of a linear order. Therefore, the problem consists of allocating the operations to the machines and sequencing them in compliance with the given precedences. The goal in the present work is the minimization of the makespan. A list scheduling algorithm is introduced and its natural extension to a beam search method is proposed. Numerical experiments assess the efficiency of the proposed approaches.

Keywords: Scheduling, flexible job shop, makespan, list scheduling, beam search.

Full text: [pdf]

Optimality properties of an Augmented Lagrangian method on infeasible problems

E. G. Birgin, J. M. Martínez, and L. F. Prudente

Computational Optimization and Applications, Vol. 60 No. 3 (August, 2015), pages 609-631.

Abstract: Sometimes, the feasible set of an optimization problem that one aims to solve using a Nonlinear Programming algorithm is empty. In this case, two characteristics of the algorithm are desirable. On the one hand, the algorithm should converge to a minimizer of some infeasibility measure. On the other hand, one may wish to find a point with minimal infeasibility for which some optimality condition, with respect to the objective function, holds. Ideally, the algorithm should converge to a minimizer of the objective function subject to minimal infeasibility. In this paper the behavior of an Augmented Lagrangian algorithm with respect to those properties will be studied.

Keywords:Nonlinear Programming, infeasible domains, Augmented Lagrangians, algorithms, numerical experiments.

Full text: [pdf]

Assessing the reliability of general-purpose Inexact Restoration methods

E. G. Birgin, L. F. Bueno, and J. M. Martínez

Journal of Computational and Applied Mathematics, Vol. 282 (July 2015), pages 1-16.

Abstract: Inexact Restoration methods have been proved to be effective to solve constrained optimization problems in which some structure of the feasible set induces a natural way of recovering feasibility from arbitrary infeasible points. Sometimes natural ways of dealing with minimization over tangent approximations of the feasible set are also employed. A recent paper [N. Banihashemi and C. Y. Kaya, Inexact Restoration for Euler discretization of box-constrained optimal control problems, Journal of Optimization Theory and Applications 156, pp. 726--760, 2013] suggests that the Inexact Restoration approach can be competitive with well-established nonlinear programming solvers when applied to certain control problems without any problem-oriented procedure for restoring feasibility. This result motivated us to revisit the idea of designing general-purpose Inexact Restoration methods, especially for large-scale problems. In this paper we introduce an affordable algorithm of Inexact Restoration type for solving arbitrary nonlinear programming problems and we perform the first experiments that aim to assess its reliability.

Keywords:Nonlinear programming, Inexact Restoration, numerical experiments.

Full text: [pdf]

Metaheuristics for large-scale instances of the linear ordering problem

C. S. Sakuraba, D. P. Ronconi, E. G. Birgin, and M. Yagiura

Expert Systems with Applications, Vol. 42 No. 9 (June, 2015), pages 4432-4442.

Abstract: This paper presents iterated local search and great deluge trajectory metaheuristics for the linear ordering problem (LOP). Both metaheuristics are based on the TREE local search method introduced in Sakuraba and Yagiura, 2010 (Efficient local search algorithms for the linear ordering problem, International Transactions in Operational Research 17, pp. 711-737) that is the only method ever applied to a set of large-sized instances that are in line with the scale of nowadays real applications. By providing diversification and intensification features, the introduced methods improve all best known solutions of the large-sized instances set. Extensive numerical experiments show that the introduced methods are capable of tackling sparse and dense large-scale instances with up to 8,000 vertices and 31,996,000 edges in a reasonable amount of time; while they also performs well in practice when compared with other state-of-the-art methods in a benchmark with small and medium-scale instances.

Keywords:Metaheuristics, iterated local search, great deluge, linear ordering problem, large-scale instances.

Full text: [pdf]

MIP models for two-dimensional non-guillotine cutting problems with usable leftovers

R. Andrade, E. G. Birgin, R. Morabito, and D. P. Ronconi

Journal of the Operational Research Society, Vol. 65 No. 11 (November , 2014), pages 1649-1663.

Abstract: In this study we deal with the two-dimensional non-guillotine cutting problem of how to cut a set of rectangular objects with known sizes and quantities to exactly produce a set of rectangular items with specified sizes and demands to be fulfilled. We are concerned with the special case of the problem in which the non-used material of the cutting patterns (objects leftovers) may be used in the future, if it is large enough to fulfill future items demands. Therefore, the problem is seen as a two-dimensional non-guillotine cutting/packing problem with usable leftovers, also known in the literature as a two-dimensional residual bin-packing problem. We use multilevel mathematical programming models to represent appropriately the problem, which basically consists on cutting the ordered items using a set of objects of minimum cost, among all possible solutions of minimum cost, choosing one that maximizes the value of the usable leftovers, and, among them, selecting one that minimizes the number of usable leftovers. Because of special characteristics of these multilevel models, they can be reformulated as one-level mixed integer programming (MIP) models. Illustrative numerical examples are presented and analysed.

Keywords: Two-dimensional cutting with usable leftovers, MIP models, non-guillotine cutting and packing, multilevel mathematical programming, residual bin-packing problem.

Full text: [pdf]

Spectral Projected Gradient methods: Review and Perspectives

E. G. Birgin, J. M. Martínez, and M. Raydan

Journal of Statistical Software, Vol. 60 No. 3 (September, 2014), http://www.jstatsoft.org/v60/i03.

Abstract: Over the last two decades, it has been observed that using the gradient vector as a search direction in large-scale optimization may lead to efficient algorithms. The effectiveness relies on choosing the step lengths according to novel ideas that are related to the spectrum of the underlying local Hessian rather than related to the standard decrease in the objective function. A review of these so-called spectral projected gradient methods for convex constrained optimization is presented. To illustrate the performance of these low-cost schemes, an optimization problem on the set of positive definite matrices is described.

Keywords: Spectral Projected Gradient methods, nonmonotone line search, large scale problems, convex constrained problems.

Full text: [pdf]

A MILP model for an extended version of the Flexible Job Shop Problem

E. G. Birgin, P. Feofiloff, C. G. Fernandes, E. L. de Melo, M. T. I. Oshiro, and D. P. Ronconi

Optimization Letters, Vol. 8 No. 4 (April, 2014), pages 1417-1431.

Abstract: A MILP model for an extended version of the Flexible Job Shop Scheduling problem is proposed. The extension allows the precedences between operations of a job to be given by an arbitrary directed acyclic graph rather than a linear order. The goal is the minimization of the makespan. Theoretical and practical advantages of the proposed model are discussed. Numerical experiments show the performance of a commercial exact solver when applied to the proposed model. The new model is also compared with a simple extension of the model described by Ozguven, Ozbakir, and Yavuz (Mathematical models for job-shop scheduling problems with routing and process plan flexibility, Applied Mathematical Modelling, 34:1539--1548, 2010), using instances from the literature and instances inspired by real data from the printing industry.

Keywords: Scheduling, Flexible Job Shop, MIP models.

Full text: [pdf]

Augmented Lagrangians with possible infeasibility and finite termination for global nonlinear programming

E. G. Birgin, J. M. Martínez, and L. F. Prudente

Journal of Global Optimization, Vol. 58 No. 2 (February, 2014), pages 207-242.

Abstract: In a recent paper, Birgin, Floudas and Martínez introduced an augmented Lagrangian method for global optimization. In their approach, augmented Lagrangian subproblems are solved using the alphaBB method and convergence to global minimizers was obtained assuming feasibility of the original problem. In the present research, the algorithm mentioned above will be improved in several crucial aspects. On the one hand, feasibility of the problem will not be required. Possible infeasibility will be detected in finite time by the new algorithms and optimal infeasibility results will be proved. On the other hand, finite termination results that guarantee optimality and/or feasibility up to any required precision will be provided. An adaptive modification in which subproblem tolerances depend on current feasibility and complementarity will also be given. The adaptive algorithm allows the augmented Lagrangian subproblems to be solved without requiring unnecessary potentially high precisions in the intermediate steps of the method, which improves the overall efficiency. Experiments showing how the new algorithms and results are related to practical computations will be given.

Keywords: Deterministic global optimization, augmented Lagrangians, nonlinear programming, algorithms, numerical experiments.

Full text: [pdf]

Packing circles within ellipses

E. G. Birgin, L. H. Bustamante, H. F. Callisaya, and J. M. Martínez

International Transactions in Operational Research, Vol. 20 No. 3 (May, 2013), pages 365-389.

Abstract: The problem of packing circles within ellipses is considered in the present paper. A new ellipse-based system of coordinates is introduced by means of which a closed formula to compute the distance of an arbitrary point to the boundary of an ellipse exists. Nonlinear programming models for some variants of 2D and 3D packing problems involving circular items and elliptical objects are given. The resulting models are medium-sized highly nonlinear challenging nonlinear programming problems for which a global solution is sought. For this purpose, multistart strategies are carefully and thoroughly explored. Numerical experiments are exhibited.

Keywords: Packing, ellipses, circles, global optimization.

Full text: [pdf]

Sparse projected-gradient method as a linear-scaling low-memory alternative to diagonalization in self-consistent field electronic structure calculations

E. G. Birgin, J. M. Martínez, L. Martínez, and G. B. Rocha

Journal of Chemical Theory and Computation, Vol. 9 No. 2 (February, 2013), pages 1043-1051.

Abstract: Large-scale electronic structure calculations usually involve huge nonlinear eigenvalue problems. A method for solving these problems without employing expensive eigenvalue decompositions of the Fock matrix is presented in this work. The sparsity of the input and output matrices is preserved at every iteration and the memory required by the algorithm scales linearly with the number of atoms of the system. The algorithm is based on a projected gradient iteration applied to the constraint fulfillment problem. The computer time required by the algorithm also scales approximately linearly with the number of atoms (or non-null elements of the matrices), and the algorithm is faster than standard implementations of modern eigenvalue decomposition methods for sparse matrices containing more than 50,000 non-null elements. The new method reproduces the sequence of semiempirical SCF iterations obtained by standard eigenvalue decomposition algorithms to good precision.

Keywords: Electronic Structure Calculations, Semiempirical methods, Projected Gradient, linear scaling, sparsity.

Full text: [pdf]

Symmetry-breaking constraints for packing identical orthogonal rectangles within polyhedra

R. Andrade and E. G. Birgin

Optimization Letters, Vol. 7 No. 2 (February 2013), pages 375-405.

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]

Deterministic and stochastic global optimization techniques for planar covering with ellipses problems

M. Andretta and E. G. Birgin

European Journal of Operational Research, Vol. 224 No. 1 (January 2013), pages 23-40.

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, Vol. 53 No. 2 (October 2012), pages 347-373.

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]

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, Vol. 44 No. 10 (October 2012), pages 1197-1208.

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]

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, Vol. 27 No. 6 (December 2012), pages 1001-1024.

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]

Augmented Lagrangian method with nonmonotone penalty parameters for constrained optimization

E. G. Birgin and J. M. Martínez

Computational Optimization and Applications, Vol. 51 No. 3 (April 2012), Pages 941-965.

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]

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.

Full text: [pdf] [ps]

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.

Full text: [pdf] [ps]

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.

Full text: [pdf] [ps]

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.

Full text: [pdf] [ps]

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.

Full text: [pdf] [ps]

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.

Full text: [pdf] [ps]

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.

Full text: [pdf] [ps]

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 (2008), 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.

Full text: [pdf] [ps]

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.

Full text: [pdf] [ps]

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.

Full text: [pdf] [ps]

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.

Full text: [pdf] [ps]

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.

Full text: [pdf] [ps]

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.

Full text: [pdf] [ps]

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.

Full text: [pdf] [ps]

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.

Full text: [pdf] [ps]

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.

Full text: [pdf] [ps]

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.

Full text: [pdf] [ps]

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.

Full text: [pdf] [ps]

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.

Full text: [pdf] [ps]

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.

Full text: [pdf] [ps]

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.

Full text: [pdf] [ps]

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.

Full text: [pdf] [ps]

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.

Full text: [pdf] [ps]

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.

Full text: [pdf] [ps]

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.

Full text: [pdf] [ps]

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.

Full text: [pdf] [ps]

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.

Full text: [pdf] [ps]

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.

Full text: [pdf] [ps]

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.

Full text: [pdf] [ps]

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.

Full text: [pdf] [ps]

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.

Full text: [pdf] [ps]

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.

Full text: [pdf] [ps]

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.

Full text: [pdf] [ps]

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.

Full text: [pdf] [ps]

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.

Full text: [pdf] [ps]