Incomplete Dynamic Backtracking for Linear Pseudo-Boolean Problems

Many combinatorial problems can be modeled as 0/1 integer linear programs. Problems expressed in this form are usually solved by Operations Research algorithms, but good results have also been obtained using generalised SAT algorithms based on backtracking or local search, after transformation to pseudo-Boolean form. A third class of SAT algorithm uses non-systematic backtracking to combine constraint propagation with local search-like scalability, at the cost of completeness. This paper describes such an algorithm for pseudo-Boolean models. Experimental results on a variety of problems are encouraging, in some cases yielding improved solutions or performance compared to previous algorithms.     

On the Solution of Min-sum-min Problems

One class of min-sum-min problems is discussed in the paper. Min-sum-min problems appear in a natural way in many applications (e.g., in cluster analysis, pattern recognition, classification theory etc.). Like min-max-min problems, min-sum-min problems represent a very important family of nonsmooth problems. Problems of this type can be treated by means of the existing tools of Nonsmooth Analysis. However, most of algorithms available provide a local minimizer only, since they are based on necessary conditions which are of local nature. In the paper it is proved that the original problem can be reduced to the problem of minimizing a finite number of sum-functions. A necessary condition for a global minimum and a sufficient condition for a local minimum are stated. The necessary condition is of nonlocal nature. An algorithm (so-called Exchange algorithm) for finding points, satisfying necessary conditions, is described. An ɛ-Exchange algorithm is formulated, allowing, in principle, to escape from a ‘shallow’ local minimizer. An example is presented to illustrate the results and algorithms. An application of the proposed algorithms to solving one clustering problem is also given. Numerical results are provided.AMS Subject Classification:90C30, 49J40.     

Problems

This column will carry problems arising in the design of algorithms for discrete problems.Problems are solicited in all areas of algorithm design that are covered byJournal of Algorithms. Some of the problems that appear here may also appear in the “Open Problems” column inSIGACT News. Problems should be submitted to me at the Department of Computer Science, University of Maryland, College Park, MD 20742 (E-mail: samir@cs.umd.edu), and if chosen, will appear in this column. I hope that there will be enough submissions to run this column twice a year. Problem submissions should be precise and succinct. Proposals for guest columns, focusing on problems in a specific research area, are also welcome.Especially welcome are algorithmic problems arising in areas not previously explored by the theoretical computer science community.I have taken over this column from Professor Peter van Emde Boas and I thank him for his efforts in running the column over the past few years.     

Rollout Algorithms for Stochastic Scheduling Problems

Stochastic scheduling problems are difficult stochastic control problems with combinatorial decision spaces. In this paper we focus on a class of stochastic scheduling problems, the quiz problem and its variations. We discuss the use of heuristics for their solution, and we propose rollout algorithms based on these heuristics which approximate the stochastic dynamic programming algorithm. We show how the rollout algorithms can be implemented efficiently, with considerable savings in computation over optimal algorithms. We delineate circumstances under which the rollout algorithms are guaranteed to perform better than the heuristics on which they are based. We also show computational results which suggest that the performance of the rollout policies is near-optimal, and is substantially better than the performance of their underlying heuristics.     

A cutting plane algorithm for semi-definite programming problems with applications to failure discriminant analysis

We will propose a new cutting plane algorithm for solving a class of semi-definite programming problems (SDP) with a small number of variables and a large number of constraints. Problems of this type appear when we try to classify a large number of multi-dimensional data into two groups by a hyper-ellipsoidal surface. Among such examples are cancer diagnosis, failure discrimination of enterprises. Also, a certain class of option pricing problems can be formulated as this type of problem. We will show that the cutting plane algorithm is much more efficient than the standard interior point algorithms for solving SDP.     

一类min-max-min问题的区间算法

讨论了一类由一阶连续可微函数构成的无约束min-max-min问题．通过构造目标函数的区间扩张、无解区域删除原则，建立了求解min-max-min问题的区间算法，证明了算法的收敛性，给出了数值算例．理论证明和数值结果表明方法是可靠和有效的．     

Probabilistic asymptotic properties of some combinatorial optimization problems

A class of combinatorial optimization problems with sum- and bottleneck objective function is described, having the following probabilistic asymptotic behaviour: With probability tending to one the ratio between worst and optimal objective function value approaches one as the size of the problem tends to infinity.Problems belonging to this class are among others quadratic assignment problems, as well as certain combinatorial and graph theoretical optimization problems.The obtained results suggest that even very simple heuristic algorithms incline to yield good solutions for high dimensional problems of this class.     

Problems

