A Lagrangean decomposition for 0–1 hyperbolic programming problems

This paper deals with the solution of the 0–1 hyperbolic programming problem (maximization of the ratio of two linear or affine functions subject to linear constraints). The dominance of Lagrangean decomposition over Lagrangean relaxation has been proved for linear programs and for convex quadratic programs. We extend these results for hyperbolic problems whose objective function is nonlinear and nonconcave. We propose a new Lagrangean decomposition which combines solving a linear programming problem and a 0–1 unconstrained hyperbolic programming problem. Computational experiments devoted to the 0–1 hyperbolic knapsack problem are reported.