A strengthened model for the web search optimization problem

Research output: Contribution to journalArticle

Abstract

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.

Original languageEnglish
Pages (from-to)143-148
Number of pages6
JournalWSEAS Transactions on Mathematics
Volume18
Publication statusPublished - 1 Jan 2019

Fingerprint

Linear Programming
Software Design
Search Problems
Web Search
Research Design
Optimization Problem
Combinatorial optimization
Valid Inequalities
Model
Mixed Integer Linear Programming
Formulation
Combinatorial Optimization
Software design
Combinatorial Optimization Problem
Computational Experiments
Linear programming
NP-complete problem
Optimization problem
Web search
Lower bound

Keywords

  • Natural Strengthened Formulation
  • Valid Inequalities
  • Web Search Optimization

Cite this

@article{d6ac0d94f83b4889a827ae60bfebd826,
title = "A strengthened model for the web search optimization problem",
abstract = "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 = "Natural Strengthened Formulation, Valid Inequalities, Web Search Optimization",
author = "Gon{\cc}alves, {Gra{\cc}a Marques} and Louren{\cc}o, {L{\'i}dia Lampreia}",
note = "UID/MAT/00297/2019#",
year = "2019",
month = "1",
day = "1",
language = "English",
volume = "18",
pages = "143--148",
journal = "WSEAS Transactions on Mathematics",
issn = "1109-2769",
publisher = "World Scientific and Engineering Academy and Society",

}

TY - JOUR

T1 - A strengthened model for the web search optimization problem

AU - Gonçalves, Graça Marques

AU - Lourenço, Lídia Lampreia

N1 - UID/MAT/00297/2019#

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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.

AB - 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.

KW - Natural Strengthened Formulation

KW - Valid Inequalities

KW - Web Search Optimization

UR - http://www.scopus.com/inward/record.url?scp=85067346285&partnerID=8YFLogxK

M3 - Article

VL - 18

SP - 143

EP - 148

JO - WSEAS Transactions on Mathematics

JF - WSEAS Transactions on Mathematics

SN - 1109-2769

ER -