A nettó jelenérték maximalizálása erőforrás-korlátos projektekben - egy új harmóniakereső metaheurisztika (A harmony search metaheuristic for the resourceconstrained project scheduling problem with discounted cash flows)

Ebben a tanulmányban a szerző egy új harmóniakereső metaheurisztikát mutat be, amely a minimális időtartamú erőforrás-korlátos ütemezések halmazán a projekt nettó jelenértékét maximalizálja. Az optimális ütemezés elméletileg két egész értékű (nulla-egy típusú) programozási feladat megoldását jelenti, ahol az első lépésben meghatározzuk a minimális időtartamú erőforrás-korlátos ütemezések időtartamát, majd a második lépésben az optimális időtartamot feltételként kezelve megoldjuk a nettó jelenérték maximalizálási problémát minimális időtartamú erőforrás-korlátos ütemezések halmazán. A probléma NP-hard jellege miatt az egzakt megoldás elfogadható idő alatt csak kisméretű projektek esetében képzelhető el. A bemutatandó metaheurisztika a Csébfalvi (2007) által a minimális időtartamú erőforrás-korlátos ütemezések időtartamának meghatározására és a tevékenységek ennek megfelelő ütemezésére kifejlesztett harmóniakereső metaheurisztika továbbfejlesztése, amely az erőforrás-felhasználási konfliktusokat elsőbbségi kapcsolatok beépítésével oldja fel. Az ajánlott metaheurisztika hatékonyságának és életképességének szemléltetésére számítási eredményeket adunk a jól ismert és népszerű PSPLIB tesztkönyvtár J30 részhalmazán futtatva. Az egzakt megoldás generálásához egy korszerű MILP-szoftvert (CPLEX) alkalmaztunk. _______________ This paper presents a harmony search metaheuristic for the resource-constrained project scheduling problem with discounted cash flows. In the proposed approach, a resource-constrained project is characterized by its „best” schedule, where best means a makespan minimal resource constrained schedule for which the net present value (NPV) measure is maximal. Theoretically the optimal schedule searching process is formulated as a twophase mixed integer linear programming (MILP) problem, which can be solved for small-scale projects in reasonable time. The applied metaheuristic is based on the "conflict repairing" version of the "Sounds of Silence" harmony search metaheuristic developed by Csébfalvi (2007) for the resource-constrained project scheduling problem (RCPSP). In order to illustrate the essence and viability of the proposed harmony search metaheuristic, we present computational results for a J30 subset from the well-known and popular PSPLIB. To generate the exact solutions a state-of-the-art MILP solver (CPLEX) was used.

Model for facilities or vendors location in a global scale considering several echelons in the Chain

The facilities location problem for companies with global operations is very complex and not well explored in the literature. This work proposes a MILP model that solves the problem through minimization of the total logistic cost. Main contributions of the model are the pioneer carrying cost calculation, the treatment given to the take-or-pay costs and to the international tax benefits such as drawback and added value taxes in Brazil. The model was successfully applied to a real case of a chemical industry with industrial plants and sales all over the world. The model application recommended a totally new sourcing model for the company.

Self-Scheduling for energy and spinning reserve of wind/CSP plants by a MILP approach

This paper is on the self-scheduling for a power producer taking part in day-ahead joint energy and spinning reserve markets and aiming at a short-term coordination of wind power plants with concentrated solar power plants having thermal energy storage. The short-term coordination is formulated as a mixed-integer linear programming problem given as the maximization of profit subjected to technical operation constraints, including the ones related to a transmission line. Probability density functions are used to model the variability of the hourly wind speed and the solar irradiation in regard to a negative correlation. Case studies based on an Iberian Peninsula wind and concentrated solar power plants are presented, providing the optimal energy and spinning reserve for the short-term self-scheduling in order to unveil the coordination benefits and synergies between wind and solar resources. Results and sensitivity analysis are in favour of the coordination, showing an increase on profit, allowing for spinning reserve, reducing the need for curtailment, increasing the transmission line capacity factor. (C) 2014 Elsevier Ltd. All rights reserved.

