0
$\begingroup$

I am trying to find a combinatorial approach to solve the following optimization problem.

\begin{align} &\max_{x_{ij}} C_{ij} x_{ij}, \\ &\text{such that},\\ &\sum_{j} x_{ij} \leq r_i~\forall i \in [N],\\ &\sum_{i} x_{ij} \leq c_j~\forall j \in [M],\\ &x_{ij} \geq 0~\forall i,j, \end{align} where the constants satisfy: $C_{ij} \geq 0$, $\sum_i r_i = 1$.

If $\sum_j c_j = 1$ then, I think, this problem is similar to the discrete (finite) optimal transport problem.

I am not interested in the most efficient solution approach. I am interested in an approach that reveals any interesting structure of a solution if such a structure exists.

In particular, is there a greedy algorithm (after sorting the weights $C_{ij}$) that solves this problem?

Improve this question
$\endgroup$
2
  • $\begingroup$ Once you reformulated the problem such that you have a nontrivial minimiser, check out the assignment problem and the Hungarian algorithm. $\endgroup$
    – Dirk
    Commented Oct 25, 2019 at 19:16
  • $\begingroup$ Now with max instead of min, the answer is not so clear to me anymore. You may check standard literature on optimal transport (not necessarily discrete) for results that don't assume positivity of the cost function (there are quite of lot of them). $\endgroup$
    – Dirk
    Commented Oct 26, 2019 at 8:35

1 Answer 1

Reset to default
1
$\begingroup$

As is, the minimum is zero... If the inequalities in the first two constraints are replaced by equalities, then the problem is indeed optimal transportation. In my experience the fastest and most scalable algorithm in practice is the one based on Sinkhorn algorithm using entropic regularization. This algorithm is described in:

https://arxiv.org/abs/1306.0895

some code can be found online as well.

Improve this answer
$\endgroup$
4
  • $\begingroup$ You are right about the minimizer, but I beg to differ about the Sinkhorn algorithm. It solves a regularized problem and if the regularization problem gets small, the convergence deteriorates (and you get numerical problems and need some more trick to make it work). Also OP is explicitly asking for combinatorial methods. $\endgroup$
    – Dirk
    Commented Oct 25, 2019 at 19:15
  • $\begingroup$ Yeah, the minimization was an error. I am interested in the maximization problem. Sorry about the confusion. $\endgroup$
    – Soumya Basu
    Commented Oct 25, 2019 at 22:22
  • $\begingroup$ @Dirk indeed you need some tricks to avoid rounding problems but if you have a large problem it's still the best method I would say. Solving the exact problem doesn't scale nearly as well except for low dimensional quadratic cost problems where you can do something special $\endgroup$
    – alesia
    Commented Oct 26, 2019 at 20:01
  • $\begingroup$ @SoumyaBasu then it is exactly optimal transportation as well as equalities will be attained in the constraints $\endgroup$
    – alesia
    Commented Oct 26, 2019 at 20:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .