A Comparison of Mixed-Integer Programming Models for Nonconvex Piecewise Linear Cost Minimization Problems
研究具有可分离非凸分段线性成本的最小化问题，证明三种经典混合整数规划模型的线性规划松弛都逼近成本函数的下凸包络，并揭示该结果与拉格朗日对偶理论的关系。
We study a generic minimization problem with separable nonconvex piecewise linear costs, showing that the linear programming (LP) relaxation of three textbook mixed-integer programming formulations each approximates the cost function by its lower convex envelope. We also show a relationship between this result and classical Lagrangian duality theory.