A branch-and-cut algorithm without binary variables for nonconvex piecewise linear optimization

作     者：Keha, Ahmet B. de Farias, Ismael R., Jr. Nemhauser, George L. 

作者机构：Arizona State Univ Dept Ind Engn Tempe AZ 85287 USA SUNY Buffalo Dept Ind Engn Buffalo NY 14260 USA Georgia Inst Technol Sch Ind & Syst Engn Atlanta GA 30332 USA 

出 版 物：《OPERATIONS RESEARCH》 (运筹学)

年 卷 期：2006年第54卷第5期

页      面：847-858页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：piecewise linear function special-ordered set branch-and-cut 

摘      要：We give a branch-and-cut algorithm for solving linear programs (LPs) with continuous separable piecewise-linear cost functions (PLFs). Models for PLFs use continuous variables in special-ordered sets of type 2 (SOS2). Traditionally, SOS2 constraints are enforced by introducing auxiliary binary variables and other linear constraints on them. Alternatively, we can enforce SOS2 constraints by branching on them, thus dispensing with auxiliary binary variables. We explore this approach further by studying the inequality description of the convex hull of the feasible set of LPs with PLFs in the space of the continuous variables, and using the new cuts in a branch-and-cut scheme without auxiliary binary variables. We give two families of valid inequalities. The first family is obtained by lifting the convexity constraints. The second family consists of lifted cover inequalities. Finally, we report computational results that demonstrate the effectiveness of our cuts, and that branch-and-cut without auxiliary binary variables is significantly more practical than the traditional mixed-integer programming approach.