An objective function is supposed linear. The variable vector is separated into two subvectors \(x\) and \(y\) and it is supposed that \((x, y)\) belongs to a convex set, \(x\) and \(y\) belong to the polytopes, \(y\) belongs to the complement of an open convex set. The problem is decomposed in such a way that global optimization is performed only in \(y\). Two realizations are presented. The first is based on conical branch-and-bound techniques and polyhedral outer approximation. The second relies on cutting plane techniques. Results of experiments show that the algorithms work well for the problems with small dimensionality of \(y\) but dimensionality of \(x\) is not very important.