Abstract. Protein-protein docking is a challenging computational problem in functional genomics, particularly when one or both proteins undergo conformational change(s) upon binding.  The major challenge is to define scoring function soft enough to tolerate these changes and specific enough to distinguish between near native and ‘misdocked’ conformations.  Using a linear programming (LP) technique, we derived protein docking potentials (PDPs) that comply with this requirement. We considered a set of 63 non-redundant complexes to this aim, and generated 400,000 putative docked complexes (decoys) based on shape complementarity criterion for each complex. The PDPs were required to yield for the native (correctly docked) structure a potential energy lower than those of all the non-native (misdocked) structures. The energy constraints applied to all complexes led to a total of ca. 25 million inequalities, the simultaneous solution of which yielded an optimal set of PDPs that discriminated the correctly docked (up to 4.0 Å root-mean-square deviation from known complex structure) structure among the 85 top-ranking (0.02%) decoys in 59/63 examined bound-bound cases.  The high performance of the potentials was further verified in jackknife tests and by ranking putative docked conformation submitted to CAPRI. In addition to their utility in identifying correctly folded complexes, the PDPs reveal biologically meaningful features that distinguish docking potentials from folding potentials.