Decomposition in large system optimization using the method of multipliers

Although the method of multipliers can resolve the dual gaps which will often appear between the true optimum point and the saddle point of the Lagrangian in large system optimization using the Lagrangian approach, it is impossible to decompose the generalized Lagrangian in a straightforward manner because of its quadratic character. A technique using the linear approximation of the perturbed generalized Lagrangian has recently been proposed by Stephanopoulos and Westerberg for the decomposition. In this paper, another attractive decomposition technique which transforms the nonseparable crossproduct terms into the minimum of sum of separable terms is proposed. The computational efforts required for large system optimization can be much reduced by adopting the latter technique in place of the former, as illustrated by application of these two techniques to an optimization problem of a chemical reactor system.The authors would like to acknowledge the valuable comments given by Professor D. G. Luenberger of Stanford University.     

Branch-and-price approach for the multi-skill project scheduling problem

This work introduces a procedure to solve the multi-skill project scheduling problem (MSPSP) (Néron and Baptista, International symposium on combinatorial, optimization (CO’2002), 2002). The MSPSP mixes both the classical resource constrained project scheduling problem and the multi-purpose machine model. The aim is to find a schedule that minimizes the completion time (makespan) of a project, composed of a set of activities. In addition, precedence relations and resources constraints are considered. In this problem, resources are staff members that master several skills. Thus, a given number of workers must be assigned to perform each skill required by an activity. Practical applications include the construction of buildings, as well as production and software development planning. We present a column generation approach embedded within a branch-and-price (B&P) procedure that considers a given activity and time-based decomposition approach. Obtained results show that the proposed B&P procedure is able to reach optimal solutions for several small and medium sized instances in an acceptable computational time. Furthermore, some previously open instances were optimally solved.     

A Decomposition Methodology Applied to the Multi-Area Optimal Power Flow Problem

This paper describes a decomposition methodology applied to the multi-area optimal power flow problem in the context of an electric energy system. The proposed procedure is simple and efficient, and presents some advantages with respect to other common decomposition techniques such as Lagrangian relaxation and augmented Lagrangian decomposition. The application to the multi-area optimal power flow problem allows the computation of an optimal coordinated but decentralized solution. The proposed method is appropriate for an Independent System Operator in charge of the electric energy system technical operation. Convergence properties of the proposed decomposition algorithm are described and related to the physical coupling between the areas. Theoretical and numerical results show that the proposed decentralized methodology has a lower computational cost than other decomposition techniques, and in large large-scale cases even lower than a centralized approach.     

Decomposition approaches in permutation scheduling problems with application to the M-machine flow shop scheduling problems

In this article, we consider three decomposition techniques for permutation scheduling problems. We introduce a general iterative decomposition algorithm for permutation scheduling problems and apply it to the permutation flow shop scheduling problem. We also develop bounds needed for this iterative decomposition approach and compare its computational requirements to that of the traditional branch and bound algorithms. Two heuristic algorithms based on the iterative decomposition approach are also developed. extensive numerical study indicates that the heuristic algorithms are practical alternatives to very costly exact algorithms for large flow shop scheduling problems.     

Differential equations for the analytic singular value decomposition of a matrix

Summary This paper is concerned with finding a smooth singular value decomposition for a matrix which is smoothly dependent on a parameter. A previous approach to this problem was based on minimisation techniques, here, in contrast, a system of ordinary differential equations is derived for the decomposition. It is shown that the numerical solution of an initial value problem associated with these differential equations provides a feasible approach to the solution of this problem. Particular consideration is given to the situation which arises with equal modulus singular values which lead to indeterminacies in the evaluations needed for the numerical solution. Examples which illustrate the behaviour of the method are included.     

A tabu search algorithm applied to the staffing roster problem of Leicestershire police force

This paper presents an application of the tabu search algorithm to a staff rostering problem relevant to Leicestershire Police. The aim is to address the issue of structuring staff rosters to enable effective use of staff to meet the demand on the Police to reduce and deal with crime-related incidents. This problem is defined through the compilation of a time-varying level of required staff and an associated staff roster. The objective is an optimised work set-up, maximising staff resources and the meeting of demand. Optimisation of staff levels to demand is sought through use of a series of tabu search algorithms, making use of two diversification techniques and an intensification technique individually and in compilation. The tabu search is shown to be a well-suited optimisation approach to the type of problem defined, with individual conclusions drawn for each of the technique combinations used.     

Modelling and optimization of carbon-in-pulp gole recovery processs

