0
$\begingroup$

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!

$\endgroup$
1
  • $\begingroup$ The question is confusing. A 'two dimensional' problem usually refers to a problem in two variables. I would change the title into 'how to solve a 0-1 problem with a matrix variable' $\endgroup$ Commented Dec 24, 2018 at 9:09

1 Answer 1

Reset to default
0
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.