Sensitivity Analysis Based Method for Optimal Road Network Pricing

Road pricing is an important economic measure for optimal management of transportation networks. The optimization objectives can be the total travel time or total cost incurred by all the travelers, or some other environmental objective such as minimum emission of dioxide, an so on. Suppose a certain toll is posed on some link on the network, this will give an impact on flows over the whole network and brings about a new equilibrium state. An equilibrium state is a state of traffic network at which no traveler could decrease the perceived travel cost by unilaterally changing the route. The aim of the toll setting is to achieve such an equilibrium state that a certain objective function is optimized. The problem can be formulated as a mathematical program with equilibrium constraints (MPEC). A key step for solving such a MPEC problem is the sensitivity analysis of traffic flows with respect to the change of link characteristics such as the toll prices. In this paper a sensitivity analysis based method is proposed for solving optimal road pricing problems.     

A hybrid inexact-stochastic water management model

An inexact-stochastic water management (ISWM) model is proposed and applied to a case study of water quality management within an agricultural system. The model is based on an inexact chance-constrained programming (ICCP) method, which improves upon the existing inexact and stochastic programming approaches by allowing both distribution information in B and uncertainties in A and C to be effectively incorporated within its optimization process. In its solution process, the ICCP model (under a given pi level) is first transformed into two deterministic submodels, which correspond to the upper and lower bounds for the desired objective function value. This transformation process is based on an interactive algorithm, which is different from normal interval analysis or best/worst case analysis. Interval solutions, which are feasible and stable in the given decision space, can then be obtained by solving the two submodels sequentially. Thus, decision alternatives can be generated by adjusting decision variable values within their solution intervals. The obtained ICCP solutions are also useful for decision makers to obtain insight regarding tradeoffs between environmental and economic objectives and between increased certainties and decreased safeties (or increased risks). Results of the case study indicate that useful solutions for the planning of agricultural activities in the water quality management system have been obtained. A number of decision alternatives have been generated and analyzed based on projected applicable conditions. Generally, some alternatives can be considered when water quality objective is given priority, while the others may provide compromises between environmental and economic considerations. The above alternatives represent various options between environmental and economic tradeoffs. Willingness to accept low agricultural income will guarantee meeting the water quality objectives. A strong desire to acquire high agricultural income will run into the risk of violating water quality constraints.     

A derivative algorithm for inexact quadratic program – application to environmental decision-making under uncertainty

Inexact quadratic programming (IQP) is an extension of conventional quadratic programming for handling both nonlinearities in cost objectives and uncertainties with modeling parameters. It has been a useful tool for environmental systems analysis. However, inefficiency in its solution method has existed, leading to difficulties in its practical application. In this study, a derivative algorithm (DAM) is proposed for solving the IQP. It improves upon the existing method through provision of a quantitative expression for uncertain relationships between the quadratic objective function and the decision variables. The DAM requires much lower computational efforts than the existing algorithm, which is especially meaningful for the IQP's application to large-scale problems. The developed DAM is applied to a hypothetical problem of municipal solid waste management and planning. Detailed solution steps are provided to clearly demonstrate the method's advantages.     

An Ant Colony Optimization Algorithm for the Minimum Weight Vertex Cover Problem

Given an undirected graph and a weighting function defined on the vertex set, the minimum weight vertex cover problem is to find a vertex subset whose total weight is minimum subject to the premise that the selected vertices cover all edges in the graph. In this paper, we introduce a meta-heuristic based upon the Ant Colony Optimization (ACO) approach, to find approximate solutions to the minimum weight vertex cover problem. In the literature, the ACO approach has been successfully applied to several well-known combinatorial optimization problems whose solutions might be in the form of paths on the associated graphs. A solution to the minimum weight vertex cover problem however needs not to constitute a path. The ACO algorithm proposed in this paper incorporates several new features so as to select vertices out of the vertex set whereas the total weight can be minimized as much as possible. Computational experiments are designed and conducted to study the performance of our proposed approach. Numerical results evince that the ACO algorithm demonstrates significant effectiveness and robustness in solving the minimum weight vertex cover problem.     

Peaceman–Rachford splitting for a class of nonconvex optimization problems

We study the applicability of the Peaceman–Rachford (PR) splitting method for solving nonconvex optimization problems. When applied to minimizing the sum of a strongly convex Lipschitz differentiable function and a proper closed function, we show that if the strongly convex function has a large enough strong convexity modulus and the step-size parameter is chosen below a threshold that is computable, then any cluster point of the sequence generated, if exists, will give a stationary point of the optimization problem. We also give sufficient conditions guaranteeing boundedness of the sequence generated. We then discuss one way to split the objective so that the proposed method can be suitably applied to solving optimization problems with a coercive objective that is the sum of a (not necessarily strongly) convex Lipschitz differentiable function and a proper closed function; this setting covers a large class of nonconvex feasibility problems and constrained least squares problems. Finally, we illustrate the proposed algorithm numerically.     

