TransWikia.com

The transportation problem with uncertain (and, in general, linearly interdependent) supply- and demand values

Mathematics Asked by Rasus on January 7, 2021

I’m looking at a transportation problem:
$$min_{x_{ij}} sum_{i=1}^{m}sum_{j=1}^{n} c_{ij}x_{ij}$$
subject to
$$sum_{j=1}^nx_{ij} = s_i, mbox{ for all } i=1,…,m.$$
and
$$sum_{i=1}^mx_{ij} = d_j, mbox{ for all } j=1,…,n.$$
The problem can be assumed to be balanced $ sum_{i=1}^m s_i = sum_{j=1}^n d_j $, and values $c_{ij}$, $s_{i}$ and $d_{j}$ are non-negative.

Normally the values of $s_i$ and $d_i$ are known and the problem can be solved by using general linear programming solvers (simplex) or by methods that utilize special structure of the problem (such as MODI). However, in my case a subset of the supply- and demand values are only known within some upper bound and can be linearly interdependent in general. For example:

$$ s = ( 1,1, epsilon_1, epsilon_1, 1, epsilon_3, 1,…)circ(S_1, S_2, …, S_m)$$
and
$$ d = ( epsilon_2,epsilon_1, 1, 1, 1, 1,…)circ(D_1, D_2, …, D_n)$$

Where $S_i$ and $D_j$ are known values, but the values of $epsilon_kin[0,1]$, $k=1,…,l$ are uncertain.

I need to find a method for calculating the worst case transportation cost:

$$max_{epsilon_kin[0,1]} min_{x_{ij}} sum_{i=1}^{m}sum_{j=1}^{n} c_{ij}x_{ij}$$

subject to the constraints described previously.

I have tried to reformulate the problem as a robust linear programming problem. But it seems to me that the row-wise approach used in the robust methods is not applicable since the rows in my constraints are linearly interdependent within the uncertainty set. Furthermore we have "$=$" constraints and not "$leq$" constraints, and if I convert each "$=$" constraint to two $leq$ constraints I get more rows that are dependent on each other.

Maybe some magic duality-trick can convert the problem into a plain vanilla linear programming problem? Maybe it can be solved as a (linear) bi-level programming problem? – I just cant see how… Please help.

update 29/12-2020:

Thanks to @Mark L. Stone for suggesting the KKT conditions as constraints. I added the dual values $u_i$, $v_j$ and optimality-constraints for the inner problem: $x_{ij}(u_i+v_j-c_{ij}) = 0$ and $u_i+v_j-c_{ij} leq 0$. If I replace the inner minimization problem with these constraints I am left with a constrained maximization problem with non-linear constraints (first optimality-constraint). However, the non-linearity is only introduced to "select" the equality-constraints corresponding to the allocated cells. I can convert the problem to a mixed-integer linear program, but I don’t think that will be easier to solve. Are there any way to get rid of this non-linearity or is it possible to solve this kind of linear problem, where some subset of the constraints are "selected"?

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP