Reducing optimization problem to its decision version
Use binary search on the target $A$, finding the maximal value for which an assignment of average compatibility $A$ exists.

I'll let you work out the resulting multiplicative overhead (which depends on the magnitude of the numbers involved).