An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation

Given a finite set V, and a hypergraph H⊆2^V, the hypergraph transversal problem calls for enumerating all minimal hitting sets (transversals) for H. This problem plays an important role in practical applications as many other problems were shown to be polynomially equivalent to it. Fredman and Khachiyan [On the complexity of dualization of monotone disjunctive normal forms, J. Algorithms 21 (1996) 618-628] gave an incremental quasi-polynomial-time algorithm for solving the hypergraph transversal problem. In this paper, we present an efficient implementation of this algorithm. While we show that our implementation achieves the same theoretical worst-case bound, practical experience with this implementation shows that it can be substantially faster. We also show that a slight modification of the original algorithm can be used to obtain a stronger bound on the running time.More generally, we consider a monotone property π over a bounded n-dimensional integral box. As an important application of the above hypergraph transversal problem, pioneered by Bioch and Ibaraki [Complexity of identification and dualization of positive Boolean functions, Inform. and Comput. 123 (1995) 50-63], we consider the problem of incrementally generating simultaneously all minimal subsets satisfying π and all maximal subsets not satisfying π, for properties given by a polynomial-time satisfiability oracle. Problems of this type arise in many practical applications. It is known that the above joint generation problem can be solved in incremental quasi-polynomial time via a polynomial-time reduction to a generalization of the hypergraph transversal problem on integer boxes. In this paper we present an efficient implementation of this procedure, and present experimental results to evaluate our implementation for a number of interesting monotone properties π.     

The triangular maps with closed sets of periodic points

In a recent paper we provided a characterization of triangular maps of the square, i.e., maps given by F(x,y)=(f(x),gx(y)), satisfying condition (P1) that any chain recurrent point is periodic. For continuous maps of the interval, there is a list of 18 other conditions equivalent to (P1), including (P2) that there is no infinite ω-limit set, (P3) that the set of periodic points is closed and (P4) that any regularly recurrent point is periodic, for instance. We provide an almost complete classification among these conditions for triangular maps, improve a result given by C. Arteaga [C. Arteaga, Smooth triangular maps of the square with closed set of periodic points, J. Math. Anal. Appl. 196 (1995) 987-997] and state an open problem concerning minimal sets of the triangular maps. The paper solves partially a problem formulated by A.N. Sharkovsky in the eighties. The mentioned open problem, the validity of (P4) ⇒ (P3), is related to the question whether some regularly recurrent point lies in the fibres over an f-minimal set possessing a regularly recurrent point. We answered this question in the positive for triangular maps with nondecreasing fiber maps. Consequently, the classification is completed for monotone triangular maps.     

Heuristic constructive algorithms for open shop scheduling to minimize mean flow time

In this paper, we consider the problem of scheduling n jobs on m machines in an open shop environment so that the sum of completion times or mean flow time becomes minimal. For this strongly NP-hard problem, we develop and discuss different constructive heuristic algorithms. Extensive computational results are presented for problems with up to 50 jobs and 50 machines, respectively. The quality of the solutions is evaluated by a lower bound for the corresponding preemptive open shop problem and by an alternative estimate of mean flow time. We observe that the recommendation of an appropriate constructive algorithm strongly depends on the ratio n/m.     

Empirical likelihood inference for the accelerated failure time model

Accelerated failure time (AFT) models are useful regression tools for studying the association between a survival time and covariates. Semiparametric inference procedures have been proposed in an extensive literature. Among these, use of an estimating equation which is monotone in the regression parameter and has some excellent properties was proposed by Fygenson and Ritov (1994). However, there is a serious under-coverage problem for small sample sizes. In this paper, we derive the limiting distribution of the empirical log-likelihood ratio for the regression parameter on the basis of the monotone estimating equations. Furthermore, the empirical likelihood (EL) confidence intervals/regions for the regression parameter are obtained. We conduct a simulation study in order to compare the proposed EL method with the normal approximation method. The simulation results suggest that the empirical likelihood based method outperforms the normal approximation based method in terms of coverage probability. Thus, the proposed EL method overcomes the under-coverage problem of the normal approximation method.     

Monotone iterations for numerical solutions of reaction-diffusion-convection equations with time delay

In this article we use the monotone method for the computation of numerical solutions of a nonlinear reaction-diffusion-convection problem with time delay. Three monotone iteration processes for a suitably formulated finite-difference system of the problem are presented. It is shown that the sequence of iteration from each of these iterative schemes converges from either above or below to a unique solution of the finite-difference system without any monotone condition on the nonlinear reaction function. An analytical comparison result among the three processes of iterations is given. Also given is the application of the iterative schemes to some model problems in population dynamics, including numerical results of a model problem with known analytical solution. © 1998 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 14: 339–351, 1998     

Accelerated monotone iterative methods for finite difference equations of reaction-diffusion