The paper presents a mixed-integer nonlinear programming (MINLP)approach to construction and operational optimization of carbon-in-pulp(CIP) processes related to hydrometallurgical gold recoveryplants. In this plant section, gold in the form of aurocyanidecomplex ions is adsorbed on the active sites of carbon particles.This takes place in a series of agitated tanks where carbonis countercurrently transferred with respect to the pulp. Threebasic process operating modes are reported and analysed: namelycarousel, continuous, and sequential. The mathematical modelof the CIP process is developed for each one of the operatingmodes examined. Economic evaluation is carried out proposingthe sum of annual gold loss to the tailings plus the total annualcost as a minimization object subject to constraints dictatedby the process model. The original problem is suitably decomposedinto a series of nonlinear programming problems and solved withsuccessive quadratic programming techniques. A characteristiccase study is presented to demonstrate the effectiveness ofthe proposed method.     

A Stochastic Analysis of a Staffing Problem

Consider an organization with several categories of staff, each having a specified number of members. The age of entry into service and the age of retirement are both specified. Withdrawals occur at time-independent rates. Under this set-up, the authors have computed the maximum ages at which promotions should take place, assuming that the staff members continuing at various ages are random. Some illustrative calculations have been carried out.     

组织内部员工信息安全胜任评价模型

针对内部员工信息安全胜任评价这一重要问题,在分析内部信息攻击行为的特点及全面总结胜任特征相关研究成果的基础上,构建了内部员工信息安全胜任特征评价指标体系,在此基础上提出了组织内部员工信息安全胜任特征评价模型。模型基于安全风险防范思想,将评价环节分为两个环节,综合考虑了决策者制定决策偏好和候选员工的个性优势,更实际地反映了候选员工间的差别。最后通过案例分析验证了该评价模型的有效性和实用性。     

A constraint generation scheme to probabilistic linear problems with an application to power system expansion planning

In this paper, we first describe a constraint generation scheme for probabilistic mixed integer programming problems. Next, we present a decomposition approach to the peak capacity expansion planning of interconnected hydrothermal generating systems, with bounds on the transmission capacity between the regions. The objective is to minimize investments in generating units and interconnection links, subject to constraints on supply reliability. The problem is formulated as a stochastic integer program. The constraint generation scheme, which is similar to Benders decomposition, is applied in the solution of the peak capacity expansion problem. The master problem in this decomposition scheme is an integer program, solved by implicit enumeration. The operating subproblem corresponds to a stochastic network flow problem, and is solved by a maximum flow algorithm and Monte Carlo simulation. The approach is illustrated through a case study involving the expansion of the system of the Brazilian Southeastern region.     

Connecting a population dynamic model with a multi-period location-allocation problem for post-disaster relief operations

In this study, we propose a mathematical model and heuristics for solving a multi-period location-allocation problem in post-disaster operations, which takes into account the impact of distribution over the population. Logistics restrictions such as human and financial resources are considered. In addition, a brief review on resilience system models is provided, as well as their connection with quantitative models for post-disaster relief operations. In particular, we highlight how one can improve resilience by means of OR/MS strategies. Then, a simpler resilience schema is proposed, which better reflects an active system for providing humanitarian aid in post-disaster operations, similar to the model focused in this work. The proposed model is non-linear and solved by a decomposition approach: the master level problem is addressed by a non-linear solver, while the slave subproblem is treated as a black-box coupling heuristics and a Variable Neighborhood Descent local search. Computational experiments have been done using several scenarios, and real data from Belo Horizonte city in Brazil.     

Fixed Charge Transportation Problems: a new heuristic approach based on Lagrangean relaxation and?the?solving of core problems

In this paper the Fixed Charge Transportation Problem is considered. A new heuristic approach is proposed, based on the intensive use of Lagrangean relaxation techniques. The more novel aspects of this approach are new Lagrangean relaxation and decomposition methods, the consideration of several core problems, defined from the previously computed Lagrangean reduced costs, the heuristic selection of the most promising core problem and the final resort to enumeration by applying a branch and cut algorithm to the selected core problem. For problems with a small ratio of the average fixed cost to the average variable cost (lower than or equal to 25), the proposed method can obtain similar or better solutions than the state-of-art algorithms, such as the tabu search procedure and the parametric ghost image processes. For larger ratios (between 50 and 180), the quality of the obtained solutions could be considered to be halfway between both methods.     

Lagrangian Relaxation and the Single-Source Capacitated Facility-Location Problem

