Branch-and-bound algorithm applied to sparse optimization problems: a study of some exploration strategies.
Gwenaël Samain, Jordan Ninin, Sebastien Bourguignon
Sparse optimization focuses on finding a solution to least-squares problems with few non-zero components. Applications include inverse problems in signal processing, subset selection, or portfolio optimization. Optimization problems can be formulated as mixed-integer programs. A dedicated branch-and-bound algorithm is able to exploit the specific structure of such problems and finds the global minimum much faster than generic MIP solvers. We will present some results about the fine-tuning process of this branch-and-bound algorithm, focusing mainly on the exploration strategy.
Continuous location in spaces with different lp-normed regions.
Moisés Rodríguez-Madrena, Martine Labbé, Justo Puerto
In this work we address the single-facility Weber location problem in a finite dimensional real space endowed with different lp-norms at different polyhedral regions. We propose an equivalent representation of the location problem as a mixed-integer second order cone mathematical programming formulation. Interior point algorithms embedded in a branch-and-bound search can be applied allowing to obtain approximate solutions with a high precision degree. Our approach is validated reporting some preliminary computational experiments.
Large-scale Global Mixed-Integer Nonlinear Problems Solver by a Bi-level Generalized-CGRASP Metaheuristic Method
João Lauro Faco’, Ricardo Silva, Mauricio Resende
Large-scale MINLP problems where the numbers n of continuous bounded variables and m constraints are large, and d discrete variables, n+d>m can be solved in 2 levels. Repeat: (1) Optimization: a reduced problem in (n-m) continuous variables and d discrete variables is solved by a Generalized-CGRASP method where the random search and local improvement phases use a continuous and a discrete set. (2) Feasibility: test the other continuous variables feasibility solving a system of m NL equations by CGRASP, keeping fixed the former variables. If any variable violates a bound, do a change-of-basis.
Tightest linear reformulations for polynomial optimization with binary variables
Mathieu Verchère, Sourour Elloumi
Polynomial optimization problems with binary variables are known to be strongly NP-hard. In this talk, we consider the reformulation of these problems into equivalent mixed integer linear problems. For a given polynomial with binary variables, many such linear reformulations may exist and we focus on the question of how to find a reformulation with a tight LP bound. For polynomials with degree up to four, we formulate this question as a mixed integer linear problem. We then provide insights on potential improvements, as well as a theoretical comparison with other existing methods.