This paper is concerned with numerical methods for a finite difference system of reaction-diffusion-convection equation under nonlinear boundary condition. Various monotone iterative methods are presented, and each of these methods leads to an existence-comparison theorem as well as a computational algorithm for numerical solutions. The monotone property of the iterations gives improved upper and lower bounds of the solution in each iteration, and the rate of convergence of the iterations is either quadratic or nearly quadratic depending on the property of the nonlinear function. Application is given to a model problem from chemical engineering, and some numerical results, including a test problem with known analytical solution, are presented to illustrate the various rates of convergence of the iterations. Received November 2, 1995 / Revised version received February 10, 1997     

Block monotone iterative methods for numerical solutions of nonlinear elliptic equations

Summary. Two block monotone iterative schemes for a nonlinear algebraic system, which is a finite difference approximation of a nonlinear elliptic boundary-value problem, are presented and are shown to converge monotonically either from above or from below to a solution of the system. This monotone convergence result yields a computational algorithm for numerical solutions as well as an existence-comparison theorem of the system, including a sufficient condition for the uniqueness of the solution. An advantage of the block iterative schemes is that the Thomas algorithm can be used to compute numerical solutions of the sequence of iterations in the same fashion as for one-dimensional problems. The block iterative schemes are compared with the point monotone iterative schemes of Picard, Jacobi and Gauss-Seidel, and various theoretical comparison results among these monotone iterative schemes are given. These comparison results demonstrate that the sequence of iterations from the block iterative schemes converges faster than the corresponding sequence given by the point iterative schemes. Application of the iterative schemes is given to a logistic model problem in ecology and numerical ressults for a test problem with known analytical solution are given. Received August 1, 1993 / Revised version received November 7, 1994     

A Computational Study of the Homogeneous Algorithm for Large-scale Convex Optimization

Recently the authors have proposed a homogeneous and self-dual algorithm for solving the monotone complementarity problem (MCP) [5]. The algorithm is a single phase interior-point type method; nevertheless, it yields either an approximate optimal solution or detects a possible infeasibility of the problem. In this paper we specialize the algorithm to the solution of general smooth convex optimization problems, which also possess nonlinear inequality constraints and free variables. We discuss an implementation of the algorithm for large-scale sparse convex optimization. Moreover, we present computational results for solving quadratically constrained quadratic programming and geometric programming problems, where some of the problems contain more than 100,000 constraints and variables. The results indicate that the proposed algorithm is also practically efficient.     

A smoothing-type algorithm for the second-order cone complementarity problem with a new nonmonotone line search

The second-order cone complementarity problem (denoted by SOCCP) can be effectively solved by smoothing-type algorithms, which in general are designed based on some monotone line search. In this paper, based on a new smoothing function of the Fischer–Burmeister function, we propose a smoothing-type algorithm for solving the SOCCP. The proposed algorithm uses a new nonmonotone line search scheme, which contains the usual monotone line search as a special case. Under suitable assumptions, we show that the proposed algorithm is globally and locally quadratically convergent. Some numerical results are reported which indicate the effectiveness of the proposed algorithm.     

An Answer to S. Simons’ Question on the Maximal Monotonicity of the Sum of a Maximal Monotone Linear Operator and a Normal Cone Operator

The question whether or not the sum of two maximal monotone operators is maximal monotone under Rockafellar’s constraint qualification—that is, whether or not “the sum theorem” is true—is the most famous open problem in Monotone Operator Theory. In his 2008 monograph “From Hahn-Banach to Monotonicity”, Stephen Simons asked whether or not the sum theorem holds for the special case of a maximal monotone linear operator and a normal cone operator of a closed convex set provided that the interior of the set makes a nonempty intersection with the domain of the linear operator. In this note, we provide an affirmative answer to Simons’ question. In fact, we show that the sum theorem is true for a maximal monotone linear relation and a normal cone operator. The proof relies on Rockafellar’s formula for the Fenchel conjugate of the sum as well as some results featuring the Fitzpatrick function.      

Upper Bounds on the Covering Number of Galois-Planes with Small Order

Our paper deals with the covering number of finite projective planes which is related to an unsolved question of P. Erdös. An integer linear programming (ILP) formulation of the covering number of finite projective planes is introduced for projective planes of given orders. The mathematical programming based approach for this problem is new in the area of finite projective planes. Since the ILP problem is NP-hard and may involve up to 360.000 boolean variables for the considered problems, we propose a heuristic based on Simulated Annealing. The computational study gives a new insight into the structure of projective planes and their (minimal) blocking sets. This computational study indicates that the current theoretical results may be improved.     

On accelerated monotone iterations for numerical solutions of semilinear elliptic boundary value problems

This paper is concerned with the computational algorithms for finite difference solutions of a class of semilinear elliptic boundary value problems. An accelerated monotone iterative scheme is presented by using the method of upper and lower solutions. The rate of convergence of the iterations is estimated by the infinity norm, and the rate of convergence is quadratic for a larger class of nonlinear functions, including monotone nonincreasing functions. An application is given to a logistic model problem in ecology.     

On a weighted total variation minimization problem

