Valid inequalities and branch‐and‐cut for the clique pricing problem

Motivated by an application in highway pricing, we consider the problem that consists in setting profit‐maximizing tolls on a clique subset of a multicommodity transportation network. We formulate the problem as a linear mixed integer program and propose strong valid inequalities, some of which define facets of the two‐commodity polyhedron. The numerical efficiency of these inequalities is assessed by embedding them within a branch‐and‐cut framework.