Random backtracking in backtrack search algorithms for satisfiability

This paper proposes the utilization of randomized backtracking within complete backtrack search algorithms for propositional satisfiability (SAT). In recent years, randomization has become pervasive in SAT algorithms. Incomplete algorithms for SAT, for example the ones based on local search, often resort to randomization. Complete algorithms also resort to randomization. These include state-of-the-art backtrack search SAT algorithms that often randomize variable selection heuristics. Moreover, it is plain that the introduction of randomization in other components of backtrack search SAT algorithms can potentially yield new competitive search strategies. As a result, we propose a stochastic backtrack search algorithm for SAT, that randomizes both the variable selection and the backtrack steps of the algorithm. In addition, we relate randomized backtracking with a more general form of backtracking, referred to as unrestricted backtracking. Finally, experimental results for different organizations of randomized backtracking are described and compared, providing empirical evidence that the new search algorithm for SAT is a very competitive approach for solving hard real-world instances.     

Local elimination algorithms for solving sparse discrete problems

The class of local elimination algorithms is considered that make it possible to obtain global information about solutions of a problem using local information. The general structure of local elimination algorithms is described that use neighborhoods of elements and the structural graph describing the problem structure; an elimination algorithm is also described. This class of algorithms includes local decomposition algorithms for discrete optimization problems, nonserial dynamic programming algorithms, bucket elimination algorithms, and tree decomposition algorithms. It is shown that local elimination algorithms can be used for solving optimization problems.     

Computational experience with an interior point algorithm on the satisfiability problem

We apply the zero-one integer programming algorithm described in Karmarkar [12] and Karmarkar, Resende and Ramakrishnan [13] to solve randomly generated instances of the satisfiability problem (SAT). The interior point algorithm is briefly reviewed and shown to be easily adapted to solve large instances of SAT. Hundreds of instances of SAT (having from 100 to 1000 variables and 100 to 32,000 clauses) are randomly generated and solved. For comparison, we attempt to solve the problems via linear programming relaxation with MINOS.     

Efficient algorithms for solving rank two and rank three bilinear programming problems

Finitely convergent algorithms for solving rank two and three bilinear programming problems are proposed. A rank k bilinear programming problem is a nonconvex quadratic programming problem with the following structure: % MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4baFfea0dXde9vqpa0lb9% cq0dXdb9IqFHe9FjuP0-iq0dXdbba9pe0lb9hs0dXda91qaq-xfr-x% fj-hmeGabaqaciGacaGaaeqabaWaaeaaeaaakeaaieaacaWFTbGaa8% xAaiaa-5gacaWFPbGaa8xBaiaa-LgacaWF6bGaa8xzaiaa-bcacaWF% 7bacbiGaa43yamaaDaaaleaacaGFWaaabaGaa4hDaaaakiaa+Hhaca% GFRaGaa4hzamaaDaaaleaacaGFWaaabaGaa4hDaaaakiaa+LhacaGF% RaWaaabuaeaacaGFJbWaa0baaSqaaiaa+PgaaeaacaGF0baaaOGaam% iEaiabl+y6NjaadsgadaqhaaWcbaGaamOAaaqaaiaadshaaaGccaWG% 5bGaaiiFaaWcbaGaa8NAaiaa-1dacaWFXaaabeqdcqGHris5aOGaa4% hEaiabgIGiolaa+HfacaGFSaGaa4xEaiabgIGiolaa+LfacaWF9bGa% a8hlaaaa!5D2E!\[minimize \{ c_0^t x + d_0^t y + \sum\limits_{j = 1} {c_j^t xd_j^t y|} x \in X,y \in Y\} ,\]where X Rⁿ¹ and Y R ⁿ² are non-empty and bounded polytopes. We show that a variant of parametric simplex algorithm can solve large scale rank two bilinear programming problems efficiently. Also, we show that a cutting-cake algorithm, a more elaborate variant of parametric simplex algorithm can solve medium scale rank three problems.This research was supported in part by Grant-in-Aid for Scientific Research of the Ministry of Education, Science and Culture, Grant No. 63490010.     

The complete parsimony haplotype inference problem and algorithms based on integer programming,branch-and-bound and Boolean satisfiability

Haplotype inference by pure parsimony (Hipp) is a well-known paradigm for haplotype inference. In order to assess the biological significance of this paradigm, we generalize the problem of Hipp to the problem of finding all optimal solutions, which we call Chipp. We study intrinsic haplotype features, such as backbone haplotypes and fat genotypes as well as equal columns and decomposability. We explicitly exploit these features in three computational approaches that are based on integer linear programming, depth-first branch-and-bound, and Boolean satisfiability. Further we introduce two hybrid algorithms that draw upon the diverse strengths of the approaches. Our experimental analysis shows that our optimized algorithms are significantly superior to the baseline algorithms, often with orders of magnitude faster running time. Finally, our experiments provide some useful insights into the intrinsic features of this important problem.     

Interactive TOPSIS algorithms for solving multi-level non-linear multi-objective decision-making problems