Lagrangian-informed mixed integer programming reformulations

La programmation linéaire en nombres entiers est une approche robuste qui permet de résoudre rapidement de grandes instances de problèmes d'optimisation discrète. Toutefois, les problèmes gagnent constamment en complexité et imposent parfois de fortes limites sur le temps de calcul. Il devient alors nécessaire de développer des méthodes spécialisées afin de résoudre approximativement ces problèmes, tout en calculant des bornes sur leurs valeurs optimales afin de prouver la qualité des solutions obtenues. Nous proposons d'explorer une approche de reformulation en nombres entiers guidée par la relaxation lagrangienne. Après l'identification d'une forte relaxation lagrangienne, un processus systématique permet d'obtenir une seconde formulation en nombres entiers. Cette reformulation, plus compacte que celle de Dantzig et Wolfe, comporte exactement les mêmes solutions entières que la formulation initiale, mais en améliore la borne linéaire: elle devient égale à la borne lagrangienne. L'approche de reformulation permet d'unifier et de généraliser des formulations et des méthodes de borne connues. De plus, elle offre une manière simple d'obtenir des reformulations de moins grandes tailles en contrepartie de bornes plus faibles. Ces reformulations demeurent de grandes tailles. C'est pourquoi nous décrivons aussi des méthodes spécialisées pour en résoudre les relaxations linéaires. Finalement, nous appliquons l'approche de reformulation à deux problèmes de localisation. Cela nous mène à de nouvelles formulations pour ces problèmes; certaines sont de très grandes tailles, mais nos méthodes de résolution spécialisées les rendent pratiques.

Mixed-integer convex model for VAr expansion planning

This paper presents a mixed-integer convex-optimization-based approach for optimum investment reactive power sources in transmission systems. Unlike some convex-optimization techniques for the reactive power planning solution, in the proposed approach the taps settings of under-load tap-changing of transformers are modeled as a mixed-integer linear set equations. Are also considered the continuous and discrete variables for the existing and new capacitive and reactive power sources. The problem is solved for three significant demand scenarios (low demand, average demand and peak demand). Numerical results are presented for the CIGRE-32 electric power system.

Enhanced Mixed Integer Programming Techniques and Routing Problems

