Instance generating algorithms for MAX2SAT are proposed.
The algorithms produce instances with their optimal solutions.
We propose two types of algorithms:
a constructive one and a randomized one.
In the former, nontrivial 2-CNF instances are produced
using expander graphs explicitly constructed.
On the other hand, in the latter,
more complicated instances are produced
although it is with high probability that
produced solutions are optimal ones.