Extended abstract
Abstract:
In this paper, a new technique to compute a synthesis structured Robust Control Law is developed. This technique is based on global optimization methods using a Branch-and-Bound algorithm. The original problem is reformulated as a min/max problem with non-convex constraint. Our approach uses interval arithmetic to compute bounds and accelerate the convergence.
Extended abstract
Abstract:
IBEX is a open-source C++ library for constraint processing over real numbers.
It provides reliable algorithms for handling non-linear constraints. In particular, roundoff errors are also taken into account. It is based on interval arithmetic and affine arithmetic. The main feature of IBEX is its ability to build strategies declaratively through the contractor programming paradigm. It can also be used as a black-box solver or with an AMPL interface. Two emblematic problems that can be addressed are:
(i) System solving: A guaranteed enclosure for each solution of a system of (nonlinear) equations is calculated;
(ii) Global optimization: A global minimizer of some function under non-linear constraints is calculated with guaranteed and reliable bounds on the objective minimum.
Extended abstract
Abstract:
This paper address the global optimization problem of polynomial mixed-integer nonlinear programs (MINLPs). A improved branch-and-prune algorithm based on the Bernstein form is proposed to solve such MINLPs. The algorithm use a new pruning feature based on the Bernstein form, called the Bernstein box and Bernstein hull consistency. The proposed algorithm is tested on a set of 16 MINLPs chosen from the literature. The efficacy of the proposed algorithm is brought out via numerical studies with the previously reported Bernstein algorithms and several state-of-the-art MINLP solvers.
Extended abstract
Abstract:
Nowadays, the quadratic assignment problem (QAP) is widely considered as one of the hardest of the NP-hard problems. One of the main reasons for this consideration can be found in the enormous difficulty of computing good quality bounds for branch-and-bound algorithms. The practice shows that even with the power of modern computers QAPs of size n>30 are typically recognized as huge computational problems.
In this work, we are concerned with the design of a new low-dimensional semidefinite programming relaxation for the computation of lower bounds of the QAP.
We discuss various ways to improve the bounding program upon its semidefinite relaxation base and give numerical examples to demonstrate its applicability.