Mixed integer programming is up today one of the most widely used techniques for dealing with hard optimization problems. On the one side, many practical optimization problems arising from real-world applications (such as, e.g., scheduling, project planning, transportation, telecommunications, economics and finance, timetabling, etc) can be easily and effectively formulated as Mixed Integer linear Programs (MIPs). On the other hand, 50 and more years of intensive research has dramatically improved on the capability of the current generation of MIP solvers to tackle hard problems in practice. However, many questions are still open and not fully understood, and the mixed integer programming community is still more than active in trying to answer some of these questions. As a consequence, a huge number of papers are continuously developed and new intriguing questions arise every year. When dealing with MIPs, we have to distinguish between two different scenarios. The first one happens when we are asked to handle a general MIP and we cannot assume any special structure for the given problem. In this case, a Linear Programming (LP) relaxation and some integrality requirements are all we have for tackling the problem, and we are ``forced" to use some general purpose techniques. The second one happens when mixed integer programming is used to address a somehow structured problem. In this context, polyhedral analysis and other theoretical and practical considerations are typically exploited to devise some special purpose techniques. This thesis tries to give some insights in both the above mentioned situations. The first part of the work is focused on general purpose cutting planes, which are probably the key ingredient behind the success of the current generation of MIP solvers. Chapter 1 presents a quick overview of the main ingredients of a branch-and-cut algorithm, while Chapter 2 recalls some results from the literature in the context of disjunctive cuts and their connections with Gomory mixed integer cuts. Chapter 3 presents a theoretical and computational investigation of disjunctive cuts. In particular, we analyze the connections between different normalization conditions (i.e., conditions to truncate the cone associated with disjunctive cutting planes) and other crucial aspects as cut rank, cut density and cut strength. We give a theoretical characterization of weak rays of the disjunctive cone that lead to dominated cuts, and propose a practical method to possibly strengthen those cuts arising from such weak extremal solution. Further, we point out how redundant constraints can affect the quality of the generated disjunctive cuts, and discuss possible ways to cope with them. Finally, Chapter 4 presents some preliminary ideas in the context of multiple-row cuts. Very recently, a series of papers have brought the attention to the possibility of generating cuts using more than one row of the simplex tableau at a time. Several interesting theoretical results have been presented in this direction, often revisiting and recalling other important results discovered more than 40 years ago. However, is not clear at all how these results can be exploited in practice. As stated, the chapter is a still work-in-progress and simply presents a possible way for generating two-row cuts from the simplex tableau arising from lattice-free triangles and some preliminary computational results. The second part of the thesis is instead focused on the heuristic and exact exploitation of integer programming techniques for hard combinatorial optimization problems in the context of routing applications. Chapters 5 and 6 present an integer linear programming local search algorithm for Vehicle Routing Problems (VRPs). The overall procedure follows a general destroy-and-repair paradigm (i.e., the current solution is first randomly destroyed and then repaired in the attempt of finding a new improved solution) where a class of exponential neighborhoods are iteratively explored by heuristically solving an integer programming formulation through a general purpose MIP solver. Chapters 7 and 8 deal with exact branch-and-cut methods. Chapter 7 presents an extended formulation for the Traveling Salesman Problem with Time Windows (TSPTW), a generalization of the well known TSP where each node must be visited within a given time window. The polyhedral approaches proposed for this problem in the literature typically follow the one which has been proven to be extremely effective in the classical TSP context. Here we present an overall (quite) general idea which is based on a relaxed discretization of time windows. Such an idea leads to a stronger formulation and to stronger valid inequalities which are then separated within the classical branch-and-cut framework. Finally, Chapter 8 addresses the branch-and-cut in the context of Generalized Minimum Spanning Tree Problems (GMSTPs) (i.e., a class of NP-hard generalizations of the classical minimum spanning tree problem). In this chapter, we show how some basic ideas (and, in particular, the usage of general purpose cutting planes) can be useful to improve on branch-and-cut methods proposed in the literature.

Red Eléctrica de España uses integer programming for annual salary revisions

In this paper, we present a mixed-integer linear programming model for determining salary-revision matrices for an organization based on that organization?s general strategies. The solution obtained from this model consists of salary increases for each employee; these increases consider the employee?s professional performance, salary level relative to peers within the organization, and professional group. In addition to budget constraints, we modeled other elements typical of compensation systems, such as equity and justice. Red Eléctrica de España (REE), the transmission agent and operator of the Spanish electricity system, used the model to revise its 2010 and 2011 salary policies, and achieved results that were aligned with the company strategy. REE incorporated the model into the salary management module within its information system, and plans to continue to use the model in revisions of the module.

Mixed-integer nonlinear approach for the optimal scheduling of a head-dependent hydro chain

This paper is on the problem of short-term hydro scheduling (STHS), particularly concerning a head-dependent hydro chain We propose a novel mixed-integer nonlinear programming (MINLP) approach, considering hydroelectric power generation as a nonlinear function of water discharge and of the head. As a new contribution to eat her studies, we model the on-off behavior of the hydro plants using integer variables, in order to avoid water discharges at forbidden areas Thus, an enhanced STHS is provided due to the more realistic modeling presented in this paper Our approach has been applied successfully to solve a test case based on one of the Portuguese cascaded hydro systems with a negligible computational time requirement.

Optimal methodology for renewable energy dispatching in islanded operation

