Uma maneira de resolver problemas de programação linear de grande escala é explorar a relaxação lagrangeana das restrições \"difíceis\'\' e utilizar métodos de subgradientes. Populares por fornecerem rapidamente boas aproximações de soluções duais, eles não produzem diretamente as soluções primais. Para obtê-las com custo computacional adequado, pode-se construir seqüências ergódicas ou utilizar uma técnica proposta recentemente, denominada algoritmo do volume. As propriedades teóricas de convergência não foram bem estabelecidas nesse algoritmo, mas pequenas modificações permitem a demonstração da convergência dual. Destacam-se como adaptações o algoritmo do volume revisado, um método de feixes específico, e o algoritmo do volume incorporado ao método de variação do alvo. Este trabalho foi baseado no estudo desses algoritmos e de todos os conceitos envolvidos, em especial, análise convexa e otimização não diferenciável. Estudamos as principais diferenças teóricas desses métodos e realizamos comparações numéricas com problemas lineares e lineares inteiros, em particular, o corte máximo em grafos. / One way to solve large-scale linear programming problems is to exploit the Lagrangian relaxation of the difficult constraints and use subgradient methods. Such methods are popular as they give good approximations of dual solutions. Unfortunately, they do not directly yield primal solutions. Two alternatives to obtain primal solutions under reasonable computational cost are the construction of ergodic sequences and the use of the recently developed volume algorithm. While the convergence of ergodic sequences is well understood, the convergence properties of the volume algorithm is not well established in the original paper. This lead to some modifications of the original method to ease the proof of dual convergence. Three alternatives are the revised volume algorithm, a special case of the bundle method, and the volume algorithm incorporated by the variable target value method. The aim of this work is to study such algorithms and all related concepts, especially convex analysis and nondifferentiable optimization. We analysed the main theoretical differences among the methods and performed numerical experiments with linear and integer problems, in particular, the maximum cut problem on graphs.

This operations research thesis should be situated in the field of the power generation industry. The general objective of this work is to efficiently solve the Generalized Unit Commitment (GUC) problem by means of specialized software. The GUC problem generalizes the Unit Commitment (UC) problem by simultane-ously solving the associated Optimal Power Flow (OPF) problem. There are many approaches to solve the UC and OPF problems separately, but approaches to solve them jointly, i.e. to solve the GUC problem, are quite scarce. One of these GUC solving approaches is due to professors Batut and Renaud, whose methodology has been taken as a starting point for the methodology presented herein.This thesis report is structured as follows. Chapter 1 describes the state of the art of the UC and GUC problems. The formulation of the classical short-term power planning problems related to the GUC problem, namely the economic dispatching problem, the OPF problem, and the UC problem, are reviewed. Special attention is paid to the UC literature and to the traditional methods for solving the UC problem. In chapter 2 we extend the OPF model developed by professors Heredia and Nabona to obtain our GUC model. The variables used and the modelling of the thermal, hydraulic and transmission systems are introduced, as is the objective function. Chapter 3 deals with the Variable Duplication (VD) method, which is used to decompose the GUC problem as an alternative to the Classical Lagrangian Relaxation (CLR) method. Furthermore, in chapter 3 dual bounds provided by the VDmethod or by the CLR methods are theoretically compared.Throughout chapters 4, 5, and 6 our solution methodology, the Radar Multiplier (RM) method, is designed and tested. Three independent matters are studied: first, the auxiliary problem principle method, used by Batut and Renaud to treat the inseparable augmented Lagrangian, is compared with the block coordinate descent method from both theoretical and practical points of view. Second, the Radar Sub- gradient (RS) method, a new Lagrange multiplier updating method, is proposed and computationally compared with the classical subgradient method. And third, we study the local character of the optimizers computed by the Augmented Lagrangian Relaxation (ALR) method when solving the GUC problem. A heuristic to improve the local ALR optimizers is designed and tested.Chapter 7 is devoted to our computational implementation of the RM method, the MACH code. First, the design of MACH is reviewed brie y and then its performance is tested by solving real-life large-scale UC and GUC instances. Solutions computed using our VD formulation of the GUC problem are partially primal feasible since they do not necessarily fulfill the spinning reserve constraints. In chapter 8 we study how to modify this GUC formulation with the aim of obtaining full primal feasible solutions. A successful test based on a simple UC problem is reported. The conclusions, contributions of the thesis, and proposed further research can be found in chapter 9.

