On PDE solution in transient optimization of gas networks

Operative planning in gas distribution networks leads to large-scale mixed-integer optimization problems involving a hyperbolic PDE defined on a graph. We consider the NLP obtained under prescribed combinatorial decisions—or as relaxation in a branch-and-bound framework, addressing in particular the KKT systems arising in primal–dual interior methods. We propose a custom solution algorithm using sparse projections locally in time, based on the KKT systems’ structural properties in space as induced by the discretized gas flow equations in combination with the underlying network topology. The numerical efficiency and accuracy of the algorithm are investigated, and detailed computational comparisons with a previously developed control space method and with the multifrontal solver MA27 are provided.     

A likelihood-MPEC approach to target classification

In this paper we develop a method for classifying an unknown data vector as belonging to one of several classes. This method is based on the statistical methods of maximum likehood and borrowed strength estimation. We develop an MPEC procedure (for Mathematical Program with Equilibrium Constraints) for the classification of a multi-dimensional observation, using a finite set of observed training data as the inputs to a bilevel optimization problem. We present a penalty interior point method for solving the resulting MPEC and report numerical results for a multispectral minefield classification application. Related approaches based on conventional maximum likehood estimation and a bivariate normal mixture model, as well as alternative surrogate classification objective functions, are described. Received: October 26, 1998 / Accepted: June 11, 2001?Published online March 24, 2003 RID="***" ID="***"The authors of this work were all partially supported by the Wright Patterson Air Force Base via Veda Contract F33615-94-D-1400. The first and third author were also supported by the National Science Foundation under grant DMS-9705220. RID="*" ID="*"The work of this author was based on research supported by the U.S. National Science Foundation under grant CCR-9624018. RID="**" ID="**"The work of this author was supported by the Office of Naval Research under grant N00014-95-1-0777.     

Distribution sensitivity in stochastic programming

In this paper, stochastic programming problems are viewed as parametric programs with respect to the probability distributions of the random coefficients. General results on quantitative stability in parametric optimization are used to study distribution sensitivity of stochastic programs. For recourse and chance constrained models quantitative continuity results for optimal values and optimal solution sets are proved (with respect to suitable metrics on the space of probability distributions). The results are useful to study the effect of approximations and of incomplete information in stochastic programming.This research was presented in parts at the 4th International Conference on Stochastic Programming held in Prague in September 1986.     

Assessing solution quality in stochastic programs

Determining whether a solution is of high quality (optimal or near optimal) is fundamental in optimization theory and algorithms. In this paper, we develop Monte Carlo sampling-based procedures for assessing solution quality in stochastic programs. Quality is defined via the optimality gap and our procedures' output is a confidence interval on this gap. We review a multiple-replications procedure that requires solution of, say, 30 optimization problems and then, we present a result that justifies a computationally simplified single-replication procedure that only requires solving one optimization problem. Even though the single replication procedure is computationally significantly less demanding, the resulting confidence interval might have low coverage probability for small sample sizes for some problems. We provide variants of this procedure that require two replications instead of one and that perform better empirically. We present computational results for a newsvendor problem and for two-stage stochastic linear programs from the literature. We also discuss when the procedures perform well and when they fail, and we propose using ɛ-optimal solutions to strengthen the performance of our procedures.     

Efficient sample sizes in stochastic nonlinear programming

We consider a class of stochastic nonlinear programs for which an approximation to a locally optimal solution is specified in terms of a fractional reduction of the initial cost error. We show that such an approximate solution can be found by approximately solving a sequence of sample average approximations. The key issue in this approach is the determination of the required sequence of sample average approximations as well as the number of iterations to be carried out on each sample average approximation in this sequence. We show that one can express this requirement as an idealized optimization problem whose cost function is the computing work required to obtain the required error reduction. The specification of this idealized optimization problem requires the exact knowledge of a few problems and algorithm parameters. Since the exact values of these parameters are not known, we use estimates, which can be updated as the computation progresses. We illustrate our approach using two numerical examples from structural engineering design.     

An interior point multiplicative method for optimization under positivity constraints

We analyze an algorithm for the problem minf(x) s.t.x 0 suggested, without convergence proof, by Eggermont. The iterative step is given by x _j ^k+1 =x _j ^k (1-_kf(x ^k)_j) with _k > 0 determined through a line search. This method can be seen as a natural extension of the steepest descent method for unconstrained optimization, and we establish convergence properties similar to those known for steepest descent, namely weak convergence to a KKT point for a generalf, weak convergence to a solution for convexf and full convergence to the solution for strictly convexf. Applying this method to a maximum likelihood estimation problem, we obtain an additively overrelaxed version of the EM Algorithm. We extend the full convergence results known for EM to this overrelaxed version by establishing local Fejér monotonicity to the solution set.Research for this paper was partially supported by CNPq grant No 301280/86.     

An obstruction to the positivity of relative Yamabe invariants

For a supergroup , we describe an obstruction to the existence of positive scalar curvature metrics with minimal boundary condition on a compact n-dimensional -manifold W with nonempty boundary M, , in terms of the bordism class [M] in the Stolz obstruction group associated to [St2]. In par ticular, when W is a 5-dimensional spin manifold and the -invariant of a connected component of M is nonzero, we prove that W does not admit a positive scalar curvature metric with minimal boundary condition. Received: 4 July 2001; in final form: 5 February 2002 / Published online: 8 November 2002 RID="*" ID="*" Partially supported by the Grants-in-Aid for Scientific Research (C), Japan Society for the Promotion of Science, No. 11640070.     

A Simply Constrained Optimization Reformulation of KKT Systems Arising from Variational Inequalities

