The industrial treatment of waste paper in order to regain valuable fibers from which recovered paper can be produced, involves several steps of preparation. One important step is the separation of stickies that are normally attached to the paper. If not properly separated, remaining stickies reduce the quality of the recovered paper or even disrupt … Read more
An automatic method for constructing linear relaxations of constrained global optimization problems is proposed. Such a construction is based on affine and interval arithmetics and uses operator overloading. These linear programs have exactly the same numbers of variables and of inequality constraints as the given problems. Each equality constraint is replaced by two inequalities. This … Read more
G. P. McCormick [Math Prog 1976] provides the framework for convex/concave relaxations of factorable functions, via rules for the product of functions and compositions of the form F(f(z)), where F is a univariate function. Herein, the composition theorem is generalized to allow multivariate outer functions F, and theory for the propagation of subgradients is presented. … Read more
The eigenvalues of a Hermitian matrix function that depends on one parameter analytically can be ordered so that each eigenvalue is an analytic function of the parameter. Ordering these analytic eigenvalues from the largest to the smallest yields continuous and piece-wise analytic functions. For multi-variate Hermitian matrix functions that depend on $d$ parameters analytically, the … Read more
Mathematical programming problems involving nonconvexities are usually solved to optimality using a (spatial) Branch-and-Bound algorithm. Algorithmic efficiency depends on many factors, among which the widths of the bounding box for the problem variables at each Branch-and-Bound node naturally plays a critical role. The practically fastest box-tightening algorithm is known as FBBT (Feasibility-Based Bounds Tightening): an … Read more
We show that global optimization techniques, based on interval analysis and constraint propagation, succeed in solving the classical problem of optimization of the Belgium gas network. CitationPublished as Inria Research report RR-7796, November 2011.ArticleDownload View PDF
The problem of optimizing a real function over the efficient set of a multiple objective programming problem arises in a variety of applications. In this article, we propose an outer approximation algorithm for maximizing a function $h(x) = \varphi(f(x))$ over the efficient set $X_E$ of the bi-criteria convex programming problem $ {\rm Vmin} \{f(x)=(f_1(x), f_2(x))^T … Read more
This paper describes libcgrpp, a GNU-style dynamic shared Python/C library of the continuous greedy randomized adaptive search procedure (C-GRASP) for bound constrained global optimization. C-GRASP is an extension of the GRASP metaheuristic (Feo and Resende, 1989). After a brief introduction to C-GRASP, we show how to download, install, configure, and use the library through an … Read more
In this paper we propose an algorithm for the global optimization of computationally expensive black–box functions. For this class of problems, no information, like e.g. the gradient, can be obtained and function evaluation is highly expensive. In many applications, however, a lower bound on the objective function is known; in this situation we derive a … Read more
A small polygon is a convex polygon of unit diameter. We are interested in small polygons which have the largest area for a given number of vertices $n$. Many instances are already solved in the literature, namely for all odd $n$, and for $n=4, 6$ and $8$. Thus, for even $n\geq 10$, instances of this … Read more