This section contains problems and solutions in the design and analysis of algorithms.Problems are solicited in all areas covered by this journal and will be selected for inclusion on the basis of their originality and ability to illustrate fundamental concepts in algorithmic thinking. The submission of exercises from well-known textbooks is not acceptable. Also inappropriate are problems whose statements are excessively long, or vague; and those which use several ad hoc definitions and/or very complex notation. If actual code is to be part of a problem, then an Algol-like syntax is preferred. Proposers should make their problems as precise and unambiguous as possible. Aim for clarity and succinctness.It is expected that a proposer will supply all information relevant to a problem and justifying its interest. Such information will most often include a solution to the problem, or perhaps some special cases. Other background material, such as references of related literature, is especially important for problems submitted without solutions. Well-known unsolved problems are unacceptable. An asterisk before a problem, or part thereof, indicates that neither the proposer nor the editor supplied a solution.Readers wishing to submit problems and/or solutions should observe the following guidelines: All correspondence must be typewritten and submitted in duplicate.Please address all correspondence concerning this section to Peter van Emde Boas, Departments of Mathematics and Computer Science, University of Amsterdam, Plantage Muidergracht 24, 1018 TV Amsterdam, the Netherlands.A number of problems in the Journal of Algorithms will be cross listed in the Bulletin of the European Association for Theoretical Computer Science (BEATCS), and vice versa. Problems listed below whose source is the above Bulletin will be marked by having the initials EATCS appended to the problem number. Such material is reprinted with permission from the BEATCS.The deadline for solutions to the proposed problems is December 31, 1992.     

Efficient Algorithms for Variants of Weighted Matching and Assignment Problems

Obtaining a matching in a graph satisfying a certain objective is an important class of graph problems. Matching algorithms have received attention for several decades. However, while there are efficient algorithms to obtain a maximum weight matching, not much is known about the maximum weight maximum cardinality, and maximum cardinality maximum weight matching problems for general graphs. Our contribution in this work is to show that for bounded weight input graphs one can obtain an algorithm for both maximum weight maximum cardinality (for real weights), and maximum cardinality maximum weight matching (for integer weights) by modifying the input and running the existing maximum weight matching algorithm. Also, given the current state of the art in maximum weight matching algorithms, we show that, for bounded weight input graphs, both maximum weight maximum cardinality, and maximum cardinality maximum weight matching have algorithms of similar complexities to that of maximum weight matching. Subsequently, we also obtain approximation algorithms for maximum weight maximum cardinality, and maximum cardinality maximum weight matching.      

On the convergence of cutting plane algorithms for a class of nonconvex mathematical programs

We discuss the convergence of cutting plane algorithms for a class of nonconvex programs called the Generalized Lattice Point Problems (GLPP). A set of sufficient conditions which guarantee finite convergence are presented. Although these conditions are usually difficult to enforce in a practical implementation, they do illustrate the various factors that must be involved in a convergent rudimentary cutting plane algorithm. A striking example of nonconvergence (in which no subsequence converges to a feasible solution, even when seemingly strong cutting planes are used), is presented to show the effect of neglecting one such factor. We give an application of our analysis to problems with multiple choice constraints and finally discuss a modification of cutting plane algorithms so as to make finite convergence more readily implementable.     

Two Classes of Smooth Objective Penalty Functions for Constrained Problems

This research aims at solving constrained problems by providing two classes of objective penalty functions which respectively approach to a class of exact penalty functions smoothly. Meanwhile, the authors present two algorithms based on the two objective penalty functions, and give the conclusion that all of the cluster points of the two sequences generated by the two algorithms are the optimal points of the original problem. Furthermore, this article discusses that both of the two penalty functions are of well-condition. Finally, the authors report numerical results to show the applicability of the two presented algorithms.     

Discrete Approximations to Continuum Optimal Flow Problems

Problems in partial differential equations with inequality constraints can be used to describe a continuum analog to various optimal flow/cut problems. While general concepts from convex optimization (like duality) carry over into continuum problems, the application of ideas and algorithms from linear programming and network flow problems is challenging. The capacity constraints are nonlinear (but convex).
In this article, we investigate a discretized version of the planar maximum flow problem that preserves the nonlinear capacity constraints of the continuum problem. The resulting finite-dimensional problem can be cast as a second-order cone programming problem or a quadratically constrained program. Good numerical results can be obtained using commercial solvers. These results are in agreement with the continuum theory of a "challenge" problem posed by Strang.     

Auxiliary Principle and Algorithm for Mixed Equilibrium Problems and Bilevel Mixed Equilibrium Problems in Banach Spaces

