Using decision oracle to solve optimization problem of maximum polyomino tiling
Although the shape of the problem instance is constrained, we still have total control over the polyominos themselves in any problem instance we decide to create, and we can get there by carefully messing with them.

A gangly polyomino in a double-width problem instance

Given the initial $a \times b$ problem instance, create a new instance of size $(2a+1) \times (b+1)$ in which each polyomino's width has been doubled, and a new polyomino has been added that consists of a row of $2a+1$ blocks with a column of $b$ blocks hanging below its leftmost block (thus giving it a total height of $b+1$) and a double-width copy of polyomino $p_1$ (the template polyomino) below the top row and to the right of the left column but pushed up and left as far as it will go, so that at least one block of column 2 below row 1 is occupied, and at least one block of row 2 to the right of column 1 is occupied. Intuitively, because all other polyominos have even width, the only way to fill up the odd-width rectangle we have is to use this gangly new polyomino, in which case its horizontal and vertical "arms" must form the topmost row and leftmost column, respectively.

Let the size of an optimal solution to the original problem be $k$ (this can be found in $O(\log {ab})$ time with binary search using only decision problem oracle calls). Iff there is a solution to the newly constructed decision problem instance with size $2k+(2a+1)+(b+1) = 2(k+a)+b+2$, then there is a solution to the original instance that has $p_1$ in its top-left corner.

If the answer is "no", try the same instance again but with a different template polyomino: form the gangly polyomino by pressing $p_2$ into the top-left corner instead of $p_1$. Repeat this until you find you hit a "yes" instance. If none of the polyominos results in a "yes" instance when pressed into the top-left corner, start again with $p_1$ but one block down from where it was in the first constructed problem, and with the blocks at positions $(2, 2)$ and $(2, 3)$ also filled in. Why? These represents a (double-width) block that we know must remain empty in every optimal solution (since if there was some optimal solution where it was covered by a polyomino, we would have found it by now). Add 2 to the target value for the decision problem to compensate for the added filler blocks.

If performing this down-one-row move would cause the polyomino to extend past the bottom of the range, add the 2 filler blocks as usual but instead move the template polyomino back up to the top (so that its topmost block occupies row 2) and as far left as possible so as to not overlap any existing block.

In general, a constructed instance with $f$ filler blocks gets $f$ added to its decision problem target.

Once you hit a "yes" instance, you know that this placement of the template polyomino is part of some optimal solution, so you keep that placement of the template in the gangly polyomino from that point on. Form the next problem with the next available polyomino as template immediately below the last one, or flush with the top and to the right as usual.

Time complexity

Each time we try all $n$ polyominos at some position, we add at least 2 blocks (either 2 filler blocks, or the double-width blocks corresponding to some input polyomino) to the gangly polyomino. We can only add at most $ab$ such pairs of blocks before it is no longer possible to obtain a "yes" answer, so at most $abn$ calls to the decision oracle suffice.