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.

**Keywords:** Quadratic matrix model updating, quadratic
Rayleigh quotient, nonlinear programming, algorithms.

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.

Using sentinels to detect intersections of convex and nonconvex polygons

W. F. Mascarenhas and E. G. Birgin

*Computational & Applied Mathematics* Vol. 29 No. 2 (June 2010), Pages 247-267.

**Abstract:** We describe finite sets of points, called sentinels, which
allow us to decide if isometric copies of polygons, convex or not, intersect.
As an example of the applicability of the concept of sentinel, we explain how
they can be used to formulate an algorithm based on the optimization of
differentiable models to pack polygons in convex sets.

**Keywords:** Sentinels, polygons, intersection, packing, nonlinear
programming.

Full text: [pdf]

Second-order negative-curvature methods for box-constrained and general constrained optimization

R. Andreani, E. G. Birgin, J. M. Martínez and M. L. Schuverdt

*Computational Optimization and Applications* Vol. 45 No. 2 (March
2010), Pages 209-236.

**Abstract:** A Nonlinear Programming algorithm that converges to
second-order stationary points is introduced in this paper. The main tool is a
second-order negative-curvature method for box-constrained minimization of a
certain class of functions that do not possess continuous second
derivatives. This method is used to define an Augmented Lagrangian algorithm
of PHR (Powell-Hestenes-Rockafellar) type. Convergence proofs under weak
constraint qualifications are given. Numerical examples showing that the new
method converge to second-order stationary points in situations in which
first-order methods fail are exhibited.

**Keywords:** Nonlinear programming, Augmented Lagrangians,
global convergence, optimality conditions, second-order conditions,
constraint qualifications.

Full text: [pdf]

An effective recursive partitioning approach for the packing of identical rectangles in a rectangle

E. G. Birgin, R. D. Lobato and R. Morabito

*Journal of the Operational Research Society* Vol. 61 No. 2 (February 2010), Pages 306-320.

**Abstract:** In this work, we deal with the problem of packing
(orthogonally and without overlapping) identical rectangles in a
rectangle. This problem appears in different logistics settings, such as the
loading of boxes on pallets, the arrangements of pallets in trucks and the
stowing of cargo in ships. We present a recursive partitioning approach
combining improved versions of a recursive five-block heuristic and an
$L$-approach for packing rectangles into larger rectangles and $L$-shaped
pieces. The combined approach is able to rapidly find the optimal solutions
of all instances of the pallet loading problem sets Cover I and II (more than
50 thousand instances). It is also effective for solving the instances of
problem set Cover III (almost 100 thousand instances) and practical examples
of a woodpulp stowage problem, if compared to other methods from the
literature. Some theoretical results are also discussed and, based on them,
efficient computer implementations are introduced. The computer implementation
and the data sets are available for benchmark purposes at
*http://www.ime.usp.br/~egbirgin/packing/*.

**Keywords:** Cutting and packing, manufacturer's pallet loading
problem, woodpulp stowage problem, non-guillotine cutting pattern, recursive
algorithms.

New and improved results for packing identical unitary radius circles within triangles, rectangles and strips

E. G. Birgin and J. M. Gentil

*Computers & Operations Research* Vol. 37 No. 7 (July 2010), Pages 1318-1327.

**Abstract:** The focus of study in this paper is the class of packing
problems. More specifically, it deals with the placement of a set of N
circular items of unitary radius inside an object with the aim of minimizing
its dimensions. Differently shaped containers are considered, namely circles,
squares, rectangles, strips and triangles. By means of the resolution of
nonlinear equations systems through the Newton-Raphson method, the herein
presented algorithm succeeds in improving the accuracy of previous results
attained by continuous optimization approaches up to numerical machine
precision. The computer implementation and the data sets are available at http://www.ime.usp.br/~egbirgin/packing/.

**Keywords:** Packing, nonlinear equations system, Newton's method,
nonlinear programming.

Full text: [pdf]

Partial Spectral Projected Gradient Method with Active-Set Strategy for Linearly Constrained Optimization

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

*Numerical Algorithms*,
Vol. 53 No. 1 (January 2010), Pages 23-52.

**Abstract:** A method for linearly constrained optimization which
modifies and generalizes recent box-constraint optimization algorithms is
introduced. The new algorithm is based on a relaxed form of Spectral Projected
Gradient iterations. Intercalated with these projected steps, internal
iterations restricted to faces of the polytope are performed, which enhance
the efficiency of the algorithms. Convergence proofs are given and numerical
experiments are included and commented. Software supporting this paper is
available through the TANGO Project web page.

