  We study rigorously a lattice gas version of the Sherrington-Kirckpatrick
spin glass model. In discrete optimization literature this problem is known as
Unconstrained Binary Quadratic Programming (UBQP) and it belongs to the class
NP-hard. We prove that the fluctuations of the ground state energy tend to
vanish in the thermodynamic limit, and we give a lower bound of such ground
state energy. Then we present an heuristic algorithm, based on a probabilistic
cellular automaton, which seems to be able to find configurations with energy
very close to the minimum, even for quite large instances.