Iterative methods are extensively used to solve linear and nonlinear problems arising from both pure and applied sciences, and in particular, in fixed point theory and optimization. An iterative method which is used to find a fixed point of an operator or an optimal solution to an optimization problem generates a sequence in an iterative manner. We are in a hope that this sequence can converge to a solution of the problem under investigation. It is therefore quite naturally to require that the distance of this sequence to the solution set of the problem under investigation be decreasing from iteration to iteration. This is the idea of Fejer-monotonicity. In this paper, We consider quasi-Fejer monotone sequences; that is, we consider Fejer monotone sequences together with errors. Properties of quasi-Fejer monotone sequences are investigated, weak and strong convergence of quasi-Fejer monotone sequences are obtained, and an application to the convex feasibility problem is included.

ALVES, Alexsandro de Oliveira. Integração de heurísticas lagrangeanas com algoritmos exatos para a otimização de particionamento de conjuntos. 2007. 49 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2007. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-05-20T18:05:04Z No. of bitstreams: 1 2007_dis_aoalves.pdf: 434539 bytes, checksum: d7550e0ddf22c4c083e44734e59375f7 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-05-20T18:08:40Z (GMT) No. of bitstreams: 1 2007_dis_aoalves.pdf: 434539 bytes, checksum: d7550e0ddf22c4c083e44734e59375f7 (MD5) / Made available in DSpace on 2016-05-20T18:08:40Z (GMT). No. of bitstreams: 1 2007_dis_aoalves.pdf: 434539 bytes, checksum: d7550e0ddf22c4c083e44734e59375f7 (MD5) Previous issue date: 2007 / In this work we evaluate both exact and heuristic methods for the set partitioning problem (SPP). These heuristics are based on greedy algorithms, tabu search and subgradient optimization. Computational experiments performed on benchmark instances of the problem indicate that our heuristics are competitive with existing ones from the literature in obtaining both lower and upper bounds of good quality in reasonable execution time. We use a Branch and Bound algorithm that allows to prove optimality of solutions obtained by our heuristics for a large set of benchmark instances of the SPP. Thus, we show that our heuristics are efficient in obtaining feasible solutions of good quality for this problem. / Neste trabalho avaliamos métodos heurísticos e exatos para o Problema de Particionamento de Conjuntos (PPC). Realizamos testes computacionais com heurísticas lagrangeanas baseadas em algoritmos gulosos, busca tabu e método de otimização pelo subgradiente. Os resultados obtidos, comparados com os da literatura, comprovam a eficiência de nossas heurísticas na obtenção de limites inferiores e superiores de boa qualidade, em tempo computacional razoável, para instâncias da literatura. Utilizamos um esquema de Branch and Bound para tentar resolver instâncias do PPC à otimalidade e para comprovar a qualidade dos resultados alcançados por nossas heurísticas.