**Keywords:** Linearly constrained optimization, spectral
projected gradient method, active set methods.

Full text: [pdf]

PACKMOL: A package for building initial configurations for molecular dynamics simulations

L. Martínez, R. Andrade, E. G. Birgin and J. M. Martínez

*Journal of Computational Chemistry*,
Vol. 30 No. 13 (October 2009), Pages 2157-2164.

**Abstract:** Adequate initial configurations for molecular dynamics
simulations consist of arrangements of molecules distributed in space in such
a way to approximately represent the system's overall structure. In order that
the simulations are not disrupted by large Van der Waals repulsive
interactions, atoms from different molecules must keep safe pairwise
distances. Obtaining such a molecular arrangement can be considered a packing
problem: Each type molecule must satisfy spatial constraints related to the
geometry of the system, and the distance between atoms of different molecules
must be greater than some specified tolerance. We have developed a code able
to pack millions of atoms, grouped in arbitrarily complex molecules, inside a
variety of three-dimensional regions. The regions may be intersections of
spheres, ellipses, cylinders, planes or boxes. The user must provide only the
structure of one molecule of each type and the geometrical constraints that
each type of molecule must satisfy. Building complex mixtures, interfaces,
solvating biomolecules in water or other solvents, or mixtures of solvents is
straightforward. In addition, different atoms belonging to the same molecule
may also be restricted to different spacial regions, in such a way that more
ordered molecular arrangements can be built, as micelles, lipid double-layers,
etc. The packing time for state-of-the-art molecular dynamics systems varies
from a few seconds to a few minutes in a personal computer. The input files
are simple and currently compatible with PDB, Tinker, Molden or Moldy
coordinate files. The package is distributed as free software and can be
downloaded from
http://www.ime.unicamp.br/~martinez/packmol/.

**Keywords:** Initial configuration, molecular dynamics, packing,
large-scale optimization, PACKMOL.

Full text: [pdf]

Estimation of the thickness and the optical parameters of several superimposed thin films using optimization

R. Andrade, E. G. Birgin, I. Chambouleyron, J. M. Martínez and S. D. Ventura

*Applied Optics*,
Vol. 47 No. 28 (October 2008), Pages 5208-5220.

