GRASP for linear integer programming

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2004

Autores

Neto, T (Autor) Outra; Pedroso, JP (Autor) FCUP

Ata de Conferência Internacional

Título: Metaheuristics: Computer Decision-Making

Páginas: 545-+

Indexação

ISI Web of Knowledge - 0 Citações

Classificação Científica

FOS: Ciências da engenharia e tecnologias > Biotecnologia industrial

Outras Informações

ID Authenticus: P-000-D7V

DOI: 10.1007/978-1-4757-4137-7_26

Abstract (EN): In this paper, we introduce a GRASP for the solution of general linear integer problems. The strategy is based on the separation of the set of variables into the integer subset and the continuous subset. The integer variables are fixed by GRASP and replaced in the original linear problem. If the original. problem had continuous variables, it becomes a pure continuous problem, which can be solved by a linear program solver to determine the objective value corresponding to the fixed variables. If the original problem was a pure integer problem, simple algebraic manipulations can be used to determine the objective value that corresponds to the fixed variables. When we assign values to integer variables that lead to an impossible linear problem, the evaluation of the corresponding solution is given by the sum of infeasibilities, together with an infeasibility flag. We report results obtained for some standard benchmark problems, and compare them to those obtained by branch-and-bound and to those obtained by an evolutionary solver.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 28