An alternate formulation of the classical vehicle routing problem with stochastic demands (VRPSD)is considered. We propose a new heuristic method to solve the problem. The algorithm is a modified version of the so-called Cross-Entropy method, which has been proposed in the literature as a heuristics for deterministic combinatorial optimization problems based upon concepts of rare-event … Read more
In this paper we present a new definition on the globally concavized filled function for the continuous global minimization problem, which was modified from that by Ge [3]. A new class of globally concavized filled functions are constructed. These functions contain two easily determinable parameters, which are not dependent on the radius of the basin … Read more
We propose a branch-and-bound algorithm for solving nonconvex quadratically-constrained quadratic programs. The algorithm is novel in that branching is done by partitioning the feasible region into the Cartesian product of two-dimensional triangles and rectangles. Explicit formulae for the convex and concave envelopes of bilinear functions over triangles and rectangles are derived and shown to be … Read more
We present a stochastic global optimization method that employs a clustering technique which is based on a typical distance and a gradient test. The method aims to recover all the local minima inside a rectangular domain. A new stopping rule is used. Comparative results on a set of test functions are reported. CitationPreprint, no 4-5/2004 … Read more
This paper is based on a recent work by Kojima which extended sums of squares relaxations of polynomial optimization problems to polynomial semidefinite programs. Let ${\cal E}$ and ${\cal E}_+$ be a finite dimensional real vector space and a symmetric cone embedded in ${\cal E}$; examples of $\calE$ and $\calE_+$ include a pair of the … Read more
Results are reported of testing a number of existing state of the art solvers for global constrained optimization and constraint satisfaction on a set of over 1000 test problems in up to 1000 variables. Citationsubmitted to the special issue on Global Optimization of Math. ProgrammingArticleDownload View PDF
In this paper we show that the unconstrained continuous global minimization problem can not be solved by any algorithm. So without loss of generality we consider the box constrained continuous global minimization problem. We present a new globally convexized filled function method for the problem. The definition of globally convexized filled function is adapted from … Read more
We consider here the problem of minimizing a polynomial function on $\oR^n$. The problem is known to be hard even for degree $4$. Therefore approximation algorithms are of interest. Lasserre \cite{lasserre:2001} and Parrilo \cite{Pa02a} have proposed approximating the minimum of the original problem using a hierarchy of lower bounds obtained via semidefinite programming relaxations. We … Read more
Sufficient optimality criteria for linearly constrained, concave minimization problems is given in this paper. Our optimality criteria is based on the sensitivity analysis of the relaxed linear programming problem. Our main result is similar to that of Phillips and Rosen (1993), however our proofs are simpler and constructive. Phillips and Rosen (1993) in their paper … Read more
This paper presents a new method for solving global optimization problems. We use a local technique based on the notion of discrete gradients for finding a cone of descent directions and then we use a global cutting angle algorithm for finding global minimum within the intersection of the cone and the feasible region. We present … Read more