The Karush—Kuhn—Tucker (KKT) conditions can be regarded as optimality conditions for both variational inequalities and constrained optimization problems. In order to overcome some drawbacks of recently proposed reformulations of KKT systems, we propose casting KKT systems as a minimization problem with nonnegativity constraints on some of the variables. We prove that, under fairly mild assumptions, every stationary point of this constrained minimization problem is a solution of the KKT conditions. Based on this reformulation, a new algorithm for the solution of the KKT conditions is suggested and shown to have some strong global and local convergence properties. Accepted 10 December 1997     

Upper bounds for Gaussian stochastic programs

We present a construction which gives deterministic upper bounds for stochastic programs in which the randomness appears on the right–hand–side and has a multivariate Gaussian distribution. Computation of these bounds requires the solution of only as many linear programs as the problem has variables. Received December 2, 1997 / Revised version received January 5, 1999? Published online May 12, 1999     

Hybrid Metaheuristics for the Vehicle Routing Problem with Stochastic Demands

This article analyzes the performance of metaheuristics on the vehicle routing problem with stochastic demands (VRPSD). The problem is known to have a computationally demanding objective function, which could turn to be infeasible when large instances are considered. Fast approximations of the objective function are therefore appealing because they would allow for an extended exploration of the search space. We explore the hybridization of the metaheuristic by means of two objective functions which are surrogate measures of the exact solution quality. Particularly helpful for some metaheuristics is the objective function derived from the traveling salesman problem (TSP), a closely related problem. In the light of this observation, we analyze possible extensions of the metaheuristics which take the hybridized solution approach VRPSD-TSP even further and report about experimental results on different types of instances. We show that, for the instances tested, two hybridized versions of iterated local search and evolutionary algorithm attain better solutions than state-of-the-art algorithms.     

Convergent adaptive finite elements for the nonlinear Laplacian

Summary. The numerical solution of the homogeneous Dirichlet problem for the p-Laplacian, , is considered. We propose an adaptive algorithm with continuous piecewise affine finite elements and prove that the approximate solutions converge to the exact one. While the algorithm is a rather straight-forward generalization of those for the linear case p=2, the proof of its convergence is different. In particular, it does not rely on a strict error reduction. Received December 29, 2000 / Revised version received August 30, 2001 / Published online December 18, 2001 RID="*" ID="*" Current address: Dipartimento di Matematica, Università degli Studi di Milano, Via C. Saldini 50, 20133 Milano, Italy; e-mail: veeser@mat.unimi.it     

Modeling languages and Condor: metacomputing for optimization

A generic framework is postulated for utilizing the computational resources provided by a metacomputer to concurrently solve a large number of optimization problems generated by a modeling language. An example of the framework using the Condor resource manager and the AMPL and GAMS modeling languages is provided. A mixed integer programming formulation of a feature selection problem from machine learning is used to test the mechanism developed. Due to this application’s computational requirements, the ability to perform optimizations in parallel is necessary in order to obtain results within a reasonable amount of time. Details about the simple and easy to use tool and implementation are presented so that other modelers with applications generating many independent mathematical programs can take advantage of it to significantly reduce solution times. Received: October 28, 1998 / Accepted: December 01, 1999?Published online June 8, 2000     

A primal all-integer algorithm based on irreducible solutions

 This paper introduces an exact primal augmentation algorithm for solving general linear integer programs. The algorithm iteratively substitutes one column in a tableau by other columns that correspond to irreducible solutions of certain linear diophantine inequalities. We prove that various versions of our algorithm are finite. It is a major concern in this paper to show how the subproblem of replacing a column can be accomplished effectively. An implementation of the presented algorithms is given. Computational results for a number of hard 0/1 integer programs from the MIPLIB demonstrate the practical power of the method. Received: April 23, 2001 / Accepted: May 2002 Published online: March 21, 2003 RID="*" ID="*" Supported by grants FKZ 0037KD0099 and FKZ 2495A/0028G of the Kultusministerium of Sachsen-Anhalt. RID="*" ID="*" Supported by grants FKZ 0037KD0099 and FKZ 2495A/0028G of the Kultusministerium of Sachsen-Anhalt. RID="*" ID="*" Supported by grants FKZ 0037KD0099 and FKZ 2495A/0028G of the Kultusministerium of Sachsen-Anhalt. RID="#" ID="#"Supported by a Gerhard-Hess-Preis and grant WE 1462 of the Deutsche Forschungsgemeinschaft, and by the European DONET program TMR ERB FMRX-CT98-0202. Mathematics Subject Classification (1991): 90C10     

Constraint qualifications for optimality conditions and total Lagrange dualities in convex infinite programming

For an inequality system defined by an infinite family of proper convex functions (not necessarily lower semicontinuous), we introduce some new notions of constraint qualifications. Under the new constraint qualifications, we provide necessary and/or sufficient conditions for the KKT rules to hold. Similarly, we provide characterizations for constrained minimization problems to have total Lagrangian dualities. Several known results in the conic programming problem are extended and improved.     

Computational complexity of stable partitions with B-preferences

Consider a special stable partition problem in which the player's preferences over sets to which she could belong are identical with her preferences over the most attractive member of a set and in case of indifference the set of smaller cardinality is preferred. If the preferences of all players over other (individual) players are strict, a strongly stable and a stable partition always exists. However, if ties are present, we show that both the existence problems are NP-complete. These results are very similar to what is known for the stable roommates problem. Received: July 2000/Revised: October 2002 RID="*" ID="*"  This work was supported by the Slovak Agency for Science, contract #1/7465/20 “Combinatorial Structures and Complexity of Algorithms”.