Laura Palagi
Margin Optimal Classification Trees
ArticleDownload View PDF
Branching with Hyperplanes in the Criterion Space: the Frontier Partitioner Algorithm for Biobjective Integer Programming
We present an algorithm for finding the complete Pareto frontier of biobjective integer programming problems. The method is based on the solution of a finite number of integer programs. The feasible sets of the integer programs are built from the original feasible set, by adding cuts that separate efficient solutions. Providing the existence of an … Read more
A Fast Branch-and-Bound Algorithm for Non-convex Quadratic Integer Optimization Subject To Linear Constraints Using Ellipsoidal Relaxations
We propose two exact approaches for non-convex quadratic integer minimization subject to linear constraints where lower bounds are computed by considering ellipsoidal relaxations of the feasible set. In the first approach, we intersect the ellipsoids with the feasible linear subspace. In the second approach we penalize exactly the linear constraints. We investigate the connection between … Read more
An Exact Algorithm for Quadratic Integer Minimization using Ellipsoidal Relaxations
We propose a branch-and-bound algorithm for minimizing a not necessarily convex quadratic function over integer variables. The algorithm is based on lower bounds computed as continuous minima of the objective function over appropriate ellipsoids. In the nonconvex case, we use ellipsoids enclosing the feasible region of the problem. In spite of the nonconvexity, these minima … Read more
SpeeDP: A new algorithm to compute the SDP relaxations of Max-Cut for very large graphs
We consider low-rank semidefinite programming (LRSDP) relaxations of unconstrained {-1,1} quadratic problems (or, equivalently, of Max-Cut problems) that can be formulated as the nonconvex nonlinear programming problem of minimizing a quadratic function subject to separable quadratic equality constraints. We prove the equivalence of the LRSDP problem with the unconstrained minimization of a new merit function … Read more