The shortest augmenting path method for solving assignment problems — Motivation and computational experience

In this paper we discuss the shortest augmenting path method for solving assignment problems in the following respect:

we introduce this basic concept using matching theory

we present several efficient labeling techniques for constructing shortest augmenting paths

we show the relationship of this approach to several classical assignment algorithms

we present extensive computational experience for complete problems, and

we show how postoptimal analysis can be performed using this approach and naturally leads to a new, highly efficient hybrid approach for solving large-scale dense assignment problems

     

On the computation of all solutions of jointly convex generalized Nash equilibrium problems

Jointly convex generalized Nash equilibrium problems are the most studied class of generalized Nash equilibrium problems. For this class of problems it is now clear that a special solution, called variational or normalized equilibrium, can be computed by solving a variational inequality. However, the computation of non-variational equilibria is more complex and less understood and only very few methods have been proposed so far. In this note we consider a new approach for the computation of non-variational solutions of jointly convex problems and compare our approach to previous proposals.     

Existence of Positive Solutions for Higher Order Boundary Value Problem on Time Scales

In this paper,we investigate the existence of positive solutions of a class higher order boundary value problems on time scales.The class of boundary value problems educes a four-point(or three-point or two-point) boundary value problems,for which some similar results are established.Our approach relies on the Krasnosel’skii fixed point theorem.The result of this paper is new and extends previously known results.     

Systems of sandwich pairs

The variational approach for solving nonlinear problems eventually leads to the search for critical points of related functionals. In case of semibounded functionals, one can look for extrema. Otherwise, one is forced to use other methods. In this paper we apply a new approach which is successful in solving a large class of problems. Applications are given. To Felix Browder on the occasion of his eightieth birthday     

Games,Critical Paths and Assignment Problems in Permutation Flow Shops and Cyclic Scheduling Flow Line Environments

In this paper we address the non-pre-emptive flow shop scheduling problem for makespan minimization in a new modelling framework. A lower bound generation scheme is developed by using appropriately defined linear assignment problems and, based on this new approach, a special class of permutation flow shop problems is identified. We present a game theoretic interpretation of our modelling approach which leads to an integer programming formulation of the scheduling problem. A new branch and bound scheme is developed based on these results. The major advantage of our modelling framework and branch-and- bound approach is that it can be easily extended to address a general class of cyclic scheduling problems for production flow lines with blocking. After a discussion of this extension, we report on computational experience that indicates the very satisfactory performance of the new optimal solution procedure for cyclic scheduling problems with finite capacity buffers.     

New Direct Numerical Methods for Some Multidimensional Problems of the Calculus of Variations

In this paper, we develop a new approach to the design of direct numerical methods for multidimensional problems of the calculus of variations. The approach is based on a transformation of the problem with the use of a new class of Sobolev-like spaces that is studied in the article. This transformation allows one to analytically compute the direction of steepest descent of the main functional of the calculus of variations with respect to a certain inner product, and, in turn, to construct new direct numerical methods for multidimensional problems of the calculus of variations. In the end of the paper, we point out how the approach developed in the article can be extended to the case of problems with more general boundary conditions, problems for functionals depending on higher order derivatives, and problems with isoperimetric and/or pointwise constraints.     

A polynomially searchable exponential neighbourhood for graph colouring

In this paper, we develop a new graph colouring strategy. Our heuristic is an example of a so-called polynomially searchable exponential neighbourhood approach. The neighbourhood is that of permutations of the colours of vertices of a subgraph. Our approach provides a solution method for colouring problems with edge weights. Results for initial tests on unweighted K-colouring benchmark problems are presented. Our colour permutation move was found in practice to be too slow to justify its use on these problems. By contrast, our implementation of iterative descent, which incorporates a permutation kickback move, performed extremely well. Moreover, our approach may yet prove valuable for weighted K-colouring. In addition, our approach offers an improved measure of the distance between colourings of a graph.     

An Estimation of Exact Penalty for Infinite-Dimensional Inequality-Constrained Minimization Problems

We use the penalty approach in order to study inequality-constrained minimization problems in infinite dimensional spaces. A penalty function is said to have the exact penalty property if there is a penalty coefficient for which a solution of an unconstrained penalized problem is a solution of the corresponding constrained problem. In this paper we consider a large class of inequality-constrained minimization problems for which a constraint is a mapping with values in a normed ordered space. For this class of problems we introduce a new type of penalty functions, establish the exact penalty property and obtain an estimation of the exact penalty. Using this exact penalty property we obtain necessary and sufficient optimality conditions for the constrained minimization problems.     

On proximal gradient method for the convex problems regularized with the group reproducing kernel norm

We consider a class of nonsmooth convex optimization problems where the objective function is the composition of a strongly convex differentiable function with a linear mapping, regularized by the group reproducing kernel norm. This class of problems arise naturally from applications in group Lasso, which is a popular technique for variable selection. An effective approach to solve such problems is by the proximal gradient method. In this paper we derive and study theoretically the efficient algorithms for the class of the convex problems, analyze the convergence of the algorithm and its subalgorithm.     

The Neumann problem of an elliptic equation with strong resonance

In the present paper, we consider a class of strong resonance problems for nonlinear elliptic Neumann BVPs, and establish existence and multiplicity results for positive, negative and sign-changing solutions by using a Morse theoretical approach.     

