A polynomial multicommodity flow problem with difficult path generation
In the paper we consider a commonly known network design problem with demand restoration assuming stub release. No compact linear programming (LP) formulation for the problem is known, and all known non-compact LP formulations of the problem require NP-hard path generation (pricing). Therefore, the problem itself is suspected to be NP-hard - this, however, is not actually known. The main result of