The present article is devoted to the study of a constrained weighted total variation minimization problem, which may be viewed as a relaxation of a generalized Cheeger problem and is motivated by landslide modeling. Using the fact that the set of minimizers is invariant by a wide class of monotone transformations, we prove that level sets of minimizers are generalized Cheeger sets and obtain qualitative properties of the minimizers: they are all bounded and all achieve their essential supremum on a set of positive measure.     

Generalized linear complementarity problems treated without fixed-point theory

We study the (monotone) linear complementarity problem in reflexive Banach space. The problem is treated as a quadratic program and shown to satisfy appropriate constraint qualifications. This leads to a theory of the generalized monotone linear complementarity problem which is independent of Brouwer's fixed-point theorem. Certain related results on linear systems are given. The final section concerns copositive operators.This research was partially supported by NSERC Grant No. A-5516.The author thanks the referee for his painstaking and thorough comments on this paper.     

A Constraint Programming Framework for Local Search Methods

We propose in this paper a novel integration of local search algorithms within a constraint programming framework for combinatorial optimization problems, in an attempt to gain both the efficiency of local search methods and the flexibility of constraint programming while maintaining a clear separation between the constraints of the problem and the actual search procedure. Each neighborhood exploration is performed by branch-and-bound search, whose potential pruning capabilities open the door to more elaborate local moves, which could lead to even better approximate results. Two illustrations of this framework are provided, including computational results for the traveling salesman problem with time windows. These results indicate that it is one order of magnitude faster than the customary constraint programming approach to local search and that it is competitive with a specialized local search algorithm.     

The boundary quenching behavior of a semilinear parabolic equation

In this paper we consider the boundary quenching behavior of a semilinear parabolic problem in one-dimensional space, of which the nonlinearity appears both in the source term and in the Neumann boundary condition. First we proved that the solution quenches at somewhere in some finite time. Then we assert that the quenching can only occur on the left boundary if the given initial datum is monotone. Finally we derived the upper and lower bounds for the quenching rate of the solution near the quenching time. Thus we generalized our former results.     

Strong Convergence Theorems for Maximal and Inverse-Strongly Monotone Mappings in Hilbert Spaces and Applications

In this paper, we prove two strong convergence theorems for finding a common point of the set of zero points of the addition of an inverse-strongly monotone mapping and a maximal monotone operator and the set of zero points of a maximal monotone operator, which is related to an equilibrium problem in a Hilbert space. Such theorems improve and extend the results announced by Y. Liu (Nonlinear Anal. 71:4852–4861, 2009). As applications of the results, we present well-known and new strong convergence theorems which are connected with the variational inequality, the equilibrium problem and the fixed point problem in a Hilbert space.     

Monotonic properties of the least squares mean

We settle an open problem of several years standing by showing that the least squares mean for positive definite matrices is monotone for the usual (Loewner) order. Indeed we show this is a special case of its appropriate generalization to partially ordered complete metric spaces of nonpositive curvature. Our techniques extend to establish other basic properties of the least squares mean such as continuity and joint concavity. Moreover, we introduce a weighted least squares mean and derive our results in this more general setting.     

Positive solutions and dynamics of a finite difference reaction–diffusion system

We investigate the dynamics and methods of computation for some nonlinear finite difference systems that are the discretized equations of a time-dependent and a steady-state reaction–diffusion problem. The formulation of the discrete equations for the time-dependent problem is based on the implicit method for parabolic equations, and the computational algorithm is based on the method of monotone iterations using upper and lower solutions as the initial iterations. The monotone iterative method yields improved upper and lower bounds of the solution in each iteration, and the sequence of iterations converges monotonically to a solution for both the time-dependent and the steady-state problems. An important consequence of this method is that it leads to a bifurcation point that determines the dynamic behavior of the time-dependent problem in relation to the corresponding steady-state problem. This bifurcation point also determines whether the steady-state problem has one or two non-negative solutions, and is explicitly given in terms of the physical parameters of the system and the type of boundary conditions. Numerical results are presented for both the time-dependent and the steady-state problems under various boundary conditions, including a test problem with known analytical solution. These numerical results exhibit the predicted dynamic behavior of the time-dependent solution given by the theoretical analysis. Also discussed are the numerical stability of the computational algorithm and the convergence of the finite difference solution to the corresponding continuous solution of the reaction–diffusion problem. © 1993 John Wiley & Sons, Inc.     

Logistics distribution network design with two commodity categories

In this paper, we study the design of a logistics distribution network consisting of a supplier, a set of potential warehouses, and a set of retailers. There are commodities from two product categories, that is, category A and category B, flowing across the network. The demand for commodities in product category A is stable. The demand for commodities in product category B is highly uncertain. We show that the network design problem to distribute the commodities in both product categories can be formulated as the uncapacitated facility location problem with monotone submodular costs and tackled using a cutting plane algorithm. We propose a strongly polynomial time algorithm for the nonlinear discrete optimization problem, which must be solved in each iteration of the cutting plane algorithm. We also provide the computational results, and summarize the insights based on the proposed model and the solution algorithm.