Subset Coefficient Reduction Cuts for 0/1 Mixed-Integer Programming
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.
- Strong formulations for mixed integer programming: A survey
- Valid inequalities and facets of the capacitated plant location problem
- Some properties of cliques in 0-1 mixed integer programs
- Efficient reformulation for 0-1 programs -- methods and computational results
- A recursive procedure to generate all cuts for 0-1 mixed integer programs
- Valid inequalities and separation for capacitated fixed charge flow problems
- Zero-coefficient cuts
- Variablenfixierungen in gemischt-ganzzahligen linearen 0-1-Optimierungsaufgaben
- Subset Algebra Lift Operators for 0-1 Integer Programming
- Generalized coefficient strengthening cuts for mixed integer programming
- Lattice based extended formulations for integer linear equality systems
- Coefficient strengthening: a tool for reformulating mixed-integer programs
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)