MPC

MPC 2014, ISSUE 3



Mathematical Programming Computation, Volume 6, Issue 3, September 2014

An exact cooperative method for the uncapacitated facility location problem

Marius Posta, Jacques A. Ferland, Philippe Michelon

In this paper, we present a cooperative primal-dual method to solve the uncapacitated facility location problem exactly. It consists of a primal process, which performs a variation of a knownand effective tabu search procedure, and a dual process, which performs a lagrangian branch-and-bound search. Both processes cooperate by exchanging information which helps them find the optimal solution. Further contributions include new techniques for improving the evaluation of the branch-and-bound nodes: decision-variable bound tightening rules applied at each node, and a subgradient caching strategy to improve the bundle method applied at each node.

Full Text: PDF



Mathematical Programming Computation, Volume 6, Issue 3, September 2014

Optimization of algorithms with OPAL

Charles Audet, Kien-Cong Dang, Dominique Orban

Opal is a general-purpose system for modeling and solving algorithm optimization problems. Opal takes an algorithm as input, and as output it suggests parameter values that maximize some user-defined performance measure. In order to achieve this, the user provides a Python script describing how to launch the target algorithm, and defining the performance measure. Opal then models this question as a blackbox optimization problem which is then solved by a state-of-the-art direct search solver. Opal handles a wide variety of parameter types, it can exploit multiple processors in parallel at different levels, and can take advantage of a surrogate blackbox. Several features of Opal are illustrated on a problem consisting in the design of a hybrid sort strategy.

Full Text: PDF



Mathematical Programming Computation, Volume 6, Issue 3, September 2014

Boosting the feasibility pump

Natashia L. Boland, Andrew C. Eberhard, Faramroze G. Engineer, Matteo Fischetti, Martin W. P. Savelsbergh, Angelos Tsoukalas

The feasibility pump (FP) has proved to be an effective method for finding feasible solutions to mixed integer programming problems. FP iterates between a rounding procedure and a projection procedure, which together provide a sequence of points alternating between LP feasible but fractional solutions, and integer but LP infeasible solutions. The process attempts to minimize the distance between consecutive iterates, producing an integer feasible solution when closing the distance between them. We investigate the benefits of enhancing the rounding procedure with a clever integer line search that efficiently explores a large set of integer points. An extensive computational study on benchmark instances demonstrates the efficacy of the proposed approach.

Full Text: PDF



Mathematical Programming Computation, Volume 6, Issue 3, September 2014

A partial proximal point algorithm for nuclear norm regularized matrix least squares problems

Kaifeng Jiang, Defeng Sun, Kim-Chuan Toh

We introduce a partial proximal point algorithm for solving nuclear norm regularized matrix least squares problems with equality and inequality constraints. The inner subproblems, reformulated as a system of semismooth equations, are solved by an inexact smoothing Newton method, which is proved to be quadratically convergent under a constraint non-degeneracy condition, together with the strong semismoothness property of the singular value thresholding operator. Numerical experiments on a variety of problems including those arising from low-rank approximations of transition matrices show that our algorithm is efficient and robust.

Full Text: PDF




Imprint and privacy statement

For the imprint and privacy statement we refer to the Imprint of ZIB.
© 2008-2020 by Zuse Institute Berlin (ZIB).