Numerical transformation methods: a constructive approach

Within group invariance theory we consider a constructive approach in order to define numerical transformation methods. These are initial-value methods for the solution of boundary value problems governed by ordinary differential equations. Here we consider the class of free boundary value problems governed by the most general second-order equation in normal form. For this class of problems the main theorem is concerned with the definition of an iterative transformation method. The definition of a noniterative method, applicable to a subclass of the original class of problems, follows as a corollary. Therefore, the proposed constructive approach allows us to establish a unifying framework for noniterative and iterative transformation methods.     

An Approximate Exact Penalty in Constrained Vector Optimization on Metric Spaces

In this paper, we use the penalty approach in order to study a class of constrained vector minimization problems on complete metric spaces. A penalty function is said to have the generalized exact penalty property iff there is a penalty coefficient for which approximate solutions of the unconstrained penalized problem are close enough to approximate solutions of the corresponding constrained problem. For our class of problems, we establish the generalized exact penalty property and obtain an estimation of the exact penalty.     

Selective Search for Global Optimization of Zero or Small Residual Least-Squares Problems: A Numerical Study

In this paper, we consider approximating global minima of zero or small residual, nonlinear least-squares problems. We propose a selective search approach based on the concept of selective minimization recently introduced in Zhang et al. (Technical Report TR99-12, Rice University, Department of Computational and Applied Mathematics MS-134, Houston, TX 77005, 1999). To test the viability of the proposed approach, we construct a simple implementation using a Levenberg-Marquardt type method combined with a multi-start scheme, and compare it with several existing global optimization techniques. Numerical experiments were performed on zero residual nonlinear least-squares problems chosen from structural biology applications and from the literature. On the problems of significant sizes, the performance of the new approach compared favorably with other tested methods, indicating that the new approach is promising for the intended class of problems.     

Using metaheuristic compromise programming for the solution of multiple-objective scheduling problems

In this paper, we propose a generic approach to find compromise solutions for multiple-objective scheduling problems using metaheuristics. As an illustration, we present a new hybrid tabu search/variable neighbourhood search application of this approach for the solution of a bi-objective scheduling problem. Through numerical experiments we demonstrate its efficiency and effectiveness. We have confirmed that compromise programming with the tabu-VNS metaheuristic generates solutions that approach those of the known reference sets.     

An exact penalty approach to constrained minimization problems on metric spaces

In this paper we use the penalty approach in order to study a class of constrained minimization problems on complete metric spaces. A penalty function is said to have the generalized exact penalty property if there is a penalty coefficient for which approximate solutions of the unconstrained penalized problem are close enough to approximate solutions of the corresponding constrained problem. For our class of problems we establish the generalized exact penalty property and obtain an estimation of the exact penalty.     

Strongly damped wave problems: Bootstrapping and regularity of solutions

The aim of the article is to present a unified approach to the existence, uniqueness and regularity of solutions to problems belonging to a class of second order in time semilinear partial differential equations in Banach spaces. Our results are applied next to a number of examples appearing in literature, which fall into the class of strongly damped semilinear wave equations. The present work essentially extends the results on the existence and regularity of solutions to such problems. Previously, these problems have been considered mostly within the Hilbert space setting and with the main part operators being selfadjoint. In this article we present a more general approach, involving sectorial operators in reflexive Banach spaces.     

On a class of ill-posed non-linear integral equations arising in the interpretation of indirect measurements

In this paper we consider a class of specific Urysohn integral equations for which the solutions are only determined with the exception of rearrangements of function values and associated arguments. As an alternative to Tikhonov's regularization method approximating minimum-norm solutions for this ill-posed class of inverse problems, a constrained least-squares approach is presented. This approach is aimed at finding decreasing rearrangements serving as appropriate solution representatives. It is shown that the inverses of these decresing solutions solve a Fredholm linear integral equation of the first kind.     

Exact penalty property for a class of inequality-constrained minimization problems

We use the penalty approach in order to study constrained minimization problems. A penalty function is said to have the exact penalty property if there is a penalty coefficient for which a solution of an unconstrained penalized problem is a solution of the corresponding constrained problem. In this paper we establish the exact penalty property for a large class of inequality-constrained minimization problems.     

SDP reformulation for robust optimization problems based on nonconvex QP duality

In a real situation, optimization problems often involve uncertain parameters. Robust optimization is one of distribution-free methodologies based on worst-case analyses for handling such problems. In this paper, we first focus on a special class of uncertain linear programs (LPs). Applying the duality theory for nonconvex quadratic programs (QPs), we reformulate the robust counterpart as a semidefinite program (SDP) and show the equivalence property under mild assumptions. We also apply the same technique to the uncertain second-order cone programs (SOCPs) with “single” (not side-wise) ellipsoidal uncertainty. Then we derive similar results on the reformulation and the equivalence property. In the numerical experiments, we solve some test problems to demonstrate the efficiency of our reformulation approach. Especially, we compare our approach with another recent method based on Hildebrand’s Lorentz positivity.     

Generalized compound matrix method

In this work we demonstrate how the extension of the Evans function method using the compound matrix approach can be implemented to undertake the stability analysis (normally done through numerical means) of nonlinear travelling waves. The main advantage of this approach is that it can easily overcome the stiffness which is normally associated with these kinds of problems. We present a general approach which allows this method to be used for a general class of nonlinear travelling wave problems.