**Abstract:** The Reverse Engineering problem addressed in the present
research consists in estimating the thicknesses and the optical parameters of
two thin films deposited on a transparent substrate using only transmittance
data through the whole stack. To the present author's knowledge this is the
first report on the retrieval of the optical constants and the thickness of
multiple film structures using transmittance data only. The same methodology
may be used if the available data correspond to normal reflectance. The
software used in this work is freely available through the PUMA Project web
page (http://www.ime.usp.br/~egbirgin/puma/).

**Keywords:** Optical constants, thin films, optimization,
numerical algorithms, Reverse Engineering.

Improving ultimate convergence of an Augmented Lagrangian method

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

*Optimization Methods and Software*,
Vol. 23 No. 2 (April 2008), Pages 177-195.

**Abstract:** Optimization methods that employ the classical
Powell-Hestenes-Rockafellar Augmented Lagrangian are useful tools
for solving Nonlinear Programming problems. Their reputation decreased
in the last ten years due to the comparative success of Interior-Point
Newtonian algorithms, which are asymptotically faster. In the present
research a combination of both approaches is evaluated. The idea is to
produce a competitive method, being more robust and efficient than its
"pure" counterparts for critical problems. Moreover, an additional
hybrid algorithm is defined, in which the Interior Point method is
replaced by the Newtonian resolution of a KKT system identified by the
Augmented Lagrangian algorithm. The software used in this work is freely
available through the TANGO Project web page.

**Keywords:** Nonlinear programming, Augmented Lagrangian methods,
Interior-Point methods, Newton's method, experiments.

Structured minimal-memory inexact quasi-Newton method and secant preconditioners for Augmented Lagrangian Optimization

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

*Computational Optimization and Applications*,
Vol. 39 No. 1 (January 2008), Pages 1-16.

**Abstract:** Augmented Lagrangian methods for large-scale optimization
usually require efficient algorithms for minimization with box constraints.
On the other hand, active-set box-constraint methods employ unconstrained
optimization algorithms for minimization inside the faces of the box. Several
approaches may be employed for computing internal search directions in the
large-scale case. In this paper a minimal-memory quasi-Newton approach with
secant preconditioners is proposed, taking into account the structure of
Augmented Lagrangians that come from the popular Powell-Hestenes-Rockafellar
scheme. A combined algorithm, that uses the quasi-Newton formula or a
truncated-Newton procedure, depending of the presence of active constraints in
the penalty-Lagrangian function, is also suggested. Numerical experiments
using the CUTE collection are presented.

**Keywords:** Nonlinear programming, Augmented Lagrangian methods, box
constraints, quasi-Newton, truncated-Newton.

Minimizing the object dimensions in circle and sphere packing problems

E. G. Birgin and F. N. C. Sobral

*Computers & Operations Research*,
Vol. 35 No. 7 (July 2008), Pages 2357-2375.

**Abstract:** Given a fixed set of identical or different-sized circular
items, the problem we deal with consists on finding the smallest object within
which the items can be packed. Circular, triangular, squared, rectangular and
also strip objects are considered. Moreover, 2D and 3D problems are
treated. Twice-differentiable models for all these problems are presented. A
strategy to reduce the complexity of evaluating the models is employed and, as
a consequence, instances with a large number of items can be
considered. Numerical experiments show the flexibility and reliability of the
new unified approach.

**Keywords:** Packing of circles and spheres, models,
algorithms, nonlinear programming.

Augmented Lagrangian methods under the Constant Positive Linear Dependence constraint qualification

R. Andreani, E. G. Birgin, J. M. Martínez and M. L. Schuverdt

*Mathematical Programming*,
Vol. 111 No. 1-2 (January 2008), Pages 5-32.

**Abstract:** Two Augmented Lagrangian algorithms for solving KKT
systems are introduced. The algorithms differ in the way in which penalty
parameters are updated. Possibly infeasible accumulation points are
characterized. It is proved that feasible limit points that satisfy the
Constant Positive Linear Dependence constraint qualification are KKT
solutions. Boundedness of the penalty parameters is proved under suitable
assumptions. Numerical experiments are presented.

**Keywords:** Nonlinear programming, Augmented Lagrangian methods, KKT
systems, numerical experiments.

On Augmented Lagrangian methods with general lower-level constraints

R. Andreani, E. G. Birgin, J. M. Martínez and M. L. Schuverdt

*SIAM Journal on Optimization*,
Vol. 18 No. 4 (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.

Method of Sentinels for Packing Items within Arbitrary Convex Regions

E. G. Birgin, J. M. Martínez, W. F. Mascarenhas and D. P. Ronconi

*Journal of the Operational Research Society*,
Vol. 57 No. 6 (June 2006), Pages 735-746.

**Abstract:** A new method is introduced for packing objects in convex
regions of the Euclidian n-dimensional space. By means of this approach the
packing problem becomes a global finite-dimensional continuous optimization
problem. The strategy is based on the new concept of sentinels sets. Sentinels
sets are finite subsets of the objects to be packed such that when two objects
are superposed at least one sentinel of one object is in the interior of the
other. Minimal sets of sentinels are found in simple 2-dimensional
cases. Numerical experiments and pictures showing the potentiality of the new
technique are presented.

**Keywords:** Sentinels, packing problems, cutting problems, models,
nonlinear programming.

Orthogonal packing of rectangular items within arbitrary convex regions by nonlinear optimization

E. G. Birgin, J. M. Martínez, F. H. Nishihara and D. P. Ronconi

*Computers & Operations Research*,
Vol. 33 No. 12 (December 2006), Pages 3535-3548.

**Abstract:** The orthogonal packing of rectangular items in an
arbitrary convex region is considered in this work. The packing problem is
modeled as the problem of deciding for the feasibility or infeasibility of a
set of nonlinear equality and inequality constraints. A procedure based on
nonlinear programming is introduced and numerical experiments which show that
the new procedure is reliable are exhibited.

**Keywords:** Packing of rectangles, orthogonal packing, feasibility
problems, models, nonlinear programming.

Local Convergence of an Inexact-Restoration method and Numerical Experiments

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

*Journal of Optimization Theory and Applications*,
Vol. 127 No. 2 (November 2005), Pages 229-247.

**Abstract:** Local convergence of an inexact-restoration method for
nonlinear programming is proved. Numerical experiments are performed with the
objective of evaluating the behavior of the purely local method against a
globally convergent nonlinear-programming algorithm.

**Keywords:** Inexact-restoration method, nonlinear programming, local
convergence, numerical experiments.

See also the Technical Report (extended version of the published article) [pdf] [ps]

A note on an L-approach for solving the manufacturer's pallet loading problem

E. G. Birgin, R. Morabito and F. H. Nishihara

*Journal of the Operational Research Society*,
Vol. 56 No. 12 (December 2005), Pages 1448-1451.

**Abstract:** An L-approach for packing (l,w)-rectangles into an
(L,W)-rectangle was introduced in [L. Lins, S. Lins and R. Morabito, An
L-approach for packing (l,w)-rectangles into rectangular and L-shaped pieces,
Journal of the Operational Research Society 54, pp. 777-789, 2003]. The
authors of that paper conjecture that the L-approach is exact and point out
its runtime requirements as the main drawback. In this note it is shown that,
by simply using a different data structure, the runtime is considerably
reduced in spite of larger (but affordable) memory requirements. This
reduction is important for practical purposes since it makes the algorithm
much more acceptable for supporting actual decisions in pallet loading.
Intensive numerical experiments showing the efficiency and effectiveness of
the algorithm are presented.

**Keywords:** Cutting and packing, pallet and container loading,
recursive algorithm, implementation.

Optimization techniques for the estimation of the thickness and the optical parameters of thin films using reflectance data

S. Ventura, E. G. Birgin, J. M. Martínez and I. Chambouleyron

*Journal of Applied Physics*,
Vol. 97 043512 (February 2005).

**Abstract:** The present work considers the problem of estimating the
thickness and the optical constants (extinction coefficient and refractive
index) of thin films from the spectrum of normal reflectance R. This is an
ill-conditioned highly underdetermined inverse problem. The estimation is done
in the spectral range where the film is not opaque. The idea behind the choice
of this particular spectral range is to compare the film characteristics
retrieved from transmittance T and from reflectance data. In the first part
of the paper a compact formula for R is deduced. The approach to deconvolute
the R data is to use well known information on the dependence of the optical
constants on photon energy of semiconductors and dielectrics and to formulate
the estimation as a nonlinear optimization problem. Previous publications of
the group on the subject provide guidelines for designing the new
procedures. The consistency of the approach is tested with computer generated
thin films and also with measured R and T spectral data of an a-Si:H film
deposited onto glass. The results on gedanken films and onto a-Si:H indicate
a very good agreement between expected and retrieved values.

**Keywords:** Optical constants, thin films, reflectance, optimization,
numerical algorithms.

Practical active-set Euclidian trust-region method with spectral projected gradients for bound-constrained minimization

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

*Optimization*,
Vol. 54 No. 3 (June 2005), Pages 305-325.

**Abstract:** A practical active-set method for bound-constrained
minimization is introduced. Within the current face the classical Euclidian
trust-region method is employed. Spectral projected gradient directions are
used to abandon faces. Numerical results are presented.

**Keywords:** Bound-constrained optimization, projected gradient,
spectral gradient, trust regions.

Numerical comparison of Augmented Lagrangian algorithms for nonconvex problems

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

*Computational Optimization and Applications*, Vol. 31 No. 1 (May
2005), Pages 31-55.

**Abstract:** Augmented Lagrangian algorithms are very popular tools for
solving nonlinear programming problems. At each outer iteration of these
methods a simpler optimization problem is solved, for which efficient
algorithms can be used, especially when the problems are large. The most
famous Augmented Lagrangian algorithm for minimization with inequality
constraints is known as Powell-Hestenes-Rockafellar (PHR) method. The main
drawback of PHR is that the objective function of the subproblems is not twice
continuously differentiable. This is the main motivation for the introduction
of many alternative Augmented Lagrangian methods. Most of them have
interesting interpretations as proximal point methods for solving the dual
problem, when the original nonlinear programming problem is convex. In this
paper a numerical comparison between many of these methods is performed using
all the suitable problems of the CUTE collection.

**Keywords:** Nonlinear programming, Augmented Lagrangian
methods, inequality constraints, benchmarking, algorithms.

Robust stopping criteria for Dykstra's algorithm

E. G. Birgin and M. Raydan

*SIAM Journal on Scientific Computing*, Vol. 26 No. 4 (March 2005),
Pages 1405-1414.

**Abstract:** Dykstra's algorithm is a suitable alternating projection
scheme for solving the optimization problem of finding the closest point to a
given one onto the intersection of a finite number of closed and convex
sets. It has been recently used in a wide variety of applications. However, in
practice, the commonly used stopping criteria are not robust and could stop
the iterative process prematurely at a point that does not solve the
optimization problem. In this work we present a counter example to illustrate
the weakness of the commonly used criteria, and then we develop full-proof
stopping rules. Additional experiments are shown to illustrate the advantages
of this new stopping criteria, including their associated computational cost.

**Keywords:** Convex optimization, alternating projection methods,
Dykstra's algorithm, stopping criteria.

Spectral projected gradient and variable metric methods for optimization with linear inequalities

R. Andreani, E. G. Birgin, J. M. Martínez and J. Yuan

*IMA Journal of Numerical Analysis*, Vol. 25 No. 2 (April 2005), Pages
221-252.

**Abstract:** A family of variable metric methods for convex constrained
optimization was introduced recently by Birgin, Martínez and Raydan. One of
the members of this family is the Inexact Spectral Projected Gradient (ISPG)
method for minimization with convex constraints. At each iteration of these
methods a strictly convex quadratic function with convex constraints must be
(inexactly) minimized. In the case of ISPG it was shown that, in some
important applications, iterative projection methods can be used for this
minimization. In this paper the particular case in which the convex domain is
a polytope described by a finite set of linear inequalities is considered. For
solving the linearly constrained convex quadratic subproblem a dual approach
is adopted, by means of which subproblems become (not necessarily strictly)
convex quadratic minimization problems with box constraints. For solving this
problem, we use an active-set box-constraint quadratic optimizer with a
proximal-point type unconstrained algorithm for minimization within the
current faces. Convergence results and numerical experiments are
presented.

**Keywords:** Linearly-constrained optimization, projected gradient,
nonmonotone line search, spectral gradient.

Optimizing the Packing of Cylinders into a Rectangular Container: A Nonlinear Approach

E. G. Birgin, J. M. Martínez and D. P. Ronconi

*European Journal of Operational Research*,
Vol. 160 No 1 (January 2005), Pages 19-33.

**Abstract:** The container loading problem has important industrial
and commercial applications. An increase in the number of items in a container
leads to a decrease in cost. For this reason the related optimization problem
is of economic importance. In this work, a procedure based on a nonlinear
decision problem to solve the cylinder packing problem with identical
diameters is presented. This formulation is based on the fact that the centers
of the cylinders have to be inside the rectangular box defined by the base of
the container (a radius far from the frontier) and far from each other at
least one diameter. With this basic premise the procedure tries to find the
maximum number of cylinder centers that satisfy these restrictions. The
continuous nature of the problem is one of the reasons that motivated this
study. A comparative study with other methods of the literature is presented
and better results are achieved.

**Keywords:** Cylinder packing, rectangular container, circular
container, nonlinear programming, bound-constrained minimization,
convex-constrained minimization.

Inexact Spectral Projected Gradient Methods on Convex Sets

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

*IMA Journal of Numerical Analysis*,
Vol. 23 No 4 (October 2003), Pages 539-559.

**Abstract:** A new method is introduced for large scale convex
constrained optimization. The general model algorithm involves, at each
iteration, the approximate minimization of a convex quadratic on the feasible
set of the original problem and global convergence is obtained by means of
nonmonotone line searches. A specific algorithm, the Inexact Spectral
Projected Gradient method (ISPG), is implemented using inexact projections
computed by Dykstra's alternating projection method and generates interior
iterates. The ISPG method is a generalization of the Spectral Projected
Gradient method (SPG), but can be used when projections are difficult to
compute. Numerical results for constrained least-squares rectangular matrix
problems are presented.

**Keywords:** Convex constrained optimization, Projected gradient,
nonmonotone line search, spectral gradient, Dykstra's algorithm.

Estimation of optical parameters of very thin films

E. G. Birgin, I. Chambouleyron, J. M. Martínez and S. D. Ventura

*Applied Numerical Mathematics*,
Vol. 47 No 2 (November 2003), Pages 109-119.

**Abstract:** In recent papers, the problem of estimating the thickness
and the optical constants (refractive index and absorption coefficient) of
thin films using only transmittance data has been addressed by means of
optimization techniques. Models were proposed for solving this problem using
linearly constrained optimization and unconstrained optimization. However, the
optical parameters of ``very thin'' films could not be recovered with methods
that are successful in other situations. Here we introduce an optimization
technique that seems to be efficient for recovering the parameters of very
thin films.

**Keywords:** Optical constants, thin films, optimization, numerical
algorithms.

Globally convergent inexact quasi-Newton methods for solving nonlinear systems

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

*Numerical Algorithms*,
Vol. 32 No 2-4 (April 2003), Pages 249-260.

**Abstract:** Large scale nonlinear systems of equations can be solved
by means of inexact quasi-Newton methods. A global convergence theory is
introduced that guarantees that, under reasonable assumptions, the algorithmic
sequence converges to a solution of the problem. Under additional standard
assumptions, superlinear convergence is preserved.

**Keywords:** Nonlinear systems, inexact Newton methods, global
convergence, superlinear convergence, quasi-Newton methods.

Optimization problems in the estimation or parameters of thin films and the elimination of the influence of the substrate

E. G. Birgin, I. Chambouleyron and J. M. Martínez

*Journal of Computational and Applied Mathematics*,
Vol. 152 No. 1 (March 2003), Pages 35-50.

**Abstract:** In a recent paper, the authors introduced a method to
estimate optical parameters of thin films using transmission data. The
associated model assumes that the film is deposited on a completely
transparent substrate. It has been observed, however, that small absorption of
substrates affect in a nonnegligible way the transmitted energy. The question
arises of the reliability of the estimation method to retrieve optical
parameters in the presence of substrates of different thicknesses and
absorption degrees. In this paper, transmission spectra of thin films
deposited on non-transparent substrates are generated and, as a first
approximation, the method based on transparent substrates is used to estimate
the optical parameters. As expected, the method is good when the absorption of
the substrate is very small, but fails when one deals with less transparent
substrates. To overcome this drawback, an iterative procedure is introduced,
that allows one to approximate the transmittance with transparent substrate,
given the transmittance with absorbent substrate. The updated method turns out
to be almost as efficient in the case of absorbent substrates as it was in the
case of transparent ones.

**Keywords:** Optimization, estimation of parameters, unconstrained
minimization, constrained optimization, thin films, optical constants,
transmittance.

Solution of bounded nonlinear systems of equations using homotopies with inexact restoration

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

*International Journal of Computer Mathematics*,
Vol. 80 No. 2 (February 2003), Pages 211-222.

**Abstract:** Nonlinear systems of equations often represent
mathematical models of chemical production processes and other engineering
problems. Homotopic techniques (in particular, the bounded homotopies
introduced by Paloschi) are used for enhancing convergence to solutions,
especially when a good initial estimate is not available. In this paper, the
homotopy curve is considered as the feasible set of a mathematical programming
problem, where the objective is to find the optimal value of the homotopic
parameter. Inexact restoration techniques can then be used to generate
approximations in a neighborhood of the homotopy, the size of which is
theoretically justified. Numerical examples are given.

**Keywords:** Nonlinear programming, nonlinear systems, homotopies,
bounded homotopies, homotopy methods, inexact restoration.

Minimization subproblems and heuristics for an applied clustering problem

E. G. Birgin, J.M. Martínez and D. P. Ronconi

*European Journal of Operational Research*,
Vol. 146 No. 1 (April 1, 2003), Pages 19-34.

**Abstract:** A practical problem that requires the classification of a
set of points of R^{n} using a criterion not sensitive to bounded
outliers is studied in this paper. A fixed-point (k-means) algorithm is
defined that uses an arbitrary distance function. Finite convergence is
proved. A robust distance defined by Boente, Fraiman and Yohai is selected for
applications. Smooth approximations of this distance are defined and suitable
heuristics are introduced to enhance the probability of finding global
optimizers. A real-life example is presented and commented.

**Keywords:** Nonlinear programming, heuristics, clustering,
classification, fixed points.

Optical constants and thickness determination of very thin amorphous semiconductor films

I. Chambouleyron, S. D. Ventura, E. G. Birgin and J. M. Martínez,

*Journal of Applied Physics*,
Vol. 92 No. 6 (September 15, 2002), Pages 3093-3102.

**Abstract:** This contribution addresses the relevant question of
retrieving, from transmittance data, the optical constants and thickness of
very thin semiconductor and dielectric films. The retrieval process looks for
a thickness that, subject to the physical input of the problem, minimizes the
difference between the measured and the theoretical spectra. This is a highly
underdetermined problem but, the use of approximate - though simple -
functional dependences of the index of refraction and of the absorption
coefficient on photon energy, used as an a priori information, allows
surmounting the ill-posedness of the problem. The method is illustrated with
the analysis of transmittance data of very thin amorphous silicon films. The
method allows retrieving physically meaningful solutions for films as thin as
300 A. The estimated parameters agree well with known data or with optical
parameters measured by independent methods. The limitations of the adopted
model and the shortcomings of the optimization algorithm are presented and
discussed.

**Keywords:** Optical constants, thin films, optimization, numerical
algorithms.

Large-scale active-set box-constrained optimization method with spectral projected gradients

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

*Computational Optimization and Applications*,
Vol. 23 No. 1 (October 2002), Pages 101-125.

**Abstract:** A new active-set method for smooth box-constrained
minimization is introduced. The algorithm combines an unconstrained method,
including a new line-search which aims to add many constraints to the working
set at a single iteration, with a recently introduced technique (spectral
projected gradient) for dropping constraints from the working set. Global
convergence is proved. A computer implementation is fully described and a
numerical comparison assesses the reliability of the new algorithm.

**Keywords:** Box-constrained minimization, numerical methods,
active-set strategies, Spectral Projected Gradient.

Algorithm 813: SPG - software for convex-constrained optimization

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

*ACM Transactions on Mathematical Software*,
Vol. 27 No. 3 (September 2001), Pages 340-349.

**Abstract:** A Fortran 77 software which implements the SPG method is
introduced. SPG is a nonmonotone projected gradient algorithm for solving
large-scale convex-constrained optimization problems. It combines the
classical projected gradient method with the spectral gradient choice of
steplength and a nonmonotone line search strategy. Implementation details are
presented and the usage of the software is described. Some new numerical tests
that have been recently performed are reported. The main conclusion is that
SPG compares favorably with existing software.

**Keywords:** Projected gradients, nonmonotone line search, large-scale
problems, bound constrained problems, spectral gradient method.

A box-constrained optimization algorithm with negative curvature directions and spectral projected gradients

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

*Computing [Suppl]*, Vol. 15 (2001), Pages 49-60.

**Abstract:** A practical algorithm for box-constrained optimization is
introduced. The algorithm combines an active-set strategy with spectral
projected gradient iterations. In the interior of each face a strategy that
deals efficiently with negative curvature is employed. Global convergence
results are given. Numerical results are presented.

**Keywords:** Box constrained minimization, active set methods, spectral
projected gradients, dogleg path methods.

A Spectral Conjugate Gradient method for unconstrained optimization

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

*Applied Mathematics and Optimization*, Vol. 43 No. 2 (2001),
Pages 117-118.

**Abstract:** A family of scaled conjugate-gradient algorithms for
large-scale unconstrained minimization is defined. The Perry, the
Polak-Ribièere and the Fletcher-Reeves formulae are compared using a spectral
scaling derived from Raydan's spectral gradient optimization method. The best
combination of formula, scaling and initial choice of step-length is compared
against well known algorithms using a classical set of problems. An additional
comparison involving an ill-conditioned estimation problem in Optics is
presented.

**Keywords:** Unconstrained minimization, spectral gradient method,
conjugate gradients.

Determination of thickness and optical constants of a-Si:H films from transmittance data

M. Mulato, I. Chambouleyron, E. G. Birgin and J. M. Martínez

*Applied Physics Letters*, Vol. 77 No. 14 (2000), Pages 2133-2135.

**Abstract:** This work presents the first application of a recently
developed numerical method to determine the thickness and the optical
constants of thin films using experimental transmittance data only. The new
method may be applied to films not displaying a fringe pattern and is shown to
work for a-Si:H layers as thin as 100 nm. The performance and limitations of
the method are discussed on the basis of experiments performed on a series of
six a-Si:H samples grown under identical conditions, but with thickness
varying from 98 nm to 1.2 mu m.

**Keywords:** Thin films, optical constants, a-Si:H films, unconstrained
minimization.

Nonmonotone Spectral Projected Gradient Methods on Convex Sets

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

*SIAM Journal on Optimization*, Vol. 10 No. 4 (2000), Pages 1196-1211.

**Abstract:** Nonmonotone projected gradient techniques are considered
for the minimization of differentiable functions on closed convex sets.
The classical projected gradient schemes are extended to include a nonmonotone
steplength strategy that is based on the Grippo-Lampariello-Lucidi nonmonotone
line search. In particular, the nonmonotone strategy is combined with the
spectral gradient choice of steplength to accelerate the convergence
process. In addition to the classical projected gradient nonlinear path, the
feasible spectral projected gradient is used as a search direction to avoid
additional trial projections during the one-dimensional search
process. Convergence properties and extensive numerical results are presented.

**Keywords:** Projected gradients, nonmonotone line search, large scale
problems, bound constrained problems, spectral gradient method.

Restricted optimization: a clue to a fast and accurate implementation of the Common Reflection Surface Stack method

E. G. Birgin, R. Biloti, M. Tygel and L. T. Santos

*Journal of Applied Geophysics*, Vol. 42 No. 3-4 (December 1999),
Pages 143-155.

**Abstract:** For a fixed, central ray in an isotropic elastic or
acoustic media, traveltime moveouts of rays in its vicinity can be described
in terms of a certain number of parameters that refer to the central ray
only. The determination of these parameters out of multi-coverage data leads
to very powerful algorithms that can be used for several imaging and inversion
processes. Assuming two-dimensional propagation, the traveltime expressions
depend on three parameters directly related to the geometry of the unknown
model in the vicinity of the central ray. We present a new method to extract
these parameters out of coherency analysis applied directly to the data. It
uses (a) fast one-parameter searches on different sections extracted from the
multi-coverage data to derive initial values of the sections parameters, and
(b) the application of a recently introduced Spectral Projected Gradient
optimization algorithm for the final parameter estimation. Application of the
method on a synthetic example shows an excellent performance of the algorithm
both in accuracy and efficiency. The results obtained so far indicate that the
algorithm may be a feasible option to solve the corresponding, harder, full
three-dimensional problem, in which eight parameters, instead of three, are
required.

**Keywords:** Multi-coverage data, Common Reflection Surface method,
hyperbolic traveltime, coherency function, optimization, Spectral Projected
Gradient method.

Estimation of the optical constants and the thickness of thin films using unconstrained optimization

E. G. Birgin, I. Chambouleyron and J. M. Martínez

*Journal of Computational Physics*, Vol. 151, No. 2 (May 1999),
Pages 862-880.

**Abstract:** The problem of estimating the thickness and the optical
constants of thin films using transmission data only is very challenging from
the mathematical point of view, and has a technological and an economic
importance. In many cases it represents a very ill-conditioned inverse problem
with many local-nonglobal solutions. In a recent publication we proposed
nonlinear programming models for solving this problem.Well-known software for
linearly constrained optimization was used with success for this purpose. In
this paper we introduce an unconstrained formulation of the nonlinear
programming model and we solve the estimation problem using a method based on
repeated calls to a recently introduced unconstrained minimization
algorithm. Numerical experiments on computer-generated films show that the new
procedure is reliable.

**Keywords:** Unconstrained minimization, spectral gradient method,
optical constants, thin films.

Automatic differentiation for optimal control problems

E. G. Birgin and Y. G. Evtushenko

in *Dynamics of Non-homogeneous System*,
edited by Y. S. Popkov, Proceedings of ISA RAS,
Institute of System Analysis of the Russian Academy of Science, Moscow,
Vol. 2 (1999), Pages 53-62.

**Abstract:** Automatic differentiation is used for the solution of
optimal control problems. The original problem is reduced to a nonlinear
programming problem using general Runge-Kutta integration formulas. Canonical
formulas which use a fast automatic differentiation strategy are given to
compute derivatives of the goal function.

**Keywords:** Automatic differentiation, optimal control problem,
Runge-Kutta integration methods.

Automatic differentiation and Spectral Projected Gradient methods for optimal control problems

E. G. Birgin and Y. G. Evtushenko

*Optimization Methods & Software*, Vol. 10 No. 2 (December
1998), Pages 125-146.

**Abstract:** Automatic differentiation and nonmonotone spectral
projected gradient techniques are used for solving optimal control
problems. The original problem is reduced to a nonlinear programming one using
general Runge-Kutta integration formulas. Canonical formulas which use a fast
automatic differentiation strategy are given to compute derivatives of the
objective function. On the basis of this approach, codes for solving optimal
control problems are developed and some numerical results are presented.

**Keywords:** Automatic differentiation, Spectral Projected Gradient,
nonmonotone line search, optimal control problem, software for optimal control
problems, Runge-Kutta integration methods.