Applications of reformulations in mathematical programming
- PDF / 95,169 Bytes
- 2 Pages / 439.37 x 666.142 pts Page_size
- 45 Downloads / 158 Views
Applications of reformulations in mathematical programming Alberto Costa
Received: 10 November 2012 / Revised: 14 November 2012 © Springer-Verlag Berlin Heidelberg 2012
This is a summary of the author’s PhD thesis supervised by Pierre Hansen, Leo Liberti, and Ider Tseveendorj and defended on September 18, 2012 at École Polytechnique, Palaiseau, France. The thesis is written in English and is available from the author upon request at [email protected] and from http://pastel.archives-ouvertes. fr/pastel-00746083. This work concerns the study of some Mathematical Programming problems and the analysis of the impact given by the application of some reformulation techniques for solving such problems. We considered the following classification of reformulations: exact reformulations (also called opt-reformulations), narrowings, relaxations (see Liberti, “Reformulations in Mathematical Programming: Definitions and Systematics”, RAIRO-OR, 43(1):55–86, 2009). For each kind of reformulation a different problem is considered, and it is shown that the reformulation was crucial to obtain a good solution. The first part of the thesis concerns exact reformulations, where the set of global and local optima are the same as in the original formulation. The main problem studied is that of clustering by means of modularity maximization. Some exact methods and several heuristics are proposed in the literature to solve this problem. We focus on one of these heuristics, namely a hierarchical divisive approach that iteratively divides a cluster in two new clusters in an optimal way, by using a 0–1 Mixed Integer Quadratic Programming (MIQP) model solved by CPLEX, until the modularity increases. Some reformulations of this model are proposed, leading to a reduction of the computational time by an order of magnitude. We then adapt the divisive heuristic to bipartite graphs, where the objective function to maximize is bipartite modularity. In this case the problem cannot be described by using a 0–1 MIQP model, thus different reformulations are employed. Tests showed the high impact of reformulation techniques on computational time, and also a good quality of the results in term of bipartite modularity value if compared with those obtained by other heuristics. After that, another contribution related to clustering is presented. In fact, one can find clusters by specifying some rules that each cluster must respect. We considered one of these criteria, called strong (see Radicchi et al., “Defining and identifying communities in networks”, PNAS, 101(9):2658–2663, 2004), and we modified it obtaining a new
123
A. Costa
criterion that is called almost-strong. We then devised an algorithm to find clusters in the strong and almost-strong sense. A comparison of the results showed that the almost-strong criterion provided more informative partitions with respect to the strong one. The second part of the thesis concerns narrowing reformulations, where the reformulated problem can have fewer global optima than the original one. This is usefu
Data Loading...
