We consider a measure of cooperativity based on the minimal interaction required to generate an observed titration behavior. We describe the corresponding algebraic optimization problem and show how it can be solved using the nonlinear algebra tool SCIP. Moreover, we compute the minimal interactions and minimal molecules for several binding polynomials that describe the oxygen binding of various hemoglobins under different conditions. We compare their minimal interaction with the maximal slope of the Hill plot, and discuss similarities and discrepancies with a view towards the shapes of the binding curves.