Lagrangian relaxation has been widely used in solving a number of hard combinatorial optimization problems. The success of the approach depends on the structure of the problem and on the values assigned to the Lagrange multipliers. A recent paper on the single-source capacitated facility-location problem proposed the use of Lagrangian relaxation in which the capacity constraints were relaxed. In this paper, a class of such problems is defined for which the proposed relaxation is guaranteed to result in an infeasible solution, irrespective of the values assigned to the Lagrange multipliers. In these cases, the bounds on the optimal solution, obtained from the relaxation, are generally poor. It is concluded that, when using Lagrangian relaxation, it may be worthwhile carrying out a preliminary analysis to determine the potential viability of the approach before extensive development takes place.     

Existence of Three Solutions for a Degenerate Kirchhoff–Type Transmission Problem

In this article, we establish the existence of three weak solutions for a nonlinear transmission problem involving degenerate nonlocal coefficients of p(x)–Kirchhoff–type. Our approach is of variational nature; the weak formulation takes place in suitable variable exponent Sobolev spaces.     

Efficient decomposition and linearization methods for the stochastic transportation problem

The stochastic transportation problem can be formulated as a convex transportation problem with nonlinear objective function and linear constraints. We compare several different methods based on decomposition techniques and linearization techniques for this problem, trying to find the most efficient method or combination of methods. We discuss and test a separable programming approach, the Frank-Wolfe method with and without modifications, the new technique of mean value cross decomposition and the more well known Lagrangean relaxation with subgradient optimization, as well as combinations of these approaches. Computational tests are presented, indicating that some new combination methods are quite efficient for large scale problems.     

On computation of real eigenvalues of matrices via the Adomian decomposition

The problem of matrix eigenvalues is encountered in various fields of engineering endeavor. In this paper, a new approach based on the Adomian decomposition method and the Faddeev-Leverrier’s algorithm is presented for finding real eigenvalues of any desired real matrices. The method features accuracy and simplicity. In contrast to many previous techniques which merely afford one specific eigenvalue of a matrix, the method has the potential to provide all real eigenvalues. Also, the method does not require any initial guesses in its starting point unlike most of iterative techniques. For the sake of illustration, several numerical examples are included.     

Delamination of Unidirectional Viscoelastic Composite Materials

The delamination of unidirectional composite materials takes place under compression along the reinforcing elements and often occurs near the free surfaces or planes of these materials. The first investigation in this field was made in 1976 and since then numerous studies have been carried out. However, the approaches developed in these investigations are applicable only to time-independent composite materials. In the present paper, an approach for investigating unidirectional viscoelastic composite materials is proposed, with a particular problem as an example. The investigations are performed within the framework of exact three-dimensional geometrically nonlinear equations of viscoelasticity theory.     

A geometric analysis of the Lagerstrom model problem

Lagerstrom's model problem is a classical singular perturbation problem which was introduced to illustrate the ideas and subtleties involved in the analysis of viscous flow past a solid at low Reynolds number by the method of matched asymptotic expansions. In this paper the corresponding boundary value problem is analyzed geometrically by using methods from the theory of dynamical systems, in particular invariant manifold theory. As an essential part of the dynamics takes place near a line of non-hyperbolic equilibria, a blow-up transformation is introduced to resolve these singularities. This approach leads to a constructive proof of existence and local uniqueness of solutions and to a better understanding of the singular perturbation nature of the problem. In particular, the source of the logarithmic switchback phenomenon is identified.     

Evaluation of staffing policies in Markov manpower systems and their extension to organizations with outsource personnel

This paper takes up the problem of the evaluation of manpower policies followed in an organization, and examines it in relation to the career growth facilitation afforded by the system to its members. The method proposes and constructs a quantitative measure of effectiveness for manpower policies based on the career growth facilitation afforded to the members, which can then be used for comparative evaluation of different policies. The models are then extended to organizations which outsource work through outsource manpower, and which seek to control the blend of internal and outsource manpower. The models and analyses developed herein will be of relevance to all manpower systems, and in particular, to organizations which outsource work, and those that attempt to achieve desired blends of the outsource staff with their own.     

Adaptation as a Morphing Process: A Methodology for the Design and Evaluation of Adaptive Organizational Structures

Changes in objectives, in resources, or in the environment may necessitate the adaptation of an organization from one form to another. However, in many cases, the organizations need to continue functioning while adaptation takes place, i.e., it is not possible to stop the organizational activity in order to reorganize, and then start again. In this case, adaptation can be expressed as a morphing process in which the organization transitions from one form with its attendant task allocation to a different one through a series of incremental steps that preserve overall functionality and performance. Coordination between organization members during adaptation is critical. A computational model for this type of organizational adaptation at the operational level is presented. The model is implemented using the Colored Petri Net formulation of discrete event dynamical systems. A design methodology that utilizes this model is outlined and a simple example is used to illustrate the approach.