Invited Session Fri.3.MA 041

Friday, 15:15 - 16:45 h, Room: MA 041

Cluster 14: Mixed-integer nonlinear programming [...]

Modelling, reformulation and solution of MINLPs


Chair: Leo Liberti



Friday, 15:15 - 15:40 h, Room: MA 041, Talk 1

Marianna de Santis
A method for MINLP problems with simple constraints

Coauthor: Stefano Lucidi


We are concerned with the problem of minimizing a continuously differentiable function subject to simple constraints on the variables where some of the variables are restricted to take integer values. To tackle the problem we propose an approach based on a minimization of distributed type: an appropriate local search is performed depending on whether the variable is continuous or integer. The continuous local search is based on an active set method that combines ideas from projected and Newton-type algorithms. For the discrete local search a grid search along the discrete variables is performed.



Friday, 15:45 - 16:10 h, Room: MA 041, Talk 2

Leo Liberti
On feasibility-based bounds tightening

Coauthors: Pietro Belotti, Sonia Cafieri, Jon Lee


Mathematical programming problems involving nonconvexities are usually solved to optimality using a spatial branch-and-bound (sBB) 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 iterative procedure to tighten the variable ranges. Depending on the instance, FBBT may not converge finitely to its limit ranges, even in the case of linear constraints. Tolerance-based termination criteria yield finite termination, but not in worst-case polynomial time. We model FBBT by using fixed-point equations in terms of the variable bounding box, and we treat these equations as constraints of an auxiliary mathematical program. We demonstrate that the auxiliary mathematical problem is a linear program, which can of course be solved in polynomial time. We demonstrate the usefulness of our approach by improving the open-source sBB solver Couenne.



Friday, 16:15 - 16:40 h, Room: MA 041, Talk 3

Claudia D'Ambrosio
Optimistic modeling of non-linear optimization problems by mixed-integer linear programming

Coauthors: Andrea Lodi, Riccardo Rovatti, Martello Silvano


We present a new piecewise linear approximation of non-linear optimization problems. It can be seen as a variant of classical triangulations that leaves more degrees of freedom to define any point as a convex combination of the samples. For a hyper-rectangular domain URL, partitioned into hyper-rectangular subdomains through a grid defined by nl points on the l-axis (l=1, … ,L), the number of potential simplexes is L! \prodl=1L(nl-1), and an MILP model incorporating it without complicated encoding strategies must have the same number of additional binary variables. In the proposed approach the choice of the simplexes is optimistically guided by one between two approximating objective functions, and the number of additional binary variables needed by a straightforward implementation drops to only l=1L(nl-1). The method allows the use of recent methods for representing such a partition with a logarithmic number of constraints and binary variables.
We show theoretical properties of the approximating functions, and provide computational evidence of the impact of the method when embedded in MILP models.


  signature loans . But it is worth noting that these tests were carried out on the blood cells. Therefore, it's too early to say about scientific evidence of Viagra influence on blood clots.