A new class of bilevel mixed equilibrium problems is introduced and studied in real Banach spaces. By using the auxiliary principle technique, new iterative algorithms for solving the mixed equilibrium problems and bilevel mixed equilibrium problems are suggested and analyzed. Strong convergence of the iterative sequences generated by the algorithms is proved under suitable conditions. The behavior of the solution set of the bilevel mixed equilibrium problem is also discussed.     

A Branch and Bound Algorithm for Solving Low Rank Linear Multiplicative and Fractional Programming Problems

This paper is concerned with a practical algorithm for solving low rank linear multiplicative programming problems and low rank linear fractional programming problems. The former is the minimization of the sum of the product of two linear functions while the latter is the minimization of the sum of linear fractional functions over a polytope. Both of these problems are nonconvex minimization problems with a lot of practical applications. We will show that these problems can be solved in an efficient manner by adapting a branch and bound algorithm proposed by Androulakis–Maranas–Floudas for nonconvex problems containing products of two variables. Computational experiments show that this algorithm performs much better than other reported algorithms for these class of problems.     

Uniformly Convergent Multigrid Methods for Convection–Diffusion Problems without Any Constraint on Coarse Grids

We construct a class of multigrid methods for convection–diffusion problems. The proposed algorithms use first order stable monotone schemes to precondition the second order standard Galerkin finite element discretization. To speed up the solution process of the lower order schemes, cross-wind-block reordering of the unknowns is applied. A V-cycle iteration, based on these algorithms, is then used as a preconditioner in GMRES. The numerical examples show that this method is convergent without imposing any constraint on the coarsest grid and the convergence of the preconditioned method is uniform.     

Soft Constraint Logic Programming and Generalized Shortest Path Problems

In this paper we study the relationship between Constraint Programming (CP) and Shortest Path (SP) problems. In particular, we show that classical, multicriteria, partially ordered, and modality-based SP problems can be naturally modeled and solved within the Soft Constraint Logic Programming (SCLP) framework, where logic programming is coupled with soft constraints. In this way we provide this large class of SP problems with a high-level and declarative linguistic support whose semantics takes care of both finding the cost of the shortest path(s) and also of actually finding the path(s). On the other hand, some efficient algorithms for certain classes of SP problems can be exploited to provide some classes of SCLP programs with an efficient way to compute their semantics.     

Medi-centre Location Problems

In this paper we consider two medi-centre location problems. One is the m-medi-centre problem in which we add to the m-median problem uniform distance constraints. The other problem is the uncapacitated medi-centre facility location problem where we include the fixed costs of establishing the facilities and thus the number of facilities is also a decision variable. For the two problems we present algorithms and discuss computational experience.     

On Complexity of the Translational-Cut Algorithm for Convex Minimax Problems

Burke, Goldstein, Tseng, and Ye (Ref. 1) have presented an interesting interior-point algorithm for a class of smooth convex minimax problems. They have also presented a complexity analysis leading to a worst-case bound on the total work necessary to obtain a solution within a prescribed tolerance. In this paper, we present refinements to the analysis of Burke et al. which show that the resulting complexity bound can be worse than those for other algorithms available at the time Ref. 1 was published.     

A Fast Algorithm for Two-Dimensional Elliptic Problems

In this paper, we extend the work of Daripa et al. [14–16,7] to a larger class of elliptic problems in a variety of domains. In particular, analysis-based fast algorithms to solve inhomogeneous elliptic equations of three different types in three different two-dimensional domains are derived. Dirichlet, Neumann and mixed boundary value problems are treated in all these cases. Three different domains considered are: (i) interior of a circle, (ii) exterior of a circle, and (iii) circular annulus. Three different types of elliptic problems considered are: (i) Poisson equation, (ii) Helmholtz equation (oscillatory case), and (iii) Helmholtz equation (monotone case). These algorithms are derived from an exact formula for the solution of a large class of elliptic equations (where the coefficients of the equation do not depend on the polar angle when written in polar coordinates) based on Fourier series expansion and a one-dimensional ordinary differential equation. The performance of these algorithms is illustrated for several of these problems. Numerical results are presented.     

A piecewise-linearized algorithm based on the Krylov subspace for solving stiff ODEs

Numerical methods for solving Ordinary Differential Equations (ODEs) have received considerable attention in recent years. In this paper a piecewise-linearized algorithm based on Krylov subspaces for solving Initial Value Problems (IVPs) is proposed. MATLAB versions for autonomous and non-autonomous ODEs of this algorithm have been implemented. These implementations have been compared with other piecewise-linearized algorithms based on Padé approximants, recently developed by the authors of this paper, comparing both precisions and computational costs in equal conditions. Four case studies have been used in the tests that come from stiff biology and chemical kinetics problems. Experimental results show the advantages of the proposed algorithms, especially when the dimension is increased in stiff problems.