Proximal methods for nonlinear programming: double regularization and inexact subproblems

This paper describes the first phase of a project attempting to construct an efficient general-purpose nonlinear optimizer using an augmented Lagrangian outer loop with a relative error criterion, and an inner loop employing a state-of-the art conjugate gradient solver. The outer loop can also employ double regularized proximal kernels, a fairly recent theoretical development that leads to fully smooth subproblems. We first enhance the existing theory to show that our approach is globally convergent in both the primal and dual spaces when applied to convex problems. We then present an extensive computational evaluation using the CUTE test set, showing that some aspects of our approach are promising, but some are not. These conclusions in turn lead to additional computational experiments suggesting where to next focus our theoretical and computational efforts.

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

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 converges to second-order stationary points in situations in which first-order methods fail are exhibited.

Outer Trust-Region Method for Constrained Optimization

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.

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

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 000 instances). It is also effective for solving the instances of problem set Cover III (almost 100 000 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 benchmarking purposes. Journal of the Operational Research Society (2010) 61, 306-320. doi: 10.1057/jors.2008.141 Published online 4 February 2009

Structured minimal-memory inexact quasi-Newton method and secant preconditioners for augmented Lagrangian optimization

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 on the presence of active constraints in the penalty-Lagrangian function, is also suggested. Numerical experiments using the Cute collection are presented.

The open capacitated arc routing problem

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Interior point method for long-term generation scheduling of large-scale hydrothermal systems

This paper presents an interior point method for the long-term generation scheduling of large-scale hydrothermal systems. The problem is formulated as a nonlinear programming one due to the nonlinear representation of hydropower production and thermal fuel cost functions. Sparsity exploitation techniques and an heuristic procedure for computing the interior point method search directions have been developed. Numerical tests in case studies with systems of different dimensions and inflow scenarios have been carried out in order to evaluate the proposed method. Three systems were tested, with the largest being the Brazilian hydropower system with 74 hydro plants distributed in several cascades. Results show that the proposed method is an efficient and robust tool for solving the long-term generation scheduling problem.

Bound constrained smooth optimization for solving variational inequalities and related problems

Variational inequalities and related problems may be solved via smooth bound constrained optimization. A comprehensive discussion of the important features involved with this strategy is presented. Complementarity problems and mathematical programming problems with equilibrium constraints are included in this report. Numerical experiments are commented. Conclusions and directions of future research are indicated.

A decomposition heuristic for the maximal covering location problem

This paper proposes a cluster partitioning technique to calculate improved upper bounds to the optimal solution of maximal covering location problems. Given a covering distance, a graph is built considering as vertices the potential facility locations, and with an edge connecting each pair of facilities that attend a same client. Coupling constraints, corresponding to some edges of this graph, are identified and relaxed in the Lagrangean way, resulting in disconnected subgraphs representing smaller subproblems that are computationally easier to solve by exact methods. The proposed technique is compared to the classical approach, using real data and instances from the available literature. © 2010 Edson Luiz França Senne et al.

Application of an iterative method and an evolutionary algorithm in fuzzy optimization

This work develops two approaches based on the fuzzy set theory to solve a class of fuzzy mathematical optimization problems with uncertainties in the objective function and in the set of constraints. The first approach is an adaptation of an iterative method that obtains cut levels and later maximizes the membership function of fuzzy decision making using the bound search method. The second one is a metaheuristic approach that adapts a standard genetic algorithm to use fuzzy numbers. Both approaches use a decision criterion called satisfaction level that reaches the best solution in the uncertain environment. Selected examples from the literature are presented to compare and to validate the efficiency of the methods addressed, emphasizing the fuzzy optimization problem in some import-export companies in the south of Spain. © 2012 Brazilian Operations Research Society.

A genetic algorithm for crop rotation

In the last few years, crop rotation has gained attention due to its economic, environmental and social importance which explains why it can be highly beneficial for farmers. This paper presents a mathematical model for the Crop Rotation Problem (CRP) that was adapted from literature for this highly complex combinatorial problem. The CRP is devised to find a vegetable planting program that takes into account green fertilization restrictions, the set-aside period, planting restrictions for neighboring lots and for crop sequencing, demand constraints, while, at the same time, maximizing the profitability of the planted area. The main aim of this study is to develop a genetic algorithm and test it in a real context. The genetic algorithm involves a constructive heuristic to build the initial population and the operators of crossover, mutation, migration and elitism. The computational experiment was performed for a medium dimension real planting area with 16 lots, considering 29 crops of 10 different botanical families and a two-year planting rotation. Results showed that the algorithm determined feasible solutions in a reasonable computational time, thus proving its efficacy for dealing with this practical application.

A hybrid method for the probabilistic maximal covering location-allocation problem

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Metodologia para otimização em subcontratação de serviço de usinagem

Operational Research (OR) is an eminent science to business competitiveness and the capacity of algorithms and spreadsheets that exist today allows people to apply them for a lower cost and with less complexity. However, spreadsheets linked to OR techniques, when directed to real problems, are still little explored in their full potential. In order to use them better, this article utilizes the Microsoft Office Excel to solve an optimization practical problem and decision-making of machining subcontracting. In general, although considered a frequent problem, is not of easy solution, optimize the mix of production versus outsourcing, because of the restrictions and resources available, it requests investments in specific software. In this way, this research aims to develop software to be called SOSU (Optimization Software for Machining Subcontracting). SOSU should introduce the best mix of internal and subcontracted machining for n types of parts that, over a certain period of time t, maximize capacity and meet all the demand at the lowest cost possible. The methodology adopted follows the bibliographic reference and it is assumed that the necessary data to prove from mathematical modeling of production areas and from a system of costs already structured. The nature of the problem justifies the application of Linear Programming (LP), Visual Basic for Applications (VBA) is used for computational implementation and interface with the user and the supplement Solver to find the solution. The analysis of the experiments show that the SOSU optimizes resources and improves the decision-making process, besides an easy operation, it can be implemented or quickly adapted and without the need of large investments.

Hybrid constraint programming and metaheuristic methods for large scale optimization problems

This work presents hybrid Constraint Programming (CP) and metaheuristic methods for the solution of Large Scale Optimization Problems; it aims at integrating concepts and mechanisms from the metaheuristic methods to a CP-based tree search environment in order to exploit the advantages of both approaches. The modeling and solution of large scale combinatorial optimization problem is a topic which has arisen the interest of many researcherers in the Operations Research field; combinatorial optimization problems are widely spread in everyday life and the need of solving difficult problems is more and more urgent. Metaheuristic techniques have been developed in the last decades to effectively handle the approximate solution of combinatorial optimization problems; we will examine metaheuristics in detail, focusing on the common aspects of different techniques. Each metaheuristic approach possesses its own peculiarities in designing and guiding the solution process; our work aims at recognizing components which can be extracted from metaheuristic methods and re-used in different contexts. In particular we focus on the possibility of porting metaheuristic elements to constraint programming based environments, as constraint programming is able to deal with feasibility issues of optimization problems in a very effective manner. Moreover, CP offers a general paradigm which allows to easily model any type of problem and solve it with a problem-independent framework, differently from local search and metaheuristic methods which are highly problem specific. In this work we describe the implementation of the Local Branching framework, originally developed for Mixed Integer Programming, in a CP-based environment. Constraint programming specific features are used to ease the search process, still mantaining an absolute generality of the approach. We also propose a search strategy called Sliced Neighborhood Search, SNS, that iteratively explores slices of large neighborhoods of an incumbent solution by performing CP-based tree search and encloses concepts from metaheuristic techniques. SNS can be used as a stand alone search strategy, but it can alternatively be embedded in existing strategies as intensification and diversification mechanism. In particular we show its integration within the CP-based local branching. We provide an extensive experimental evaluation of the proposed approaches on instances of the Asymmetric Traveling Salesman Problem and of the Asymmetric Traveling Salesman Problem with Time Windows. The proposed approaches achieve good results on practical size problem, thus demonstrating the benefit of integrating metaheuristic concepts in CP-based frameworks.