I have some problems to solve a two dimensional 01 programming problem. The problem has a similar body as follows,
${\text{min}}_{\{x_{ij}\}} \sum_i \sum_j x_{ij} c_{ij}$
s.t. $\sum_i x_{ij} \leq 1$
$\sum_j x_{ij} \leq 1$
$x_{ij} \in \{0,1\}$
The range of $i$ and $j$ are large. I think for one dimensional variable $x_i\in\{0,1\}$, the problem can be solved by bisection method or Dinkelbach method. While as the problem has constraints in two dimension $i$ and $j$, I am not sure if these methods can still be effective. Moreover, since the variable matrix $X=\{x_{ij},\forall i,j\}$ is a sparse matrix, I wonder if there are some matrix related methods that can solve this problem. I'd like to ask about mathematic methods rather than computing tools such as CPLEX.
Thanks a lot if you guys can give me some advices!
The problem is equivalent to finding a maximum weight matching in a bipartite graph, also known as the weighted bipartite matching problem; it can be solved efficiently with combinatorial algorithms, without the need of a general solver such as CPLEX. In fact, since they are combinatorial, they can solve the problem without any numerical error, and if the $c$ matrix is sparse, they are faster. The algorithms are not so simple that I can describe them here shortly, however they are very well-known algorithms of combinatorial optimization and they are not hard to implement. You will find a lot of material on the web if you search for "weighted bipartite matching".
Side note (although you probably already realized this): the problem is only interesting when some of the $c_{ij}$ are negative, otherwise the optimal solution is $x=0$.