In this paper we report results on the problem of docking two large proteins by means of a two-phase monotonic basin hopping method. Given an appropriate force field which is used to measure the interaction energy between two biomolecules which are considered as rigid bodies, we used a randomized global optimization methods based upon the … Read more
This article considers continuous trajectories of the vector fields induced by primal-dual potential-reduction algorithms for solving linear programming problems. It is known that these trajectories converge to the analytic center of the primal-dual optimal face. We establish that this convergence may be tangential to the central path, tangential to the optimal face, or in between, … Read more
Let $P$ be an optimization problem, and let $A$ be an approximation algorithm for $P$. The domination ratio $\domr(A,n)$ is the maximum real $q$ such that the solution $x(I)$ obtained by $A$ for any instance $I$ of $P$ of size $n$ is not worse than at least a fraction $q$ of the feasible solutions of … Read more
In this paper, we describe a methodology for the analysis of greedy randomized adaptive search procedures (GRASP). GRASP is a metaheuristic for combinatorial optimization. It usually consists of a construction procedure based on a greedy randomized algorithm and a local search. Hybrid approaches of GRASP with path-relinking developed for the 3-index assignment problem (AP3) and … Read more
This paper addresses recent advances and application of hybridizations of greedy randomized adaptive search procedures (GRASP) and path-relinking. We present a template for implementing path-relinking as an intensification procedure for GRASP. Enhancements to the procedure, recently described in the literature, are reviewed. The effectiveness of the procedure is illustrated experimentally. CitationAT&T Labs Research Technical Report, … Read more
In this paper we combine both trust-region and linesearch globalization strategies in a globally convergent hybrid algorithm to solve a continuously differentiable nonlinear equality constrained minimization problem. First, the trust-region approach is used to determine a descent direction of the augmented Lagrangian chosen as the merit function, and second, linesearch techniques are used to obtain … Read more
This paper describes a methodology that has been implemented in a major British airline to find the optimal price to charge for airline tickets under one-way pricing. An analytical model has been developed to describe the buying behaviour of customers for flights over the selling period. Using this model and a standard analytical method for … Read more
We consider primal-dual algorithms for certain types of infinite-dimensional optimization problems. Our approach is based on the generalization of the technique of finite-dimensional Euclidean Jordan algebras to the case of infinite-dimensional JB-algebras of finite rank. This generalization enables us to develop polynomial-time primal-dual algorithms for “infinite-dimensional second-order cone programs.” We consider as an example a … Read more
Solving systems of linear equations with “normal” matrices of the form $A D^2 A^T$ is a key ingredient in the computation of search directions for interior-point algorithms. In this article, we establish that a well-known basis preconditioner for such systems of linear equations produces scaled matrices with uniformly bounded condition numbers as $D$ varies over … Read more
A nonincreasing sequence of positive integers $\langle m_1,m_2,\cdots,m_k \rangle$ is said to be {\em $n$-realizable\/} if the set $I_n=\{ 1,2,\cdots,n\}$ can be partitioned into $k$ mutually disjoint subsets $S_1,S_2,\cdots, S_k$ such that $\sum\limits_{x\in S_i}x=m_i$ for each $1\le i\le k$. In this paper, we will prove that a nonincreasing sequence of positive integers $\langle m_1,m_2,\cdots,m_k\rangle$ is … Read more