  We consider the regular balanced model of formula generation in conjunctive
normal form (CNF) introduced by Boufkhad, Dubois, Interian, and Selman. We say
that a formula is $p$-satisfying if there is a truth assignment satisfying
$1-2^{-k}+p 2^{-k}$ fraction of clauses. Using the first moment method we
determine upper bound on the threshold clause density such that there are no
$p$-satisfying assignments with high probability above this upper bound. There
are two aspects in deriving the lower bound using the second moment method. The
first aspect is, given any $p \in (0,1)$ and $k$, evaluate the lower bound on
the threshold. This evaluation is numerical in nature. The second aspect is to
derive the lower bound as a function of $p$ for large enough $k$. We address
the first aspect and evaluate the lower bound on the $p$-satisfying threshold
using the second moment method. We observe that as $k$ increases the lower
bound seems to converge to the asymptotically derived lower bound for uniform
model of formula generation by Achlioptas, Naor, and Peres.
