Valid Inequalities for the Lasdon-Terjung Production Model
研究一个简单的单产品生产整数规划模型，通过添加一类简单有效不等式和启发式切割选择，大幅缩小分支定界树规模，甚至无需分支定界即可求解。
AbstractWe consider a very simple integer program involving production of a single item and start-up costs for the standard machines first studied by Lasdon and Terjung. Solving directly as an integer program leads to prohibitively large branch and bound trees. Here, we show how using a simple family of valid inequalities and a heuristic procedure to choose one of these inequalities as a cut, it is possible to reduce substantially the size of the tree, and in several cases to eliminate the need for branch and bound. The valid inequalities used are all simple Gomory cuts. However, they are derived from the initial problem formulation rather than from the optimal linear programming tableau.Keywords: Machine SchedulingLot-Sizing ModelsInteger ProgrammingStart-Up CostsCutting PlanesPolyhedral Combinatorics