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?

  • $\begingroup$ Once you reformulated the problem such that you have a nontrivial minimiser, check out the assignment problem and the Hungarian algorithm. $\endgroup$ – Dirk Oct 25 '19 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 Oct 26 '19 at 8:35

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:


some code can be found online as well.

  • $\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 Oct 25 '19 at 19:15
  • $\begingroup$ Yeah, the minimization was an error. I am interested in the maximization problem. Sorry about the confusion. $\endgroup$ – Soumya Basu Oct 25 '19 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 Oct 26 '19 at 20:01
  • $\begingroup$ @SoumyaBasu then it is exactly optimal transportation as well as equalities will be attained in the constraints $\endgroup$ – alesia Oct 26 '19 at 20:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.