# Structure of an Optimal Solution to a Fractional Packing Problem

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?