|
 
|
[BIL02] Approximate and exact solution methods for the hyperbolic 0-1 knapsack problem
Revue Internationale avec comité de lecture : Journal INFOR, vol. 40(2), pp. 97-110, 2002
motcle:
Résumé:
The hyperbolic 0-1 knapsack problem (HKP) to obtain a 0-1 solution that maximizes a linear fractional objective function under the constraint of one linear inequality is considered. First it is shown how to find approximate solutions of this problem with a given accuracy by solving successively two mixed integer linear programs. Then, six mixed integer programming-based strategies are compared for finding exact solutions of HKP. Some of these strategies exploit the knowledge of an approximate solution. The computational results that are reported give a comparison of the different strategies and show the efficiency of one of them since it allows instances comprising up to 10,000 variables to be solved.
Keywords: Fractional 0-1 programming, Hyperbolic 0-1 knapsack problem, Mixed integer programming, Approximate solutions, Exact solutions, Computational experiments.
BibTeX
| @article { | |||
| BIL02, | |||
| title | = | "{Approximate and exact solution methods for the hyperbolic 0-1 knapsack problem}", | |
| author | = | "A. Billionnet", | |
| journal | = | "INFOR", | |
| year | = | 2002, | |
| volume | = | 40, | |
| number | = | 2, | |
| pages | = | "97-110", | |
| } | |||