This paper extended the concept of the technique for order preference by similarity to ideal solution (TOPSIS) to develop a methodology for solving multi-level non-linear multi-objective decision-making (MLN-MODM) problems of maximization-type. Also, two new interactive algorithms are presented for the proposed TOPSIS approach for solving these types of mathematical programming problems. The first proposed interactive TOPSIS algorithm includes the membership functions of the decision variables for each level except the lower level of the multi-level problem. These satisfactory decisions are evaluated separately by solving the corresponding single-level MODM problems. The second proposed interactive TOPSIS algorithm lexicographically solves the MODM problems of the MLN-MOLP problem by taking into consideration the decisions of the MODM problems for the upper levels. To demonstrate the proposed algorithms, a numerical example is solved and compared the solutions of proposed algorithms with the solution of the interactive algorithm of Osman et al. (2003) [4]. Also, an example of an application is presented to clarify the applicability of the proposed TOPSIS algorithms in solving real world multi-level multi-objective decision-making problems.     

Approximation algorithms for Hamming clustering problems

We study Hamming versions of two classical clustering problems. The Hamming radius p-clustering problem (HRC) for a set S of k binary strings, each of length n, is to find p binary strings of length n that minimize the maximum Hamming distance between a string in S and the closest of the p strings; this minimum value is termed the p-radius of S and is denoted by . The related Hamming diameter p-clustering problem (HDC) is to split S into p groups so that the maximum of the Hamming group diameters is minimized; this latter value is called the p-diameter of S.We provide an integer programming formulation of HRC which yields exact solutions in polynomial time whenever k is constant. We also observe that HDC admits straightforward polynomial-time solutions when k=O(logn) and p=O(1), or when p=2. Next, by reduction from the corresponding geometric p-clustering problems in the plane under the L₁ metric, we show that neither HRC nor HDC can be approximated within any constant factor smaller than two unless P=NP. We also prove that for any >0 it is NP-hard to split S into at most pk^1/7− clusters whose Hamming diameter does not exceed the p-diameter, and that solving HDC exactly is an NP-complete problem already for p=3. Furthermore, we note that by adapting Gonzalez' farthest-point clustering algorithm [T. Gonzalez, Theoret. Comput. Sci. 38 (1985) 293–306], HRC and HDC can be approximated within a factor of two in time O(pkn). Next, we describe a 2^O(p/)k^O(p/)n²-time (1+)-approximation algorithm for HRC. In particular, it runs in polynomial time when p=O(1) and =O(log(k+n)). Finally, we show how to find in

Full-size image

time a set L of O(plogk) strings of length n such that for each string in S there is at least one string in L within distance (1+), for any constant 0<<1.     

Trajectory-following algorithms for min-max optimization problems

In this paper, we consider a class of nonlinear minimum-maximum optimization problems subject to boundedness constraints on the decision vectors. Three algorithms are developed for finding the min-max point using the concept of solving an associated dynamical system. In the first and third algorithms, solutions are obtained by solving systems of differential equations. The second algorithm is a discrete version of the first algorithm. The trajectories generated by the first and second algorithms may move inside or on the boundary of the constraint set, while the third algorithm ensures that any trajectory that begins inside the constraint region remains in its interior. Sufficient conditions for global convergence of the two algorithms are also established. For illustration, four numerical examples are solved.This work was partially supported by a research grant from the Australian Research Committee.     

Modified extragradient algorithms for solving equilibrium problems

ABSTRACT

In this paper, we introduce some new algorithms for solving the equilibrium problem in a Hilbert space which are constructed around the proximal-like mapping and inertial effect. Also, some convergence theorems of the algorithms are established under mild conditions. Finally, several experiments are performed to show the computational efficiency and the advantage of the proposed algorithm over other well-known algorithms.     

非线性半定规划若干算法介绍

介绍近几年国际上求解非线性半定规划的若干有效新算法, 包括增广Lagrangian函数法、序列半定规划法、序列线性方程组法以及交替方向乘子法. 最后, 对非线性半定规划的算法研究前景进行了探讨.     

New variable-metric algorithms for nondifferentiable optimization problems

This paper deals with new variable-metric algorithms for nonsmooth optimization problems, the so-called adaptive algorithms. The essence of these algorithms is that there are two simultaneously working gradient algorithms: the first is in the main space and the second is in the space of the matrices that modify the main variables. The convergence of these algorithms is proved for different cases. The results of numerical experiments are also given.     

A linear programming-based optimization algorithm for solving nonlinear programming problems

In this paper a linear programming-based optimization algorithm called the Sequential Cutting Plane algorithm is presented. The main features of the algorithm are described, convergence to a Karush–Kuhn–Tucker stationary point is proved and numerical experience on some well-known test sets is showed. The algorithm is based on an earlier version for convex inequality constrained problems, but here the algorithm is extended to general continuously differentiable nonlinear programming problems containing both nonlinear inequality and equality constraints. A comparison with some existing solvers shows that the algorithm is competitive with these solvers. Thus, this new method based on solving linear programming subproblems is a good alternative method for solving nonlinear programming problems efficiently. The algorithm has been used as a subsolver in a mixed integer nonlinear programming algorithm where the linear problems provide lower bounds on the optimal solutions of the nonlinear programming subproblems in the branch and bound tree for convex, inequality constrained problems.     

