# Knapsack problem - reducing the number of decision variables

I am trying to solve something similar to a knapsack problem:

$$\max \sum v_{n}P_{n}$$

subject to some basic weight constraints. However, what makes this problem difficult to solve is that $$P_{n}$$ is a function of $$x_{i,n}$$, my decision variable.

$$P_{n} = \sum c_{i}x_{i,n}/d_{n}$$

In my problem, I have a portfolio of products that each have a price, $$c_{i}$$ and I can choose an amount of this product $$x_{i,n}$$ that I allocate to a customer, $$n$$. Note that there is an upper limit on how much I can allocate for each product. The constraints make this an interesting problem to solve (e.g., I need to allocate enough to satisfy the demand of each $$n$$).

$$v_{n}$$, $$c_{i}$$ and $$d_{n}$$ are all parameters. $$x_{i,n}$$ is a continuous decision variable.

However, I was wondering if there is a way for me to not use the $$x_{i,n}$$'s as my decision variable but instead use $$P_{n}$$ but with some constraints.

The reason I would like to do this is that I have a very large number of $$x_{i}$$'s. I was thinking something like an upper bound on $$P_{n}$$ could be the most expensive product in my portfolio and the lower bound could be the cheapest product in the portfolio. And I could add a constraint that says that the average of $$P_{n}$$ has to be the average price of the (weighted) portfolio. But the problem with this approach is that if a customer has a very high demand, I need to use multiple products and the price will be the weighted average price of all allocated products. So the upper bound is not necessarily the most expensive product, it depends on the demand of the customers.

I have not been able to find any literature on this kind of problem.

EDIT: To add some additional context to my problem, here are the relevant constraints:

Each product,$$i$$, has a fixed amount, $$k_{i}$$:

$$\sum_{n}x_{i,n} \leq k_{i}$$

Each customer, $$n$$, has a demand that needs to be satisfied with the chosen products:

$$\sum_{i}x_{i,n} = d_{n}$$

To re-state my problem: Since I have a large number of products, I was wondering if there is a way to change my problem in a way that I do not need to consider $$x_{i,n}$$ as my decision variables but instead just use $$P_{n}$$, but of course with some additional constraints.

• What are $v$, $P$, $x$, $c$, $d$? inputs, decisions? what do they represent? Commented May 9 at 15:33
• $v$, $c$ and $d$ are parameters. $x$ is the decision variable and $P$ is simply a linear function of $x$. Commented May 9 at 15:40
• Are your $x$ variables continuous, integer or binary? What does a typical "basic weight constraint" look like?
– prubin
Commented May 9 at 16:01
• $x$ is continuous. And the weight constraints are e.g., the sum of products allocated to a customer must satisfy the customer's demand. So $\sum x_{i,n} = d_n$ where the sum is over the $i$'s. Commented May 9 at 16:08
• So far the original problem seems to be separable -- the variables $x_{i,n}$ and $x_{j,m}$ with $m \neq n$ do not appear in the same constraint. Unless there is something tying the customer allocations together, you can solve a separate LP for each customer.
– prubin
Commented May 9 at 18:56