I have $n$ people. I want assign them to $c$ jobs. A job may be not assigned at all or there must be a minimum and maximum number of people assigned to it. $n$ is about 4000 and $c$ is about 1000.
The linear programming mode is as follows. There is an $OR$ condition in constraints. I have seen some methods (pp. 78) to add an extra boolean variable $y\in\{0,1\}$ and a large constant $M$.
Is there any simpler model I can use for the problem. Is there any polynomial solution for the problem?
$\min \sum_{i,j} c_{i,j} x_{i,j}$
$s.t.$
$(1)$ $\sum_j x_{i,j}=0 \ \ \ \ \ \ \forall i=\{1,2,\ldots c\}$
OR
$(2)$ $ 2\leq \sum_j x_{i,j} < 4 \ \ \ \ \forall i=\{1,2,\ldots c\}$
AND
$(3)$ $\sum_i x_{i,j}=1 \ \ \ \ \ \forall j=\{1,2,\ldots n\}$
I mean that $(3)$ is mandatory and at least ($(1)$ or $(2)$) must be true for all $i$ (Any $i$ is considered separetely). $c_{i,j}$ is known.
A linear program must be posed such that the feasible set is a convex polytope. In your case, it is easy to simply solve two separate linear programs and combine the result, however. One program satisfies (1) and (3), while one satisfies (2) and (3). Solve these programs separately, and pick whichever has lower optimal objective value.