In this paper we combine some results that are published elsewhere. We prove that tight upperbounds can be given for the number of non-unique assignments that remain after solving the linear programming relaxation of some types of assignment problems.
For the generalized assignment problem and time table problems we will give these bounds explicitly.
Moreover, we will give bounds for the required capacity to ensure easy solutions.
Keywords: mixed integer problems, assignment problems, time tables, linear programming.