Finite element approximation of elliptic control problems with constraints on the gradient

We consider an elliptic optimal control problem with control constraints and pointwise bounds on the gradient of the state. We present a tailored finite element approximation to this optimal control problem, where the cost functional is approximated by a sequence of functionals which are obtained by discretizing the state equation with the help of the lowest order Raviart–Thomas mixed finite element. Pointwise bounds on the gradient variable are enforced in the elements of the triangulation. Controls are not discretized. Error bounds for control and state are obtained in two and three space dimensions. A numerical example confirms our analytical findings.     

Convergence of the control parameterization Ritz method for nonlinear optimal control problems

This paper studies the local convergence properties of the control parameterization Ritz method in which the control variable is approximated over a finite-dimensional subspace. The nonlinear free-endpoint optimal control problem is considered, and error bounds are derived for both the cost functional and state-control convergence. Explicit error bounds are obtained for the particular case of approximations over spline spaces. On specializing the general results to the linear-quadratic regulator problem, global convergence results are obtained. Computational results supporting the theoretically derived error bounds are presented.This research was supported by the University Grants Committee of New Zealand.     

Cost efficiency measurement with price uncertainty: a DEA application to bank branch assessments

This paper enhances cost efficiency measurement methods to account for different scenarios relating to input price information. These consist of situations where prices are known exactly at each decision making unit (DMU) and situations with incomplete price information. The main contribution of this paper consists of the development of a method for the estimation of upper and lower bounds for the cost efficiency (CE) measure in situations of price uncertainty, where only the maximal and minimal bounds of input prices can be estimated for each DMU. The bounds of the CE measure are obtained from assessments in the light of the most favourable price scenario (optimistic perspective) and the least favourable price scenario (pessimistic perspective). The assessments under price uncertainty are based on extensions to the Data Envelopment Analysis (DEA) model that incorporate weight restrictions of the form of input cone assurance regions. The applicability of the models developed is illustrated in the context of the analysis of bank branch performance. The results obtained in the case study showed that the DEA models can provide robust estimates of cost efficiency even in situations of price uncertainty.     

D.C. programming approach for multicommodity network optimization problems with step increasing cost functions

We address a class of particularly hard-to-solve combinatorial optimization problems, namely that of multicommodity network optimization when the link cost functions are discontinuous step increasing. Unlike usual approaches consisting in the development of relaxations for such problems (in an equivalent form of a large scale mixed integer linear programming problem) in order to derive lower bounds, our d.c.(difference of convex functions) approach deals with the original continuous version and provides upper bounds. More precisely we approximate step increasing functions as closely as desired by differences of polyhedral convex functions and then apply DCA (difference of convex function algorithm) to the resulting approximate polyhedral d.c. programs. Preliminary computational experiments are presented on a series of test problems with structures similar to those encountered in telecommunication networks. They show that the d.c. approach and DCA provide feasible multicommodity flows x ^* such that the relative differences between upper bounds (computed by DCA) and simple lower bounds r:=(f(x^*)-LB)/{f(x^*)} lies in the range [4.2 %, 16.5 %] with an average of 11.5 %, where f is the cost function of the problem and LB is a lower bound obtained by solving the linearized program (that is built from the original problem by replacing step increasing cost functions with simple affine minorizations). It seems that for the first time so good upper bounds have been obtained.     

Undiscounted approximations of discounted regenerative models

This paper approximates the discounted average cost in regenerative models by an undiscounted average cost. A financial holding cost is assessed on expenditures that are incurred earlier than the middle of each cycle. A financial variability cost that depends on the variability of the cycle time is also assessed. Explicit upper and lower bounds on the approximation are obtained in the deterministic case. Application to the EOQ model is made.     

Bounds for an Optimization Problem with a Linear Programming Structure

The problem of estimating the value of a quadratic cost indexminimized with respect to a linear system constraint arisesin many design studies in control theory and regression analysis.In particular, the assessment of several choices of system inputscould lead to inefficient procedures based on the executionof an optimization routine for each input subset. To avoid suchpitfalls, a set of bounds on the optimal cost have been constructedusing information resident in a set of system moments. The momentsare easily calculated for systems in weighting function formand the bounds obtained from explicit formulae. The derivationof these bounds is presented in some detail using Hilbert spaceanalysis to obtain a canonical form, and randomized solutionsto give the subsequent bound formulae. A simple example is presentedto illustrate the results.     

A hybrid heuristic for the diameter constrained minimum spanning tree problem

