Partitioning problem

From Glossary

Jump to: navigation, search

This is the combination of packing and covering. Its IP form is LaTeX: \textstyle \mbox{Opt}\left \{cx: Ax=b, x \in \left \{0,1 \right \}^n \right \}, where Opt could be Min or Max, and LaTeX: A is a 0-1 matrix. The equation LaTeX: \textstyle A(i,.) x = b_i means that exactly LaTeX: b_i elements must be selected from set LaTeX: i. In particular, a multiple choice constraint is LaTeX: \textstyle \sum_j x_j = 1.

Personal tools