One of the foremost difficulties in solving Mixed Integer Nonlinear Programs (MINLP), either with exact or heuristic methods, is to find a feasible point. We address this issue with a new feasibility pump algorithm tailored for nonconvex MINLPs. Feasibility pumps are successive projection algorithms that iterate between solving a continuous relaxation and a mixed-integer relaxation of the original problems; such approaches currently exist in the literature for Mixed-Integer Linear Programs and convex MINLPs. Both cases exhibit the distinctive property that the continuous relaxation can be solved in polynomial time. In nonconvex MINLP such a property does not hold and the main innovations in this paper are tailored algorithmic methods to overcome such a difficulty. In this talk, we review the Feasibility Pump evolution from the original one proposed by Fischetti, Glover, and Lodi (2005) to the one addressed to nonconvex Mixed Integer Nonlinear Programming problems, one of the first effective heuristics proposed for general MINLPs.

We consider a network design application which is modeled as the two level network design problem under uncertainty. In this problem, one of the two available technologies can be installed on each edge and all customers of the network need to be served by at least the lower level (secondary) technology. The decision maker is confronted with uncertainty regarding the set of primary customers, i.e., the set of nodes that need to be served by the higher level (primary) technology. A set of discrete scenarios associated to the possible realizations of primary customers is available. The network is built in two stages. In the first stage the network topology must be determined. One may decide to install the primary technology on some of the edges in the first stage, or one can wait to see which scenario will be realized, in which case, edges with the installed secondary technology may be upgraded to primary technology, but at higher recovery cost. The overall goal is to build a spanning tree in the first stage that serves all customers by at least the lower level technology, and that minimizes the first stage installation cost plus the worst-case cost needed to upgrade the edges of that tree, so that the primary customers of each scenario can be served using the primary technology.

Using the recently introduced concept of recoverable robustness, we address this problem of importance in the design of telecommunication and distribution networks. We study the complexity of the problem on trees and provide mixed integer programming models for solving the problem on trees and on general graphs, respectively. Finally, we provide a qualitative study of the solutions in terms of robustness and recoverability and an assessment of the algorithmic performance of our branch-and-cut approach.

This is a joint work with Eduardo Alvarez-Miranda, S. Raghavan and Paolo Toth.