Polynomial time algorithms for some classes of constrained nonconvex quadratic problems

In this paper we consider different classes of noneonvex quadratic problems that can be solved in polynomial time. We present an algorithm for the problem of minimizing the product of two linear functions over a polyhedron P in R ⁿ The complexity of the algorithm depends on the number of vertices of the projection of P onto the R ² space. In the worst-case this algorithm requires an exponential number of steps but its expected computational time complexity is polynomial. In addition, we give a characterization for the number of isolated local minimum areas for problems on this form.

Furthermore, we consider indefinite quadratic problems with variables restricted to be nonnegative. These problems can be solved in polynomial time if the number of negative eigenvalues of the associated symmetric matrix is fixed.     

Approximate nonlinear programming algorithms for solving stochastic programs with recourse

This paper summarizes the main results on approximate nonlinear programming algorithms investigated by the author. These algorithms are obtained by combining approximation and nonlinear programming algorithms. They are designed for programs in which the evaluation of the objective functions is very difficult so that only their approximate values can be obtained. Therefore, these algorithms are particularly suitable for stochastic programming problems with recourse.Project supported by the National Natural Science Foundation of China.     

Parametric simplex algorithms for solving a special class of nonconvex minimization problems

It is shown that parametric linear programming algorithms work efficiently for a class of nonconvex quadratic programming problems called generalized linear multiplicative programming problems, whose objective function is the sum of a linear function and a product of two linear functions. Also, it is shown that the global minimum of the sum of the two linear fractional functions over a polytope can be obtained by a similar algorithm. Our numerical experiments reveal that these problems can be solved in much the same computational time as that of solving associated linear programs. Furthermore, we will show that the same approach can be extended to a more general class of nonconvex quadratic programming problems.     

Simplex-inspired algorithms for solving a class of convex programming problems

We consider a class of convex programming problems whose objective function is given as a linear function plus a convex function whose arguments are linear functions of the decision variables and whose feasible region is a polytope. We show that there exists an optimal solution to this class of problems on a face of the constraint polytope of dimension not more than the number of arguments of the convex function. Based on this result, we develop a method to solve this problem that is inspired by the simplex method for linear programming. It is shown that this method terminates in a finite number of iterations in the special case that the convex function has only a single argument. We then use this insight to develop a second algorithm that solves the problem in a finite number of iterations for an arbitrary number of arguments in the convex function. A computational study illustrates the efficiency of the algorithm and suggests that the average-case performance of these algorithms is a polynomial of low order in the number of decision variables. The work of T. C. Sharkey was supported by a National Science Foundation Graduate Research Fellowship. The work of H. E. Romeijn was supported by the National Science Foundation under Grant No. DMI-0355533.     

Analysis of some greedy algorithms for the single-sink fixed-charge transportation problem

The single-sink fixed-charge transportation problem (SSFCTP) consists of finding a minimum cost flow from a number of nodes to a single sink. Beside a cost proportional to the amount shipped, the flow cost encompass a fixed charge. The SSFCTP is an important subproblem of the well-known fixed-charge transportation problem. Nevertheless, just a few methods for solving this problem have been proposed in the literature. In this paper, some greedy heuristic solutions methods for the SSFCTP are investigated. It is shown that two greedy approaches for the SSFCTP known from the literature can be arbitrarily bad, whereas an approximation algorithm proposed in the literature for the binary min-knapsack problem has a guaranteed worst case bound if adapted accordingly to the case of the SSFCTP.     

Global convergence rates for descent algorithms: Improved results for strictly convex problems

Convergence to the minimal value is studied for the important type of descent algorithm which, at each interation, uses a search direction making an angle with the negative gradient which is smaller than a prespecified angle. Improvements on existing convergence rate results are obtained.Paper received on 4 October, 1977; in revised form, April 3, 1978     

Iterative processes for solving incorrect convex variational problems

The present paper is concerned with a general approach to the construction and the numerical analysis of stable methods solving semi-infinite convex programs and variational inequalities of elliptical type in case where the considered problems are incorrect. The approach which is based on the application of the PROX-regularization (cf. Martinet, 1970; Ekeland and Temam, 1976; Rockafellar, 1976; Brézis and Lions, 1978; Lemaire, 1988) secures the strong convergence of the minimizing sequence. The possibility of the algorithmical realization is described and depends on the smoothness properties of the solutions.Supported by Deutsche Forschungsgemeinschaft under grant Ti 191/1-1.     

Investigation of polynomial algorithms for solving the three-index planar assignment problem

Under certain additional conditions imposed on the coefficients of the objective function in the three-index planar assignment problem, a large series of computational experiments aimed at the investigation of four polynomial algorithms for finding an asymptotically optimal solution of this problem is conducted.