Set covering-based surrogate approach for solving sup-{\mathcal{T}} equation constrained optimization problems

This work considers solving the sup-T{\mathcal{T}} equation constrained optimization problems from the integer programming viewpoint. A set covering-based surrogate approach is proposed to solve the sup-T{\mathcal{T}} equation constrained optimization problem with a separable and monotone objective function in each of the variables. This is our first trial of developing integer programming-based techniques to solve sup-T{\mathcal{T}} equation constrained optimization problems. Our computational results confirm the efficiency of the proposed method and show its potential for solving large scale sup-T{\mathcal{T}} equation constrained optimization problems.     

A block coordinate gradient descent method for regularized convex separable optimization and covariance selection

We consider a class of unconstrained nonsmooth convex optimization problems, in which the objective function is the sum of a convex smooth function on an open subset of matrices and a separable convex function on a set of matrices. This problem includes the covariance selection problem that can be expressed as an ℓ ₁-penalized maximum likelihood estimation problem. In this paper, we propose a block coordinate gradient descent method (abbreviated as BCGD) for solving this class of nonsmooth separable problems with the coordinate block chosen by a Gauss-Seidel rule. The method is simple, highly parallelizable, and suited for large-scale problems. We establish global convergence and, under a local Lipschizian error bound assumption, linear rate of convergence for this method. For the covariance selection problem, the method can terminate in O(n³/e){O(n^3/\epsilon)} iterations with an e{\epsilon}-optimal solution. We compare the performance of the BCGD method with the first-order methods proposed by Lu (SIAM J Optim 19:1807–1827, 2009; SIAM J Matrix Anal Appl 31:2000–2016, 2010) for solving the covariance selection problem on randomly generated instances. Our numerical experience suggests that the BCGD method can be efficient for large-scale covariance selection problems with constraints.     

Environmental site evaluation of waste management facilities embedded into EUGÈNE model: A multicriteria approach

EUGÈNE is a sophisticated mixed integer linear programming model developed to help regional decision makers on long-term planning for solid waste management activities. The model removes almost every limitations encountered in other waste management models and contains a large quantity of variables and constraints. The method used to embed waste management environmental parameters in the EUGÈNE model consists in building global impact index (GII) for all site/facility combinations. First, an environmental and spatial evaluation of waste management facilities over sites is based on qualitative and quantitative criteria measuring biophysical and social impacts. Spatial analysis is carried out by geographical information system routines. Then, a multicriteria analysis ranks all site/facility combinations, according to their global performance based on all criteria. The net flow, computed by the PROMETHEE multicriteria outranking method, is considered as a GII to be embedded into EUGÈNE. The model objective function is thus modified to minimize total system cost and GII. Some practical results obtained for the City of Montreal are discussed.     

An infeasible interior-point algorithm for solving primal and dual geometric programs

In this paper an algorithm is presented for solving the classical posynomial geometric programming dual pair of problems simultaneously. The approach is by means of a primal-dual infeasible algorithm developed simultaneously for (i) the dual geometric program after logarithmic transformation of its objective function, and (ii) its Lagrangian dual program. Under rather general assumptions, the mechanism defines a primal-dual infeasible path from a specially constructed, perturbed Karush-Kuhn-Tucker system.Subfeasible solutions, as described by Duffin in 1956, are generated for each program whose primal and dual objective function values converge to the respective primal and dual program values. The basic technique is one of a predictor-corrector type involving Newton’s method applied to the perturbed KKT system, coupled with effective techniques for choosing iterate directions and step lengths. We also discuss implementation issues and some sparse matrix factorizations that take advantage of the very special structure of the Hessian matrix of the logarithmically transformed dual objective function. Our computational results on 19 of the most challenging GP problems found in the literature are encouraging. The performance indicates that the algorithm is effective regardless of thedegree of difficulty, which is a generally accepted measure in geometric programming. Research supported in part by the University of Iowa Obermann Fellowship and by NSF Grant DDM-9207347.     

An interval-parameter fuzzy nonlinear optimization model for stream water quality management under uncertainty

