Subset Coefficient Reduction Cuts for 0/1 Mixed-Integer Programming

From MaRDI portal





A method termed subset coefficient reduction to generate cuts for mixed-integer 0-1 programs is described. It is a general procedure designed to tighten both pure 0-1 and mixed 0-1 programming problems prior to the application of lp-based branch-and-bound algorithms. The idea of subset coefficient reduction is as follows: any inequality in continuous and/or 0-1 variables can be arranged to have the form (1) \(\Sigma_ Ia_ jx_ j+\Sigma_ Fa_ jx_ j+\Sigma_ Pa_ jx_ j-\Sigma_ Na_ jx_ j\geq b\), where \(a_ j\geq 0\) for all j, \(x_ j\in \{0,1\}\) for all \(j\in I\), \(x_ j\geq 0\) for all \(j\in P\cup N\) and \(0\leq x_ j\leq 1\) for all \(j\in F.\) If now \(K\subseteq I\), \(S\subseteq F\), \(b_ 0=b-\Sigma_ Ka_ j- \Sigma_ Sa_ j\), then a valid cut implied by (1) is (2) \(\Sigma_{I-K}\min \{b_ 0,a_ j\}x_ j+\Sigma_{F-S}a_ jx_ j+\Sigma_ Pa_ jx_ j\geq b_ 0.\) A way is indicated how to choose these subsets \(K\) and S in order to obtain cuts which are as tight as possible. Furthermore, the lifting of a mixed constraint and cuts obtained from minimal covers are described. Section 2) treats the case that more than one constraint are considered simultaneously, and section 3) is devoted to facet-defining properties of the cuts derived. Finally, the use of this methodology in solving a variety of fixed-charge problems is reported.











This page was built for publication: Subset Coefficient Reduction Cuts for 0/1 Mixed-Integer Programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3706846)