Groupe d’études et de recherche en analyse des décisions

G-97-07

Maximizing the Product of Two Linear Functions in 0-1 Variables

, , et

We study both the continuous and discrete problems of maximizing the product of two linear functions subject to all variables being between 0 and~1. We first give linear and low-order polynomial algorithms for the solution of the continuous problem. In addition, we describe penalties that help to fix variables in the discrete problem. Extensive computational tests demonstrate the effectiveness of these results.

, 28 pages