Does the WP-Optimize page cache work with query parameter-based permalinks?

No. It’s necessary to have pretty permalinks of the type http://xxxxx.com/my-post/ rather than http://xxxxx.com/?p=1234. Pretty permalinks are the WordPress default setting, and there is no good reason to turn them off, so you should not have a problem with this.

Note that permalinks including /index.php/ are cacheable. It is only those based upon query parameters (?…) that are not.