How to perform automated mining in regtest mode?
The miner can generate a block candidate with the getblocktemplate call, which uses certain heuristics to construct an approximation of an fee-optimised block given the current local mempool state. 

1) The question in regards to when to begin mining 

Generally, the miner will want to begin mining the next block as soon as the strong chain is extended, maximising the time available to search for the solution. 

However, consider building an optimal block template from a growing number of unconfirmed transactions being accepted into the mempool. This means a transaction selection so that total block fee reward is optimised, whilst ensuring no double-spend. A growing mempool provides a greater optimisation space, but takes time. Solving for the exact optimal block from an increasingly large pool of valid transactions is NP-Hard (knapsack/max independent sets) and expensive.

At some point, the gains in fee rewards of solving this optimisation problem will be offset by the opportunity cost of the miner (during optimisation, the miner hashing equipment will necessarily be idle). Simpler heuristics may optimise for a less than optimal block template (as in getblocktemplate), but enables the miner to begin mining immediately.

If you wish to apply your own block template solver, you can get a mempool dump via 
getrawmempool (not very efficient to acquire over RPC).

2) Regarding regtest in a local network

Is it possible to create bitcoind regtest network on Ubuntu (which itself is on Virtualbox)?