Planning for water quality management systems is complicated by a variety of uncertainties and nonlinearities, where difficulties in formulating and solving the resulting inexact nonlinear optimization problems exist. With the purpose of tackling such difficulties, this paper presents the development of an interval-fuzzy nonlinear programming (IFNP) model for water quality management under uncertainty. Methods of interval and fuzzy programming were integrated within a general framework to address uncertainties in the left- and right-hand sides of the nonlinear constraints. Uncertainties in water quality, pollutant loading, and the system objective were reflected through the developed IFNP model. The method of piecewise linearization was developed for dealing with the nonlinearity of the objective function. A case study for water quality management planning in the Changsha section of the Xiangjiang River was then conducted for demonstrating applicability of the developed IFNP model. The results demonstrated that the accuracy of solutions through linearized method normally rises positively with the increase of linearization levels. It was also indicated that the proposed linearization method was effective in dealing with IFNP problems; uncertainties can be communicated into optimization process and generate reliable solutions for decision variables and objectives; the decision alternatives can be obtained by adjusting different combinations of the decision variables within their solution intervals. It also suggested that the linearized method should be used under detailed error analysis in tackling IFNP problems.     

An interval nonlinear program for the planning of waste management systems with economies-of-scale effects—A case study for the region of Hamilton,Ontario, Canada

In practical environmental systems with the effects of economies-of-scale (EOS), most relationships among different system components are nonlinear in nature, which can be described precisely only if a nonlinear model is employed. In this study, an interval nonlinear programming (INLP) model is developed and applied to the planning of a municipal solid waste (MSW) management system with EOS effects on system costs. The INLP has a nonlinear objective function and linear constraints. It handles nonlinearity presented as exponential functions. When exponential term p = 1 (in the INLP’s objective function), the model becomes an interval linear program; when p = 2, it becomes an interval quadratic program. Therefore, the INLP is flexible in reflecting a variety of system complexities. A solution algorithm with satisfactory performance is proposed. Application of the proposed method to the planning of waste management activities in the Hamilton-Wentworth Region, Ontario, Canada, indicated that reasonable solutions have been generated. In general, the INLP model could reflect uncertain and nonlinear characteristics of MSW management systems with EOS effects. The modeling results provided useful decision support for the Region’s waste management activities.     

A conflict analysis approach for illuminating distributional issues in sustainability policy

In the area of environmental and resource management and in policies aiming at sustainable development, conflicting issues and interests are the normal state of affairs. Mathematical approaches cannot of course be a panacea able to resolve all real-world conflicts; but they can help to provide more insight into the nature of these conflicts by providing systematic information. Moreover mathematical models are very useful in helping at finding potential social compromises by making a complex situation more transparent to policy-makers and lay people. This is the main objective of the conflict analysis procedure developed here. Distributional issues are taken into consideration by means of an eclectic approach using concepts from land-use planning, fuzzy cluster analysis and social choice. All the various properties presented by the proposed approach are made explicit thus allowing its evaluation on theoretical and empirical grounds. Possible relationships of complementarity or conflictuality with other existing approaches are also discussed briefly. A real-world illustrative example is presented too.     

Fuzzy goal programming for multiobjective transportation problems

Several fuzzy approaches can be considered for solving multiobjective transportation problem. This paper presents a fuzzy goal programming approach to determine an optimal compromise solution for the multiobjective transportation problem. We assume that each objective function has a fuzzy goal. Also we assign a special type of nonlinear (hyperbolic) membership function to each objective function to describe each fuzzy goal. The approach focuses on minimizing the negative deviation variables from 1 to obtain a compromise solution of the multiobjective transportation problem. We show that the proposed method and the fuzzy programming method are equivalent. In addition, the proposed approach can be applied to solve other multiobjective mathematical programming problems. A numerical example is given to illustrate the efficiency of the proposed approach.     

An Algorithm for Solving Multicriterion Linear Programming Problems with Examples

The purpose of this paper is to develop a useful technique for solving linear programmes involving more than one objective function. Motivation for solving multicriterion linear programmes is given along with the inherent difficulty associated with obtaining a satisfactory solution set. By applying a linear programming approach for the solution of two person–zero sum games with mixed strategies, it is shown that a linear optimization problem with multiple objective functions can be formulated in this fashion in order to obtain a solution set satisfying all the requirements for an efficient solution of the problem. The solution method is then refined to take into account disparities between the magnitude of the values generated by each of the objective functions and solution preferences as determined by a decision-maker. A summary of the technique is then given along with several examples in order to demonstrate its applicability.     

On the graphical relaxation of the symmetric traveling salesman polytope

The Graphical Traveling Salesman Polyhedron (GTSP) has been proposed by Naddef and Rinaldi to be viewed as a relaxation of the Symmetric Traveling Salesman Polytope (STSP). It has also been employed by Applegate, Bixby, Chvátal, and Cook for solving the latter to optimality by the branch-and-cut method. There is a close natural connection between the two polyhedra. Until now, it was not known whether there are facets in TT-form of the GTSP polyhedron which are not facets of the STSP polytope as well. In this paper we give an affirmative answer to this question for n ≥ 9. We provide a general method for proving the existence of such facets, at the core of which lies the construction of a continuous curve on a polyhedron. This curve starts in a vertex, walks along edges, and ends in a vertex not adjacent to the starting vertex. Thus there must have been a third vertex on the way.      

