Partitioning a boolean circuit for automatic parallelization
One approach for formulating this as an ILP problem could be to have zero-or-one variables $x_{i,t},y_{i,t},z_t$, with the intended meaning that $x_{i,t}=1$ if the $i$th gate is evaluated in the $t$th instruction (not as part of a batch), or $x_{i,t}=0$ otherwise; and $y_{i,t}=1$ if the $i$th gate is evaluated in a batch in the $t$th instruction, or $y_{i,t}=0$ otherwise; and $z_t=1$ if the $t$th instruction is a batch instruction, or $z_t=0$ otherwise.

Your problem can then be represented as an integer linear program, with some constraints to enforce consistency of these boolean variables:


Each gate is assigned to a single instruction: $\sum_t x_{i,t} + y_{i,t}=1$.
Non-batch instructions are assigned a single gate: $\sum_i x_{i,t} = 1-z_t$.
Non-batch instructions don't set any $y$ values: $\sum_i y_{i,t} \le C z_t$, where $C$ is a large constant equal to the maximum batch size (or the number of gates, if there is no limit).
Gates can only be batched together if they compute the same logic function: $y_{i,t} + y_{j,t} \le 1$ for each pair of gates $i,j$ that have a different logic function.
A gate can only be evaluated once all of its inputs are ready: $x_{i,t} + y_{i,t} \ge x_{j,u} + y_{j,u}$ for each pair of gates $i,j$ such that the output of $i$ is an input to $j$, and for each pair $t,u$ with $t&lt;u$.


(I'll assume you treat NOT gates as free and don't try to assign them to any instruction; they just happen automatically.)

Now any consistent assignment to the $x$'s and $y$'s will correspond to a valid way to implement the circuit.  The cost of this assignment will be $9 \sum_t z_t + c \sum_{i,t} y_{i,t} + k$, where $c$ is the tiny proportional term and $k$ is the total number of instructions in the schedule (both $c$ and $k$ are constants).  If you pick a value for $k$, the maximum number of instructions allowed, you can use an ILP solver to minimize $9 \sum_t z_t + c \sum_{i,t} y_{i,t} + k$ subject to the inequalities above, and this will give you the best way to schedule your boolean circuit using $k$ instructions. Then, I suggest you search over different values of $k$, solving an ILP for each one, to find the best boolean circuit.

Be prepared: ILP is NP-hard, so finding the optimal solution might take a very long time if the circuit is large and you're aren't very lucky.  Some ILP solvers have the ability to terminate their search after a fixed time limit and return the best solution they've found so far, which might be useful if that happens.