Mixed Integer Programming (MIP) solvers have reached a remarkable efficiency for a wide range of optimization problems in recent years. There are however some classes of problems which “resist”. Among others, these are classes of vehicle routing, scheduling, network design problems. For many of them, there are no known compact MIP formulations with a strong linear relaxation after adding generic or even problem-specific cutting planes. Extended formulations with an exponential number of variables solved by branch-cut-andprice (BCP) algorithms may come to the rescue in this case. BCP algorithms are however
competitive with modern MIP solvers only if the extended formulation has much stronger linear relaxation than known compact formulations. Non-robust cuts, i.e. cuts expressed in the space of extended variables, often help us to obtain such relaxation and help BCP algorithms to achieve state-of-the-art efficiency. In this tutorial, we will review some families of known nonrobust
cutting planes. We will also discuss issues which may arise while using non-robust cuts, including their impact on the solution time of the pricing problem, implementation difficulties, and generality/efficiency trade-off. Some recommendations on how to overcome these issues will be given.