Influence of the normalization constraint on the integral simplex using decomposition

详细信息    查看全文

• 作者：Samuel Rosat^a ; ^c ; ^{samuel.rosat@gerad.ca} ; Issmail Elhallaoui^a ; ^c ; ^{issmail.elhallaoui@gerad.ca} ; Franç ; ois Soumis^a ; ^c ; ^{francois.soumis@gerad.ca} ; Driss Chakour^b ; ^c ; ^{driss.chakour@polytechnique.edu}
• 关键词：0&ndash ; 1 programming ; Set partitioning problem ; Primal algorithms ; Normalization constraint ; Augmenting algorithms
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：30 January 2017
• 年：2017
• 卷：217
• 期：part_P1
• 页码：53-70
• 全文大小：631 K
• 卷排序：217

文摘

Since its introduction in 1969, the set partitioning problem has received much attention, and the structure of its feasible domain has been studied in detail. In particular, there exists a decreasing sequence of integer feasible points that leads to the optimum, such that each solution is a vertex of the polytope of the linear relaxation and adjacent to the previous one. Several algorithms are based on this observation and aim to determine that sequence; one example is the integral simplex using decomposition (ISUD) of Zaghrouti et al. (2014). In ISUD, the next solution is often obtained by solving a linear program without using any branching strategy. We study the influence of the normalization-weight vector of this linear program on the integrality of the next solution. We extend and strengthen the decomposition theory in ISUD, prove theoretical properties of the generic and specific normalization constraints, and propose new normalization constraints that encourage integral solutions. Numerical tests on scheduling instances (with up to 500,000 variables) demonstrate the potential of our approach.