The node-edge weighted 2-edge connected subgraph problem: Linear relaxation, facets and separation

Let G=(V,E) be a undirected k-edge connected graph with weights c_e on edges and w_v on nodes. The minimum 2-edge connected subgraph problem, 2ECSP for short, is to find a 2-edge connected subgraph of G, of minimum total weight. The 2ECSP generalizes the well-known Steiner 2-edge connected subgraph problem. In this paper we study the convex hull of the incidence vectors corresponding to feasible solutions of 2ECSP. First, a natural integer programming formulation is given and it is shown that its linear relaxation is not sufficient to describe the polytope associated with 2ECSP even when G is series-parallel. Then, we introduce two families of new valid inequalities and we give sufficient conditions for them to be facet-defining. Later, we concentrate on the separation problem. We find polynomial time algorithms to solve the separation of important subclasses of the introduced inequalities, concluding that the separation of the new inequalities, when G is series-parallel, is polynomially solvable.     

Integration and propagation of a multi-criteria decision making model in constraint programming

In this paper we propose a general integration scheme for a Multi-Criteria Decision Making model of the Multi-Attribute Utility Theory in Constraint Programming. We introduce the Choquet integral as a general aggregation function for multi-criteria optimization problems and define the Choquet global constraint that propagates this function during the Branch-and-Bound search. Finally the benefits of the propagation of the Choquet constraint are evaluated on the examination timetabling problem.     

A Verified Optimization Technique to Locate Chaotic Regions of Hénon Systems

We present a new verified optimization method to find regions for Hénon systems where the conditions of chaotic behaviour hold. The present paper provides a methodology to verify chaos for certain mappings and regions. We discuss first how to check the set theoretical conditions of a respective theorem in a reliable way by computer programs. Then we introduce optimization problems that provide a model to locate chaotic regions. We prove the correctness of the underlying checking algorithms and the optimization model. We have verified an earlier published chaotic region, and we also give new chaotic places located by the new technique.     

A Constraint Programming Approach to Extract the Maximum Number of Non-Overlapping Test Forms

This paper introduces a novel approach for extracting the maximum number of non-overlapping test forms from a large collection of overlapping test sections assembled from a given item bank. The approach involves solving maximum set packing problems (MSPs). A branch-and-bound MSP algorithm is developed along with techniques adapted from constraint programming to estimate lower and upper bounds on the optimal MSP solution. The algorithm is general and can be applied in other applications including combinatorial auctions. The results of computer simulations and experiments with an operational item bank are presented. An erratum to this article is available at .     

Butyltins in california river and lake marina waters

Butyltins were analyzed in waters from California river and lake marinas and were detected at the part per trillion (ppt) level in most locations. The tributyltin:dibutyltin (TBT/DBT) ratios in the fresh waters were similar to those in their saline counterparts indicating like rates of degradation in the two salinity regimes.     

Artificial time integration

Many recent algorithmic approaches involve the construction of a differential equation model for computational purposes, typically by introducing an artificial time variable. The actual computational model involves a discretization of the now time-dependent differential system, usually employing forward Euler. The resulting dynamics of such an algorithm is then a discrete dynamics, and it is expected to be “close enough” to the dynamics of the continuous system (which is typically easier to analyze) provided that small – hence many – time steps, or iterations, are taken. Indeed, recent papers in inverse problems and image processing routinely report results requiring thousands of iterations to converge. This makes one wonder if and how the computational modeling process can be improved to better reflect the actual properties sought. In this article we elaborate on several problem instances that illustrate the above observations. Algorithms may often lend themselves to a dual interpretation, in terms of a simply discretized differential equation with artificial time and in terms of a simple optimization algorithm; such a dual interpretation can be advantageous. We show how a broader computational modeling approach may possibly lead to algorithms with improved efficiency. AMS subject classification (2000)  65L05, 65M32, 65N21, 65N22, 65D18     

On a Modified Subgradient Algorithm for Dual Problems via Sharp Augmented Lagrangian*

We study convergence properties of a modified subgradient algorithm, applied to the dual problem defined by the sharp augmented Lagrangian. The primal problem we consider is nonconvex and nondifferentiable, with equality constraints. We obtain primal and dual convergence results, as well as a condition for existence of a dual solution. Using a practical selection of the step-size parameters, we demonstrate the algorithm and its advantages on test problems, including an integer programming and an optimal control problem. *Partially Supported by 2003 UniSA ITEE Small Research Grant Ero2. Supported by CAPES, Brazil, Grant No. 0664-02/2, during her visit to the School of Mathematics and Statistics, UniSA.     

On Characterizations of Proper Efficiency for Nonconvex Multiobjective Optimization

In this paper, nonconvex multiobjective optimization problems are studied. New characterizations of a properly efficient solution in the sense of Geoffrion's are established in terms of the stability of one scalar optimization problem and the existence of an exact penalty function of a scalar constrained program, respectively. One of the characterizations is applied to derive necessary conditions for a properly efficient control-parameter pair of a nonconvex multiobjective discrete optimal control problem with linear constraints.     

Global Optimization of Stochastic Black-Box Systems via Sequential Kriging Meta-Models

This paper proposes a new method that extends the efficient global optimization to address stochastic black-box systems. The method is based on a kriging meta-model that provides a global prediction of the objective values and a measure of prediction uncertainty at every point. The criterion for the infill sample selection is an augmented expected improvement function with desirable properties for stochastic responses. The method is empirically compared with the revised simplex search, the simultaneous perturbation stochastic approximation, and the DIRECT methods using six test problems from the literature. An application case study on an inventory system is also documented. The results suggest that the proposed method has excellent consistency and efficiency in finding global optimal solutions, and is particularly useful for expensive systems.     

基于二次插值的非饱和土壤水流问题的特征差分方法及数值模拟

本文针对一类非饱和土壤水流问题,提出了基于二次插值的特征差分格式,得到了严谨的L2模误差估计.并作了数值试验,指明方法的有效性.