For Maximum 3-Satisfiability Problem (MAX 3SAT), 
we discuss about random test instance generation.

First, we analyze the expected number of unsatisfiable clauses 
on the optimal assignment.
We prove two lower bounds theoretically.
One is $\Omega(m / \ln m)$ for $m \ge 5.19 n$ 
and the other is $m/8 - O(\sqrt{mn})$ for $m \ge 9.7n$ 
where $n$ is the number of variables and $m$ is the number of clauses.
We also compare these theoretical lower bounds with experimental results.

Next, we propose a simple random test instance generator 
that takes the number of variables $n$ 
and the minimum number of unsatisfiable clauses $u$ 
as inputs and outputs an appropriate size test instance 
and its optimal solution with high probability.
For this algorithm, 
we analyze the number of clauses 
that is sufficient to output its optimal solution with high probability.
Theoretically, 
we prove the upper bound $8u + \Omega(n \ln n) + \Omega(n \sqrt{u \ln n})$.