The management of energy resources for islanded operation is of crucial importance for the successful use of renewable energy sources. A Virtual Power Producer (VPP) can optimally operate the resources taking into account the maintenance, operation and load control considering all the involved cost. This paper presents the methodology approach to formulate and solve the problem of determining the optimal resource allocation applied to a real case study in Budapest Tech’s. The problem is formulated as a mixed-integer linear programming model (MILP) and solved by a deterministic optimization technique CPLEX-based implemented in General Algebraic Modeling Systems (GAMS). The problem has also been solved by Evolutionary Particle Swarm Optimization (EPSO). The obtained results are presented and compared.

Distributed energy resources management with cyber-physical SCADA in the context of future smart grids

In the energy management of a small power system, the scheduling of the generation units is a crucial problem for which adequate methodologies can maximize the performance of the energy supply. This paper proposes an innovative methodology for distributed energy resources management. The optimal operation of distributed generation, demand response and storage resources is formulated as a mixed-integer linear programming model (MILP) and solved by a deterministic optimization technique CPLEX-based implemented in General Algebraic Modeling Systems (GAMS). The paper deals with a vision for the grids of the future, focusing on conceptual and operational aspects of electrical grids characterized by an intensive penetration of DG, in the scope of competitive environments and using artificial intelligence methodologies to attain the envisaged goals. These concepts are implemented in a computational framework which includes both grid and market simulation.

Wind-CSP short-term coordination by MILP approach

This paper is on the maximization of total profit in a day-ahead market for a price-taker producer needing a short-term scheduling for wind power plants coordination with concentrated solar power plants, having thermal energy storage systems. The optimization approach proposed for the maximization of profit is a mixed-integer linear programming problem. The approach considers not only transmission grid constraints, but also technical operating constraints on both wind and concentrated solar power plants. Then, an improved short-term scheduling coordination is provided due to the more accurate modelling presented in this paper. Computer simulation results based on data for the Iberian wind and concentrated solar power plants illustrate the coordination benefits and show the effectiveness of the approach.

Energy-Aware Routing And Grooming For IP Transport Over WDM MLR Networks

In this work a mixed integer optimization linear programming (MILP) model was applied to mixed line rate (MLR) IP over WDM and IP over OTN over WDM (with and without OTN grooming) networks, with aim to reduce network energy consumption. Energy-aware and energy-aware & short-path routing techniques were used. Simulations were made based on a real network topology as well as on forecasts of traffic matrix based on statistical data from 2005 up to 2017. Energy aware routing optimization model on IPoWDM network, showed the lowest energy consumption along all years, and once compared with energy-aware & short-path routing, has led to an overall reduction in energy consumption up to 29%, expecting to save even more than shortest-path routing. © 2014 IEEE.

Wind-CSP short-term coordination by Milp approach

This paper is on the maximization of total profit in a day-ahead market for a price-taker producer needing a short-term scheduling for wind power plants coordination with concentrated solar power plants, having thermal energy storage systems. The optimization approach proposed for the maximization of profit is a mixed-integer linear programming problem. The approach considers not only transmission grid constraints, but also technical operating constraints on both wind and concentrated solar power plants. Then, an improved short-term scheduling coordination is provided due to the more accurate modelling presented in this paper. Computer simulation results based on data for the Iberian wind and concentrated solar power plants illustrate the coordination benefits and show the effectiveness of the approach.

Scheduling aircraft’s engines repair process: a mathematical model

In this talk, we discuss a scheduling problem that originated at TAP - Maintenance & Engineering - the maintenance, repair and overhaul organization of Portugal’s leading airline. In the repair process of aircrafts’ engines, the operations to be scheduled may be executed on a certain workstation by any processor of a given set, and the objective is to minimize the total weighted tardiness. A mixed integer linear programming formulation, based on the flexible job shop scheduling, is presented here, along with computational experiment on a real instance, provided by TAP-ME, from a regular working week. The model was also tested using benchmarking instances available in literature.

Multiobjective 0-1 integer programming for the use of sugarcane residual biomass in energy cogeneration

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)