A symmetrical linear maxmin approach to disjoint bilinear programming

Received June 24, 1996 / Revised version received May 22, 1997 Published online February 25, 1999     

Finding maximum likelihood estimators for the three-parameter Weibull distribution

Much work has been devoted to the problem of finding maximum likelihood estimators for the three-parameter Weibull distribution. This problem has not been clearly recognized as a global optimization one and most methods from the literature occasionally fail to find a global optimum. We develop a global optimization algorithm which uses first order conditions and projection to reduce the problem to a univariate optimization one. Bounds on the resulting function and its first order derivative are obtained and used in a branch-and-bound scheme. Computational experience is reported. It is also shown that the solution method we propose can be extended to the case of right censored samples.     

Global optimization of Hölder functions

We propose a branch-and-bound framework for the global optimization of unconstrained Hölder functions. The general framework is used to derive two algorithms. The first one is a generalization of Piyavskii's algorithm for univariate Lipschitz functions. The second algorithm, using a piecewise constant upper-bounding function, is designed for multivariate Hölder functions. A proof of convergence is provided for both algorithms. Computational experience is reported on several test functions from the literature.     

Concavity cuts for disjoint bilinear programming

We pursue the study of concavity cuts for the disjoint bilinear programming problem. This optimization problem has two equivalent symmetric linear maxmin reformulations, leading to two sets of concavity cuts. We first examine the depth of these cuts by considering the assumptions on the boundedness of the feasible regions of both maxmin and bilinear formulations. We next propose a branch and bound algorithm which make use of concavity cuts. We also present a procedure that eliminates degenerate solutions. Extensive computational experiences are reported. Sparse problems with up to 500 variables in each disjoint sets and 100 constraints, and dense problems with up to 60 variables again in each sets and 60 constraints are solved in reasonable computing times. Received: October 1999 / Accepted: January 2001?Published online March 22, 2001     

An anytime deduction algorithm for the probabilistic logic and entailment problems

We study two basic problems of probabilistic reasoning: the probabilistic logic and the probabilistic entailment problems. The first one can be defined as follows. Given a set of logical sentences and probabilities that these sentences are true, the aim is to determine whether these probabilities are consistent or not. Given a consistent set of logical sentences and probabilities, the probabilistic entailment problem consists in determining the range of the possible values of the probability associated with additional sentences while maintaining a consistent set of sentences and probabilities.This paper proposes a general approach based on an anytime deduction method that allows the follow-up of the reasoning when checking consistency for the probabilistic logic problem or when determining the probability intervals for the probabilistic entailment problem. Considering a series of subsets of sentences and probabilities, the approach proceeds by computing increasingly narrow probability intervals that either show a contradiction or that contain the tightest entailed probability interval. Computational experience have been conducted to compare the proposed anytime deduction method, called ad-psat with an exact one, psatcol, using column generation techniques, both with respect to the range of the probability intervals and the computing times.     

Reduction of indefinite quadratic programs to bilinear programs

Indefinite quadratic programs with quadratic constraints can be reduced to bilinear programs with bilinear constraints by duplication of variables. Such reductions are studied in which: (i) the number of additional variables is minimum or (ii) the number of complicating variables, i.e., variables to be fixed in order to obtain a linear program, in the resulting bilinear program is minimum. These two problems are shown to be equivalent to a maximum bipartite subgraph and a maximum stable set problem respectively in a graph associated with the quadratic program. Non-polynomial but practically efficient algorithms for both reductions are thus obtaine.d Reduction of more general global optimization problems than quadratic programs to bilinear programs is also briefly discussed.     

On using estimates of Lipschitz constants in global optimization

Several authors have proposed estimating Lipschitz constants in global optimization by a multiple of the largest slope (in absolute value) between successive evaluation points. A class of univariate functions is exhibited for which the global optimum will be missed when using such a procedure, even if the multiple is arbitrarily large.Research of the first and third authors was supported by AFOSR Grants 0271 and 0066 to Rutgers University. Research of the second author was supported by NSERC Grant GP0036426 and FCAR Grant 90NC0305.This research was done while the first author was Professor and the third author was Graduate Student at RUTCOR, Rutgers University.     

Generalized Convex Multiplicative Programming via Quasiconcave Minimization

We present a new method for minimizing the sum of a convex function and aproduct of k nonnegative convex functions over a convex set. This problem isreduced to a k-dimensional quasiconcave minimization problem which is solvedby a conical branch-and-bound algorithm. Comparative computational results areprovided on test problems from the literature.     

Penalty computations for the set partitioning problem

The computation of penalties associated with the continuous relaxation of integer programming problems can be useful to derive conditional and relational tests which allow to fix some variables at their optimal value or to generate new constraints (cuts). We study in this paper the computation and the use of penalties as a tool to improve the efficiency of algorithms for solving set partitioning problems. This leads to a preprocessing scheme which can be embedded within any exact or approximate algorithm. The strength of these penalties is illustrated through computational results on some real-world set partitioning problems.This work was sponsored by FINEP (research contract number 4.3.86.0689-00), CNPq (research contract numbers 11.1592-84, 30.2281-85 and 40.2002-86.5), IBM Brazil and NSERC (grant # GP0036426).On leave from the Catholic University of Rio de Janeiro, Department of Electrical Engineering, Caixa Postal 38063, Gávea, Rio de Janeiro 22452, Brazil.     

A branch and cut algorithm for nonconvex quadratically constrained quadratic programming

We present a branch and cut algorithm that yields in finite time, a globally ε-optimal solution (with respect to feasibility and optimality) of the nonconvex quadratically constrained quadratic programming problem. The idea is to estimate all quadratic terms by successive linearizations within a branching tree using Reformulation-Linearization Techniques (RLT). To do so, four classes of linearizations (cuts), depending on one to three parameters, are detailed. For each class, we show how to select the best member with respect to a precise criterion. The cuts introduced at any node of the tree are valid in the whole tree, and not only within the subtree rooted at that node. In order to enhance the computational speed, the structure created at any node of the tree is flexible enough to be used at other nodes. Computational results are reported that include standard test problems taken from the literature. Some of these problems are solved for the first time with a proof of global optimality. Received December 19, 1997 / Revised version received July 26, 1999?Published online November 9, 1999