0
$\begingroup$

I would like to know if there is a method to solve the Problem.

Problem:
Maximize the following function: $$f(p_{1,i},p_{2,i},\dotsc,p_{m,i})=\sum_{i=1}^{n}\begin{bmatrix}p_{1,i} & p_{2,i} & \cdots & p_{m,i} \end{bmatrix}*\begin{bmatrix}e_1 \\ e_2 \\ \vdots \\ e_m \end{bmatrix} * c_i$$

where we know the values of each $e_j$ ($j \in \{1, \dotsc, m\}$) and $c_i$.
The values of the $p_{j,i}$ should be either 1 or 0 and we have the following constraints:

  1. For all $j \in \{1,\dotsc,m\}$: $\sum_{i=1}^n p_{j,i} \le 1$.
  2. For all $i \in \{1,\dotsc,n\}$: $\sum_{j=1}^m p_{j,i} = t_i$, where $t_i$ is a known value.

I would be grateful for every hint, method or solution.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
4
$\begingroup$

This is the transportation problem in a bipartite network, with a supply of $1$ at each $j$ node and a demand of $t_i$ at demand node $i$. The problem can be solved via linear programming, a minimum-cost network flow algorithm, or a specialized algorithm. Because of total unimodularity, you can relax the binary $\{0,1\}$ restriction to $\ge 0$ and still obtain an optimal binary solution.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thank you, that's what i was looking for! So i tried to solve that with a minimum cost flow algorithm, but the problem is that as far as my understanding goes, the demand (the outgoing capacity of the demand node) doesn't have to be fully satisfied in that algorithm. Do you maybe know an algorithm where in the solution the demand is either fully satisfied or 0? $\endgroup$
    – kris
    Commented Oct 5, 2022 at 17:50
  • $\begingroup$ Not sure what you mean. If the demand satisfaction is not enforced, the optimal solution is $p\equiv 0$. $\endgroup$
    – RobPratt
    Commented Oct 5, 2022 at 18:58
  • $\begingroup$ I mean that in my problem case the demand $t_i$ should always be either fully satisfied or all edges to the node should be 0 (e.g. a machine can only run if the exact amount of resources that are needed, are supplied) And since i want to maximize the function, i also calculate $max = max(e_j * c_i)$and use $max - (e_j * c_i)$ as costs for the edges from one node $j$ with supply 1 to the demanding node $i$, so i can still use minimum-cost flow algorithm. Or is there a better algorithm for my case? $\endgroup$
    – kris
    Commented Oct 5, 2022 at 20:52
  • $\begingroup$ OK, I missed the "maximize" part. I think you will need to introduce a new binary variable $y_i$, change the $=t_i$ constraint to $=t_i y_i$, and use a MILP solver. The all-or-nothing requirement destroys the total unimodularity. $\endgroup$
    – RobPratt
    Commented Oct 5, 2022 at 20:59
  • $\begingroup$ Thank you, i changed the constraint and the first test looks promising! $\endgroup$
    – kris
    Commented Oct 7, 2022 at 21:36

You must log in to answer this question.

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