AUTHORS: Graca Marques Goncalves, Lidia Lampreia Lourenco
Download as PDF
In this article we investigate the Web Search Optimization Problem, a NP-hard combinatorial optimization problem arising from Software Design. This is a new problem in the combinatorial optimization area. We develop a natural mixed integer linear programming formulation for this problem. The natural model is strengthened by including in the model valid inequalities. Computational experiments show that, in most cases, the strengthened model gives an integer solution for the problem. The lower bounds obtained by the strengthened model relaxation of the considered formulation improve upon those obtained by the natural model relaxation
KEYWORDS: Web Search Optimization, Natural Strengthened Formulation, Valid Inequalities.
REFERENCES:
[1] Billionnet A. (2005). ”Different formulations
for solving the heaviest k-subgraph problem”.
Information Systems and Operational Research
43 (3): 171-186.
[2] Bruglieri, M., Ehrgott, M., Hamacher, H. and
Maffioli, F. (2006). ”An annotated bibliography
of combinatorial optimization problems with
fixed cardinality constraints”. Discrete Applied
Mathematics, 154, pp. 1344-1357.
[3] Fan, W., Gordon, M., Pathak, P., Xi, W., Fox,
E. (2004). ”Ranking Function Optimization For
Effective Web Search By Genetic Programming: An Empirical Study”. Proceedings of the
37th Hawaii International Conference on System Sciences, pp. 1-8.
[4] M. R. Garey and D. S. Johnson, Computers
and intractability: a guide to the teory of NPcompleteness, San Francisco: W. H. Freeman
and Company, 1979.
[5] Hansen, P. and Jaumard, B. (1997). ”Cluster analysis and mathematical programming”.
Mathematical Programming, 79, pp. 191-215.
[6] Park, K., Lee and Park, S. (1996). ”An
extended formulation approach to the edgeweighted maximal clique problem”. European
Journal of Operational Research, 95, pp. 671-
682.
[7] Zeng, H., He, Q., Chen, Z., Ma, W., Ma, J.
(2004). ”Learning to Cluster Web Search Results”, SIGIR ’04 Proceedings of the 27th annual international ACM SIGIR conference on
Research and development in information retrieval, pp. 210-217.