We propose a hybrid GRASP and ILS based heuristic for the diameter constrained minimum spanning tree problem. The latter typically models network design applications where, under a given quality requirement, all vertices must be connected at minimum cost. An adaptation of the one time tree heuristic is used to build feasible diameter constrained spanning trees. Solutions thus obtained are then attempted to be improved through local search. Four different neighborhoods are investigated, in a scheme similar to VND. Upper bounds within 2% of optimality were obtained for problems in two test sets from the literature. Additionally, upper bounds stronger than those previously obtained in the literature are reported for OR-Library instances.     

Cost efficiency measures in data envelopment analysis with data uncertainty

This paper extends the classical cost efficiency (CE) models to include data uncertainty. We believe that many research situations are best described by the intermediate case, where some uncertain input and output data are available. In such cases, the classical cost efficiency models cannot be used, because input and output data appear in the form of ranges. When the data are imprecise in the form of ranges, the cost efficiency measure calculated from the data should be uncertain as well. So, in the current paper, we develop a method for the estimation of upper and lower bounds for the cost efficiency measure in situations of uncertain input and output data. Also, we develop the theory of efficiency measurement so as to accommodate incomplete price information by deriving upper and lower bounds for the cost efficiency measure. The practical application of these bounds is illustrated by a numerical example.     

On lower bound updates in primal potential reduction methods for linear programming

We present a procedure for computing lower bounds for the optimal cost in a linear programming problem. Whenever the procedure succeeds, it finds a dual feasible slack and the associated duality gap. Although no projective transformations or problem restatements are used, the method coincides with the procedures by Todd and Burrell and by de Ghellinck and Vial when these procedures are applicable. The procedure applies directly to affine potential reduction algorithms, and improves on existent techniques for finding lower bounds.     

THE SHIFTED-INVERSE POWER WEAK GALERKIN METHOD FOR EIGENVALUE PROBLEMS

This paper proposes and analyzes a new weak Galerkin method for the eigenvalue problem by using the shifted-inverse power technique. A high order lower bound can be obtained at a relatively low cost via the proposed method. The error estimates for both eigenvalue and eigenfunction are provided and asymptotic lower bounds are shown as well under some conditions. Numerical examples are presented to validate the theoretical analysis.     

The effect of redundancy on probability bounds

Lower bounds on the probability of a union obtained by applying optimal bounds to subsets of events can provide excellent bounds. Comparisons are made with bounds obtained by linear programming and in the cases considered, the best bound is obtained with a subset that contains no redundant events contributing to the union. It is shown that redundant events may increase or decrease the value of a lower bound but surprisingly even removal of a non-redundant event can increase the bound.     

Robust network design in telecommunications under polytope demand uncertainty

We consider a model for robust network design in telecommunications, in which we minimize the cost of the maximum mismatch between supply and demand. In the present study, the demand is uncertain and takes its values in a polytope defined by constraints. This problem is hardly tractable, so we limit ourselves to computing lower bounds (by a column-generation mechanism) and upper bounds (using an algorithm due to Falk and Soland for maximizing a separable convex function over a polytope). The experimental gap obtained turns out to be large, and this seems to be mainly due to poor upper bounds. Two possible solutions are suggested for further research aimed at improving them: dc optimization (to minimize the difference of two convex functions) and AARC modeling (affinely adjustable robust counterpart).     

Efficient Solution of the Single-item,Capacitated Lot-sizing Problem with Start-up and Reservation Costs

A capacitated dynamic lot-sizing model, where the costs incurred are a start-up cost for switching the production facility on and another reservation cost for keeping the facility on, whether or not it is producing, is considered. The resulting scheduling problem is NP-hard. An efficient shortest path model of the uncapacitated version of the problem is developed. This model is then included, via a redefinition of variables, into a tight capacitated model; tight in the sense that sharp lower bounds can be produced from it. The lower bound problems are solved efficiently by recovering the shortest path structure through column generation, and effective upper bounds are generated by solving a small capacitated trans-shipment problem. The results of computational tests to verify the computational efficiency of the resulting solution scheme are presented.     

Optimizing cost flows by edge cost and capacity upgrade

We examine a network upgrade problem for cost flows. A budget can be distributed among the arcs of the network. An investment on each single arc can be used either to decrease the arc flow cost, or to increase the arc capacity, or both. The goal is to maximize the flow through the network while not exceeding bounds on the budget and on the total flow cost.

The problems are NP-hard even on series-parallel graphs. We provide an approximation algorithm on series-parallel graphs which, for arbitrary δ,>0, produces a solution which exceeds the bounds on the budget and the flow cost by factors of at most 1+δ and 1+, respectively, while the amount of flow is at least that of an optimum solution. The running time of the algorithm is polynomial in the input size and 1/(δ). In addition we give an approximation algorithm on general graphs applicable to problem instances with small arc capacities.     