In this doctoral thesis, we propose new iterative methods for solving a class of convex optimization problems. In general, we consider problems in which the objective function is composed of a finite sum of convex functions and the set of constraints is, at least, convex and closed. The iterative methods we propose are basically designed through the combination of incremental subgradient methods and string-averaging algorithms. Furthermore, in order to obtain methods able to solve optimization problems with many constraints (and possibly in high dimensions), generally given by convex functions, our analysis includes an operator that calculates approximate projections onto the feasible set, instead of the Euclidean projection. This feature is employed in the two methods we propose; one deterministic and the other stochastic. A convergence analysis is proposed for both methods and numerical experiments are performed in order to verify their applicability, especially in large scale problems. / Nesta tese de doutorado, propomos novos métodos iterativos para a solução de uma classe de problemas de otimização convexa. Em geral, consideramos problemas nos quais a função objetivo é composta por uma soma finita de funções convexas e o conjunto de restrições é, pelo menos, convexo e fechado. Os métodos iterativos que propomos são criados, basicamente, através da junção de métodos de subgradientes incrementais e do algoritmo de média das sequências. Além disso, visando obter métodos flexíveis para soluções de problemas de otimização com muitas restrições (e possivelmente em altas dimensões), dadas em geral por funções convexas, a nossa análise inclui um operador que calcula projeções aproximadas sobre o conjunto viável, no lugar da projeção Euclideana. Essa característica é empregada nos dois métodos que propomos; um determinístico e o outro estocástico. Uma análise de convergência é proposta para ambos os métodos e experimentos numéricos são realizados a fim de verificar a sua aplicabilidade, principalmente em problemas de grande escala.

FundaÃÃo Cearense de Apoio ao Desenvolvimento Cientifico e TecnolÃgico / Neste trabalho avaliamos mÃtodos heurÃsticos e exatos para o Problema de Particionamento de Conjuntos (PPC). Realizamos testes computacionais com heurÃsticas lagrangeanas baseadas em algoritmos gulosos, busca tabu e mÃtodo de otimizaÃÃo pelo subgradiente. Os resultados obtidos, comparados com os da literatura, comprovam a eficiÃncia de nossas heurÃsticas na obtenÃÃo de limites inferiores e superiores de boa qualidade, em tempo computacional razoÃvel, para instÃncias da literatura. Utilizamos um esquema de Branch and Bound para tentar resolver instÃncias do PPC ÃÂotimalidade e para comprovar a qualidade dos resultados alcanÃados por nossas heurÃsticas. / In this work we evaluate both exact and heuristic methods for the set partitioning problem (SPP). These heuristics are based on greedy algorithms, tabu search and subgradient optimization. Computational experiments performed on benchmark instances of the problem indicate that our heuristics are competitive with existing ones from the literature in obtaining both lower and upper bounds of good quality in reasonable execution time. We use a Branch and Bound algorithm that allows to prove optimality of solutions obtained by our heuristics for a large set of benchmark instances of the SPP. Thus, we show that our heuristics are efficient in obtaining feasible solutions of good quality for this problem.

Uma maneira de resolver problemas de programação linear de grande escala é explorar a relaxação lagrangeana das restrições \"difíceis\'\' e utilizar métodos de subgradientes. Populares por fornecerem rapidamente boas aproximações de soluções duais, eles não produzem diretamente as soluções primais. Para obtê-las com custo computacional adequado, pode-se construir seqüências ergódicas ou utilizar uma técnica proposta recentemente, denominada algoritmo do volume. As propriedades teóricas de convergência não foram bem estabelecidas nesse algoritmo, mas pequenas modificações permitem a demonstração da convergência dual. Destacam-se como adaptações o algoritmo do volume revisado, um método de feixes específico, e o algoritmo do volume incorporado ao método de variação do alvo. Este trabalho foi baseado no estudo desses algoritmos e de todos os conceitos envolvidos, em especial, análise convexa e otimização não diferenciável. Estudamos as principais diferenças teóricas desses métodos e realizamos comparações numéricas com problemas lineares e lineares inteiros, em particular, o corte máximo em grafos. / One way to solve large-scale linear programming problems is to exploit the Lagrangian relaxation of the difficult constraints and use subgradient methods. Such methods are popular as they give good approximations of dual solutions. Unfortunately, they do not directly yield primal solutions. Two alternatives to obtain primal solutions under reasonable computational cost are the construction of ergodic sequences and the use of the recently developed volume algorithm. While the convergence of ergodic sequences is well understood, the convergence properties of the volume algorithm is not well established in the original paper. This lead to some modifications of the original method to ease the proof of dual convergence. Three alternatives are the revised volume algorithm, a special case of the bundle method, and the volume algorithm incorporated by the variable target value method. The aim of this work is to study such algorithms and all related concepts, especially convex analysis and nondifferentiable optimization. We analysed the main theoretical differences among the methods and performed numerical experiments with linear and integer problems, in particular, the maximum cut problem on graphs.

