Boolean query optimization and the 0-1 hyperbolic sum problem. (English) Zbl 0870.68048

Summary: An “intelligent front-end” or “logic assistant”is an interactive program devised to assist the users of an information retrieval system in the formulation of their queries. In order to provide knowledge usable in such a program, we study a problem of query optimization with an average efficiency criterion. We formulate it as a new combinatorial optimization problem, which we call 0-1 hyperbolic sum, and provide an exact branch-and-bound algorithm and two heuristics (of simulated annealing and tabu search type) to solve it. Computational experience illustrating the effectiveness of the tabu search technique is reported.


68N99 Theory of software
68P15 Database theory
Full Text: DOI


[1] E. Aarts and J. Korst,Simulated Annealing and Boltzmann Machines (Wiley, 1989). · Zbl 0674.90059
[2] R.E. Burkard and F. Rendl, A thermodynamically motivated simulation procedure for combinatorial optimization problems, Europ. J. Oper. Res. 17 (1984) 169-174. · Zbl 0541.90070 · doi:10.1016/0377-2217(84)90231-5
[3] V. Cerny, A thermodynamical approach to the Traveling Salesman problem: An efficient simulation algorithm, J. Optimization Theory Appl. 45 (1985) 41-51. · Zbl 0534.90091 · doi:10.1007/BF00940812
[4] A. El Baamrani, Analyse the deux m?thodes heuristiques: m?thode de ?recuit? et m?thode de ?plus grande descente-plus petite remont?e?, B. Sc. Essay, Facult? Universitaire Catholique de Mons (supervised by P. Hansen) (1985).
[5] F. Glover, Future paths for integer programming and links with artificial intelligence, Comput. Oper. Res. 13 (1986) 533-549. · Zbl 0615.90083 · doi:10.1016/0305-0548(86)90048-1
[6] F. Glover, Tabu search methods in artificial intelligence and operations research, ORSA Artificial Intell. Newsletter 1 (1987) 2-6.
[7] F. Glover, Tabu search ? Part I, ORSA J. Comput. 1 (1989) 190-206. · Zbl 0753.90054
[8] F. Glover, Tabu search ? Part II, ORSA J. Comput. 2 (1990) 4-32. · Zbl 0771.90084
[9] F. Glover and H.J. Greenberg, New approaches for heuristic search: A bilateral linkage with artificial intelligence, Europ. J. Oper. Res. 39 (1989) 119-130. · Zbl 0658.90079 · doi:10.1016/0377-2217(89)90185-9
[10] P. Hansen, The steepest-ascent-mildest-descent heuristic for combinatorial programming, presentation at theConf. on Numerical Methods in Combinatorial Optimization, Capri, Italy (1986).
[11] P. Hansen and B. Jaumard, Algorithms for the maximum satisfiability problem, Computing 44 (1990), in press. · Zbl 0716.68077
[12] P. Hansen, M.V. Poggi de Arag?o and C.C. Ribeiro, Hyperbolic 0-1 programming and query optimization in information retrieval, to appear in Math. Programming Series B (1991).
[13] M.H. Heine, A simple intelligent front-end for information retrieval systems using Boolean logic, Inform. Technol. 2 (1982) 247-260.
[14] M.H. Heine, Information retrieval from classical databases from a signal detection stand point: A review, Inform. Technol. 3 (1984) 95-112.
[15] M.H. Heine, Automatic optimization of search logic, contribution to theRound Table Workshop on Techniques for Access to Information and its Re-Use, Luxemburg (1986).
[16] M.H. Heine, A logic assistant for the database researcher, Inform. Proc. Management 24 (1988) 323-329. · doi:10.1016/0306-4573(88)90098-2
[17] A. Hertz and D. de Werra, The tabu search metaheuristic ? How we used it, Ann. Math. AI 1 (1990) 111-121. · Zbl 0878.68053
[18] S. Kirkpatrick, C.D. Gelatt and M.P. Vecchi, Optimization by simulated annealing, Science 220 (1983) 671-674. · Zbl 1225.90162 · doi:10.1126/science.220.4598.671
[19] M.V. Poggi de Arag?o,Programa??o hiperb?lica em vari?veis 0-1 e otimiza??o de consultas a bancos de dados bibliogr?ficos, M. Sc. Dissertation, Catholic University of Rio de Janeiro, Rio de Janeiro, Brazil (1988).
[20] M. Queyranne, private communication (1987).
[21] G. Salton, A simple blueprint for automatic Boolean query processing, Inform. Proc. Management 24 (1988) 269-280. · doi:10.1016/0306-4573(88)90094-5
[22] D. Stephany, Localisation de postes en fonction du trafic interpostes, B. Sc. Essay, Facult? Universitaire Catholique de Mons (supervised by P. Hansen) (1986).
[23] C.J. Van Rijsbergen, Foundation of evaluation, J. Documentation 30 (1974) 365-373. · doi:10.1108/eb026584
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.