Sharp bounds on the volume fractions of two materials in a two-dimensional body from electrical boundary measurements: the translation method

We deal with the problem of estimating the volume of inclusions using a small number of boundary measurements in electrical impedance tomography. We derive upper and lower bounds on the volume fractions of inclusions, or more generally two phase mixtures, using two boundary measurements in two dimensions. These bounds are optimal in the sense that they are attained by certain configurations with some boundary data. We derive the bounds using the translation method which uses classical variational principles with a null Lagrangian. We then obtain necessary conditions for the bounds to be attained and prove that these bounds are attained by inclusions inside which the field is uniform. When special boundary conditions are imposed the bounds reduce to those obtained by Milton and these in turn are shown here to reduce to those of Capdeboscq–Vogelius in the limit when the volume fraction tends to zero. The bounds of this article, and those of Milton, work for inclusions of arbitrary volume fractions. We then perform some numerical experiments to demonstrate how good these bounds are.     

Long-term staffing based on qualification profiles

Manpower still is one of the most expensive resources, in spite of increasing automation. While employee scheduling and rostering has been the topic of extensive research over the past decades, usually it is assumed that the demand for staff is either given or can be obtained without difficulty. In this research we provide an integer programming model for long-term staffing decisions which fits to the needs of manufacturing-to-order companies. The model is based on qualification profiles, the number of which grows exponentially in terms of the number of processes considered. In order to compute tight lower bounds we provide a column generation technique. The subproblem is a shortest path problem in a network where the arcs have multiple weights. Upper bounds, that is, feasible solutions are calculated by means of local search. We present computational results for randomly generated instances and empirical results for examples from practice. The results show that substantial cost savings can be achieved.     

Bounds for the reliability functions of coherent systems with heterogeneous components

The computation of the reliability function of a (complex) coherent system is a difficult task. Hence, sometimes, we should simply work with some bounds (approximations). The computation of these bounds has been widely studied in the case of coherent systems with independent and identically distributed (IID) components. However, few results have been obtained in the case of heterogeneous (non ID) components. In this paper, we derive explicit bounds for systems with heterogeneous (independent or dependent) components. Also some stochastic comparisons are obtained. Some illustrative examples are included where we compare the different bounds proposed in the paper.     

Dynamic parametric bounds on efficient outcomes in interactive multiple criteria decision making problems

Bounds on efficient outcomes in interactive multiple criteria decision making problems are derived. Bounds are dynamic, i.e., they become stronger with the growing number of explicitly identified outcomes. They are also parametric with respect to weighting coefficients. Computational cost to calculate bounds is negligible.Bounds of the sort offer a breakthrough for prohibitive size and/or solution time bottlenecks by allowing a decision maker to interact with an approximation of the underlying mathematical model rather the model itself.Possible applications of bounds to existing interactive decision making algorithms are discussed. Illustrative numerical examples are given.     

New Linear Program Performance Bounds for Queueing Networks

We obtain new linear programs for bounding the performance and proving the stability of queueing networks. They exploit the key facts that the transition probabilities of queueing networks are shift invariant on the relative interiors of faces and the cost functions of interest are linear in the state. A systematic procedure for choosing different quadratic functions on the relative interiors of faces to serve as surrogates of the differential costs in an inequality relaxation of the average cost function leads to linear program bounds. These bounds are probably better than earlier known bounds. It is also shown how to incorporate additional features, such as the presence of virtual multi-server stations to further improve the bounds. The approach also extends to provide functional bounds valid for all arrival rates.     

Bounds on the value of information in uncertain decision problems II†

In most stochastic decision problems one has the opportunity to collect information that would partially or totally eliminate the inherent uncertainty. One wishes to compare the cost and value of such information in terms of the decision maker's preferences to determine an optimal information gathering plan. The calculation of the value of information generally involves oneor more stochastic recourse problems as well as one or more expected value distribution problems. The difficulty and costs of obtaining solutions to these problems has led to a focus on the development of upper and lower bounds on the various subproblems that yield bounds on the value of information. In this paper we discuss published and new bounds for static problems with linear and concave preference functions for partial and perfect information. We also provide numerical examples utilizing simple production and investment problems that illustrate the calculations involved in the computation of the various bounds and provide a setting for a comparison of the bounds that yields some tentative guidelines for their use. The bounds compared are the Jensen's Inequality bound,the Conditional Jensen's Inequality bound and the Generalized Jensen and Edmundson-Madansky bounds.