An approach based on level set method for void identification of continuum structure with time-domain dynamic response

An approach based on the level set method has been developed to identify the position and geometry of voids in continuum structure using time-domain dynamic response. The level set method is employed in the proposed approach to represent the boundary of the voids implicitly. The voids are identified by solving an optimization problem which minimizes an objective function about the displacement error. The boundary of the voids is evolved by updating the level set function. The shape derivative of the objective function for the time-domain dynamic response is derived and used to construct the velocity field. Then, the level set function is updated through the velocity field. The proposed approach has been applied to several numerical examples of void identification in continuum structure. The results indicate that the proposed approach based on the level set method can identify voids effectively and accurately with time-domain dynamic response. Moreover, the effects of measure points, excitation force, noise, void distribution, numerical error, element size and boundary conditions on the approach are studied. Meanwhile, the computational costs of some examples are provided.     

The Incremental Gauss-Newton Algorithm with Adaptive Stepsize Rule

In this paper, we consider the Extended Kalman Filter (EKF) for solving nonlinear least squares problems. EKF is an incremental iterative method based on Gauss-Newton method that has nice convergence properties. Although EKF has the global convergence property under some conditions, the convergence rate is only sublinear under the same conditions. One of the reasons why EKF shows slow convergence is the lack of explicit stepsize. In the paper, we propose a stepsize rule for EKF and establish global convergence of the algorithm under the boundedness of the generated sequence and appropriate assumptions on the objective function. A notable feature of the stepsize rule is that the stepsize is kept greater than or equal to 1 at each iteration, and increases at a linear rate of k under an additional condition. Therefore, we can expect that the proposed method converges faster than the original EKF. We report some numerical results, which demonstrate that the proposed method is promising.     

Global Minimization Algorithms for Holder Functions

This paper deals with the one-dimensional global optimization problem where the objective function satisfies a Hölder condition over a closed interval. A direct extension of the popular Piyavskii method proposed for Lipschitz functions to Hölder optimization requires an a priori estimate of the Hölder constant and solution to an equation of degree N at each iteration. In this paper a new scheme is introduced. Three algorithms are proposed for solving one-dimensional Hölder global optimization problems. All of them work without solving equations of degree N. The case (very often arising in applications) when a Hölder constant is not given a priori is considered. It is shown that local information about the objective function used inside the global procedure can accelerate the search signicantly. Numerical experiments show quite promising performance of the new algorithms.     

A method for analysing operational complexity in supply chains

This paper proposes a method for analysing the operational complexity in supply chains by using an entropic measure based on information theory. The proposed approach estimates the operational complexity at each stage of the supply chain and analyses the changes between stages. In this paper a stage is identified by the exchange of data and/or material. Through analysis the method identifies the stages where the operational complexity is both generated and propagated (exported, imported, generated or absorbed). Central to the method is the identification of a reference point within the supply chain. This is where the operational complexity is at a local minimum along the data transfer stages. Such a point can be thought of as a ‘sink’ for turbulence generated in the supply chain. Where it exists, it has the merit of stabilising the supply chain by attenuating uncertainty. However, the location of the reference point is also a matter of choice. If the preferred location is other than the current one, this is a trigger for management action. The analysis can help decide appropriate remedial action. More generally, the approach can assist logistics management by highlighting problem areas. An industrial application is presented to demonstrate the applicability of the method.     

Optimizing the initial setting of complex adaptive systems–optimizing the layout of initial AFVs stations for maximizing the diffusion of AFVs

There are occasions when people want to optimize the initial setting of a CAS (complex adaptive system) so that it evolves in a desired direction. A CAS evolves by heterogeneous actors interacting with each other. It is difficult to describe the evolution process with an objective function. Researchers usually attempt to optimize an intervening objective function, which is supposed to help a CAS evolve in a desired direction. This article puts forward an approach to optimize the initial setting of a CAS directly (instead of through an intervening objective function) by nesting agent‐based simulations in a genetic algorithm. In the approach, an initial setting of a CAS is treated as a genome, and its fitness is defined by the closeness between the simulation result and the desired evolution. We test the applicability of the proposed approach on the problem of optimizing the layout of initial AFV (alternative fuel vehicle) refueling stations to maximize the diffusion of AFVs. Computation experiments show that the initial setting generated with the approach could better induce the desired evolving result than optimizing an intervening objective function. The idea of the approach can also be applied to other decision making associated with a complex adaptive process. © 2015 Wiley Periodicals, Inc. Complexity 21: 275–290, 2016