No description available.

The air transportation market has been growing steadily for the past three decades since the airline deregulation in 1978. With competition also becoming more intense, airline companies have been trying to enhance their market shares and profit margins by composing favorable flight schedules and by efficiently allocating their resources of aircraft and crews so as to reduce operational costs. In practice, this is achieved based on demand forecasts and resource availabilities through a structured airline scheduling process that is comprised of four decision stages: schedule planning, fleet assignment, aircraft routing, and crew scheduling. The outputs of this process are flight schedules along with associated assignments of aircraft and crews that maximize the total expected profit. Traditionally, airlines deal with these four operational scheduling stages in a sequential manner. However, there exist obvious interdependencies among these stages so that restrictive solutions from preceding stages are likely to limit the scope of decisions for succeeding stages, thus leading to suboptimal results and even infeasibilities. To overcome this drawback, we first study the aircraft routing problem, and develop some novel modeling foundations based on which we construct and analyze an integrated model that incorporates fleet assignment, aircraft routing, and crew pairing within a single framework. Given a set of flights to be covered by a specific fleet type, the aircraft routing problem (ARP) determines a flight sequence for each individual aircraft in this fleet, while incorporating specific considerations of minimum turn-time and maintenance checks, as well as restrictions on the total accumulated flying time, the total number of takeoffs, and the total number of days between two consecutive maintenance operations. This stage is significant to airline companies as it directly assigns routes and maintenance breaks for each aircraft in service. Most approaches for solving this problem adopt set partitioning formulations that include exponentially many variables, thus requiring the design of specialized column generation or branch-and-price algorithms. In this dissertation, however, we present a novel compact polynomially sized representation for the ARP, which is then linearized and lifted using the Reformulation-Linearization Technique (RLT). The resulting formulation remains polynomial in size, and we show that it can be solved very efficiently by commercial software without complicated algorithmic implementations. Our numerical experiments using real data obtained from United Airlines demonstrate significant savings in computational effort; for example, for a daily network involving 344 flights, our approach required only about 10 CPU seconds for deriving an optimal solution. We next extend Model ARP to incorporate its preceding and succeeding decision stages, i.e., fleet assignment and crew pairing, within an integrated framework. We formulate a suitable representation for the integrated fleeting, routing, and crew pairing problem (FRC), which accommodates a set of fleet types in a compact manner similar to that used for constructing the aforementioned aircraft routing model, and we generate eligible crew pairings on-the-fly within a set partitioning framework. Furthermore, to better represent industrial practice, we incorporate itinerary-based passenger demands for different fare-classes. The large size of the resulting model obviates a direct solution using off-the-shelf software; hence, we design a solution approach based on Benders decomposition and column generation using several acceleration techniques along with a branch-and-price heuristic for effectively deriving a solution to this model. In order to demonstrate the efficacy of the proposed model and solution approach and to provide insights for the airline industry, we generated several test instances using historical data obtained from United Airlines. Computational results reveal that the massively-sized integrated model can be effectively solved in reasonable times ranging from several minutes to about ten hours, depending on the size and structure of the instance. Moreover, our benchmark results demonstrate an average of 2.73% improvement in total profit (which translates to about 43 million dollars per year) over a partially integrated approach that combines the fleeting and routing decisions, but solves the crew pairing problem sequentially. This improvement is observed to accrue due to the fact that the fully integrated model effectively explores alternative fleet assignment decisions that better utilize available resources and yield significantly lower crew costs. / Ph. D.