2
$\begingroup$

Packing LP

We have the following optimization problem:

$$ \max_{x_{ij}} x_{ij} c_{ij}$$ s.t. $$(i)\forall j\mbox{ }\sum_{i} x_{ij} \leq \beta_j$$ $$(ii)\forall i\mbox{ }\sum_{j} x_{ij} D_{ij} \leq 1$$ $$(iii)\forall i\mbox{ }\forall j\mbox{ }0 \leq x_{ij} \leq 1.$$

Here, $D_{ij} \geq 1$ are integers, $c_{ij} \geq 0$, $\beta_j>0$, and $\sum_j \beta_j = 1$.

Are there known results to understand the structure of the optimal solution of the above LP?

Connection to Generalized Flow Problem:

This packing problem can be formed as a generalized max cost flow problem on a graph which has one source and one sink. The flow passes through a complete bipartite graph.

The nodes in left partite are connected to the source and correspond to the $i$-component in the LP. The edge between the source and the $i$-th node has: (cost = 0, capacity = 1, scale = 1).

The nodes in right partite are connected to the sink and correspond to the $j$-component in the LP. The edge between the source and the $i$-th node has (cost = 0, capacity = $\beta_j$, scale = 1).

In the bipartite graph, the edge $i\to j$ have: (cost = $c_{ij}$, capacity = $1$, scale = $1/D_{ij}$).

Can this be used to infer any structure for the optimal solution?

Crossposted: https://cstheory.stackexchange.com/questions/44494/structure-of-an-optimal-solution-to-a-fractional-packing-problem

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.