The constrained compartmentalized knapsack problem: mathematical models and solution methods

The constrained compartmentalized knapsack problem can be seen as an extension of the constrained knapsack problem. However, the items are grouped into different classes so that the overall knapsack has to be divided into compartments, and each compartment is loaded with items from the same class. Moreover, building a compartment incurs a fixed cost and a fixed loss of the capacity in the original knapsack, and the compartments are lower and upper bounded. The objective is to maximize the total value of the items loaded in the overall knapsack minus the cost of the compartments. This problem has been formulated as an integer non-linear program, and in this paper, we reformulate the non-linear model as an integer linear master problem with a large number of variables. Some heuristics based on the solution of the restricted master problem are investigated. A new and more compact integer linear model is also presented, which can be solved by a branch-and-bound commercial solver that found most of the optimal solutions for the constrained compartmentalized knapsack problem. On the other hand, heuristics provide good solutions with low computational effort. (C) 2011 Elsevier BM. All rights reserved.

On the cutting stock problem under stochastic demand

This paper addresses the one-dimensional cutting stock problem when demand is a random variable. The problem is formulated as a two-stage stochastic nonlinear program with recourse. The first stage decision variables are the number of objects to be cut according to a cutting pattern. The second stage decision variables are the number of holding or backordering items due to the decisions made in the first stage. The problem`s objective is to minimize the total expected cost incurred in both stages, due to waste and holding or backordering penalties. A Simplex-based method with column generation is proposed for solving a linear relaxation of the resulting optimization problem. The proposed method is evaluated by using two well-known measures of uncertainty effects in stochastic programming: the value of stochastic solution-VSS-and the expected value of perfect information-EVPI. The optimal two-stage solution is shown to be more effective than the alternative wait-and-see and expected value approaches, even under small variations in the parameters of the problem.

Job rotation in assembly lines employing disabled workers

In this paper we consider the programming of job rotation in the assembly line worker assignment and balancing problem. The motivation for this study comes from the designing of assembly lines in sheltered work centers for the disabled, where workers have different task execution times. In this context, the well-known training aspects associated with job rotation are particularly desired. We propose a metric along with a mixed integer linear model and a heuristic decomposition method to solve this new job rotation problem. Computational results show the efficacy of the proposed heuristics. (C) 2009 Elsevier B.V. All rights reserved.

Time-series-based maximization of distributed wind power generation integration

Energy policies and technological progress in the development of wind turbines have made wind power the fastest growing renewable power source worldwide. The inherent variability of this resource requires special attention when analyzing the impacts of high penetration on the distribution network. A time-series steady-state analysis is proposed that assesses technical issues such as energy export, losses, and short-circuit levels. A multiobjective programming approach based on the nondominated sorting genetic algorithm (NSGA) is applied in order to find configurations that maximize the integration of distributed wind power generation (DWPG) while satisfying voltage and thermal limits. The approach has been applied to a medium voltage distribution network considering hourly demand and wind profiles for part of the U.K. The Pareto optimal solutions obtained highlight the drawbacks of using a single demand and generation scenario, and indicate the importance of appropriate substation voltage settings for maximizing the connection of MPG.

Optimal Contract Pricing of Distributed Generation in Distribution Networks

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

Comparison of Reactive Power Support in Distribution Networks Provided by Capacitor Banks and Distributed Generators

This paper presents a comparison of reactive power support in distribution networks provided by switched Capacitor Banks (CBs) and Distributed Generators (DGs). Regarding switched CBs, a Tabu Search metaheuristic algorithm is developed to determine their optimal operation with the objective of reducing the power losses in the lines on the system, while meeting network constraints. on the other hand, the optimal operation of DGs is analyzed through an evolutionary Multi-Objective (MO) programming approach. The objectives of such approach are the minimization of power losses and operation cost of the DGs. The comparison of the reactive power support provided by switched CBs and DGs is carried out using a modified IEEE 34 bus distribution test system.

A nonlinear model for the long-term hydro-thermal generation scheduling problem over multiple areas with transmission constraints

This paper presents a nonlinear model with individual representation of plants for the centralized long-term hydrothermal scheduling problem over multiple areas. In addition to common aspects of long-term scheduling, this model takes transmission constraints into account. The ability to optimize hydropower exchange among multiple areas is important because it enables further minimization of complementary thermal generation costs. Also, by considering transmission constraints for long-term scheduling, a more precise coupling with shorter horizon schedules can be expected. This is an important characteristic from both operational and economic viewpoints. The proposed model is solved by a sequential quadratic programming approach in the form of a prototype system for different case studies. An analysis of the benefits provided by the model is also presented. ©2009 IEEE.

Optimal contract pricing of distributed generation under a competitive framework

A bilevel programming approach for the optimal contract pricing of distributed generation (DG) in distribution networks is presented. The outer optimization problem corresponds to the owner of the DG who must decide the contract price that would maximize his profits. The inner optimization problem corresponds to the distribution company (DisCo), which procures the minimization of the payments incurred in attending the expected demand while satisfying network constraints. The meet the expected demand the DisCo can purchase energy either form the transmission network through the substations or form the DG units within its network. The inner optimization problem is substituted by its Karush- Kuhn-Tucker optimality conditions, turning the bilevel programming problem into an equivalent single-level nonlinear programming problem which is solved using commercially available software. © 2010 IEEE.

Optimal allocation of capacitors in radial distribution systems with distributed generation

This paper presents a mixed-integer linear programming approach to solving the optimal fixed/switched capacitors allocation (OCA) problem in radial distribution systems with distributed generation. The use of a mixed-integer linear formulation guarantees convergence to optimality using existing optimization software. The results of one test system and one real distribution system are presented in order to show the accuracy as well as the efficiency of the proposed solution technique. © 2011 IEEE.

Extração semi-automática do eixo de rodovia em imagens de média e alta resolução usando programação dinâmica

Pós-graduação em Ciências Cartográficas - FCT

Improvements in the score matrix calculation method using parallel score estimating algorithm

The increasing amount of sequences stored in genomic databases has become unfeasible to the sequential analysis. Then, the parallel computing brought its power to the Bioinformatics through parallel algorithms to align and analyze the sequences, providing improvements mainly in the running time of these algorithms. In many situations, the parallel strategy contributes to reducing the computational complexity of the big problems. This work shows some results obtained by an implementation of a parallel score estimating technique for the score matrix calculation stage, which is the first stage of a progressive multiple sequence alignment. The performance and quality of the parallel score estimating are compared with the results of a dynamic programming approach also implemented in parallel. This comparison shows a significant reduction of running time. Moreover, the quality of the final alignment, using the new strategy, is analyzed and compared with the quality of the approach with dynamic programming.

Generating unconstrained two-dimensional non-guillotine cutting patterns by a Recursive Partitioning Algorithm

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 pro blem 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. Journal of the Operational Research Society (2012) 63, 183-200. doi: 10.1057/jors.2011.6 Published online 17 August 2011

Constraint based methods for allocation and scheduling of periodic applications

This work presents exact algorithms for the Resource Allocation and Cyclic Scheduling Problems (RA&CSPs). Cyclic Scheduling Problems arise in a number of application areas, such as in hoist scheduling, mass production, compiler design (implementing scheduling loops on parallel architectures), software pipelining, and in embedded system design. The RA&CS problem concerns time and resource assignment to a set of activities, to be indefinitely repeated, subject to precedence and resource capacity constraints. In this work we present two constraint programming frameworks facing two different types of cyclic problems. In first instance, we consider the disjunctive RA&CSP, where the allocation problem considers unary resources. Instances are described through the Synchronous Data-flow (SDF) Model of Computation. The key problem of finding a maximum-throughput allocation and scheduling of Synchronous Data-Flow graphs onto a multi-core architecture is NP-hard and has been traditionally solved by means of heuristic (incomplete) algorithms. We propose an exact (complete) algorithm for the computation of a maximum-throughput mapping of applications specified as SDFG onto multi-core architectures. Results show that the approach can handle realistic instances in terms of size and complexity. Next, we tackle the Cyclic Resource-Constrained Scheduling Problem (i.e. CRCSP). We propose a Constraint Programming approach based on modular arithmetic: in particular, we introduce a modular precedence constraint and a global cumulative constraint along with their filtering algorithms. Many traditional approaches to cyclic scheduling operate by fixing the period value and then solving a linear problem in a generate-and-test fashion. Conversely, our technique is based on a non-linear model and tackles the problem as a whole: the period value is inferred from the scheduling decisions. The proposed approaches have been tested on a number of non-trivial synthetic instances and on a set of realistic industrial instances achieving good results on practical size problem.

Exploring the feasibility of integrating water issues into the CAPRI model

Although numerous modelling efforts have integrated food and water considerations at the farm or river basin level, very few agro-economic models are able to jointly assess water and food policies at the global level. The present report explores the feasibility of integrating water considerations into the CAPRI model. First, a literature review of modelling approaches integrating food and water issues has been conducted. Three agro-economic models, IMPACT, WATERSIM and GLOBIOM, have been analysed in detail. In addition, biophysical and hydrological models estimating agricultural water use have also been studied, in particular the global hydrological model WATERGAP and the LISFLOOD model. Thanks to the programming approach of its supply module, CAPRI shows a high potentiality to integrate environmental indicators as well as to enter new resource constraints (land potentially irrigated, irrigation water) and input-output relationships. At least in theory, the activity-based approach of the regional programming model in CAPRI allows differentiating between rainfed and irrigated activities. The suggested approach to include water into the CAPRI model involves creating an irrigation module and a water use module. The development of the CAPRI water module will enable to provide scientific assessment on agricultural water use within the EU and to analyze agricultural pressures on water resources. The feasibility of the approach has been tested in a pilot case study including two NUTS 2 regions (Andalucia in Spain and Midi-Pyrenees in France). Preliminary results are presented, highlighting the interrelations between water and agricultural developments in Europe. As a next step, it is foreseen to further develop the CAPRI water module to account for competition between agricultural and non-agricultural water use. This will imply building a water use sub-module to compute water use balances.

A performance assessment method for hospitals:the case of municipal hospitals in Angola

Over 60% of the recurrent budget of the Ministry of Health (MoH) in Angola is spent on the operations of the fixed health care facilities (health centres plus hospitals). However, to date, no study has been attempted to investigate how efficiently those resources are used to produce health services. Therefore the objectives of this study were to assess the technical efficiency of public municipal hospitals in Angola; assess changes in productivity over time with a view to analyzing changes in efficiency and technology; and demonstrate how the results can be used in the pursuit of the public health objective of promoting efficiency in the use of health resources. The analysis was based on a 3-year panel data from all the 28 public municipal hospitals in Angola. Data Envelopment Analysis (DEA), a non-parametric linear programming approach, was employed to assess the technical and scale efficiency and productivity change over time using Malmquist index.The results show that on average, productivity of municipal hospitals in Angola increased by 4.5% over the period 2000-2002; that growth was due to improvements in efficiency rather than innovation. © 2008 Springer Science+Business Media, LLC.