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 .     

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.     

Speedup estimates for some variants of the parallel implementations of the branch-and-bound method

The efficiency of parallel implementations of the branch-and-bound method in discrete optimization problems is considered. A theoretical analysis and comparison of two parallel implementations of this method is performed. A mathematical model of the computation process is constructed and used to obtain estimates of the maximum possible speedup. Examples of problems in which none of these two parallel implementations can speed up the computations are considered.     

Semiconvergence in distribution of random closed sets with application to random optimization problems

The paper considers upper semicontinuous behavior in distribution of sequences of random closed sets. Semiconvergence in distribution will be described via convergence in distribution of random variables with values in a suitable topological space. Convergence statements for suitable functions of random sets are proved and the results are employed to derive stability statements for random optimization problems where the objective function and the constraint set are approximated simultaneously. The author is grateful to two anonymous referees for helpful suggestions.     

The statement and numerical solution of an optimization problem in X-ray tomography

A nonclassical problem is considered for the transport equation with coefficients depending on the energy of radiation. The task is to find the discontinuity surfaces for the coefficients of the equation from measurements of the radiation flux leaving the medium. For this tomography problem, an optimization problem is stated and numerically analyzed. The latter consists in determining the radiation energy that ensures the best reconstruction of the unknown medium. A simplified optimization problem is solved analytically.     

开关布局中本质不同的开关线路计算

通过对开关布局问题的研究，来解决一类象开关线路一样比较特殊，比较复杂的布局优化问题。从而寻找出这类问题的全局优化算法。本应用对称群对集合的作用，轨道，不动点等讨论了开关布局问题，给出了本质不同的开关线路个数的计算公式。     

Shape sensitivity of a plane crack front

The 3D‐elasticity model of a solid with a plane crack under the stress‐free boundary conditions at the crack is considered. We investigate variations of a solution and of energy functionals with respect to perturbations of the crack front in the plane. The corresponding expansions at least up to the second‐order terms are obtained. The strong derivatives of the solution are constructed as an iterative solution of the same elasticity problem with specified right‐hand sides. Using the expansion of the potential and surface energy, we consider an approximate quadratic form for local shape optimization of the crack front defined by the Griffith criterion. To specify its properties, a procedure of discrete optimization is proposed, which reduces to a matrix variational inequality. At least for a small load we prove its solvability and find a quasi‐static model of the crack growth depending on the loading parameter. Copyright © 2003 John Wiley & Sons, Ltd.