# Combinatorial Optimization Problem with Constraints

To explain my problem I'd like to go with an example first. Suppose I have many bills of grocery purchases in the same shop. On the invoices I can only see the total amount of the invoice and which products I have bought and in what quantity. I would like to find out how much a single product actually costs by looking at the available amount of invoices. Assuming that the prices of the products do not change and I always have invoices with at least 3 products on them.

I have the following problem:

$$f(n_1 P_1, n_2 P_2, n_3 P_3, n_4 P_4) = \Big\{\sum^4_{i=1}\big(n_i f_1(P_i)\big), \sum^4_{i=1}\big(n_i f_1(P_i)\big), \sum^4_{i=1}\big(n_i f_1(P_i)\big), \sum^4_{i=1}\big(n_i f_1(P_i)\big)\Big\}$$

$$P_i$$ is a product with 4 features
$$n_i$$ is the quantity (amount) of $$P_i$$
$$f_i(P_i)$$ is $$\mathrm{feature}_i$$ of Product $$P_i$$

I know the sum of every feature for many combinations of different products in different amounts. I want to know the values of the features for every product.

Wanted: $$f_i(P_i)$$

The data I have looks like (I added only 2 features and products instead of 4):
(The values here are made up, I just want to give an example)

$$n_1 f_1(p_1) + n_2f_1(p_2)$$ $$n_1 f_2(p_1) + n_2f_2(p_2)$$ $$p_1$$ $$n_1$$ $$p_2$$ $$n_2$$
10 20 A 0.7 B 0.3
20 10 B 0.2 A 0.8
30 40 A 0.5 E 0.5
40 30 C 0.4 D 0.6
10 20 D 0.9 C 0.1

I want to know each feature value of each product given such data. Additionally, I have some constraints for the process and some constraints for the values of the features. If there are multiple solutions for this problem I'd like to have them all.

Process:

$$\sum(n_i) = 1\\ 0 \leq n_i < 1$$

Product:

$$\mathrm{LowerBound}_{j, i} < f_i(P_j) < \mathrm{UpperBound}_{j, i}$$

Is anybody familiar with this kind of problem and could point me in the right direction?
Is there a recommended python framework to solve these problems?

• Your question is very hard to read. Maybe you can refomulate it in a mathematical way by putting the constraints into equations. Next, consider if you really need all definitions you provided (why did you introduce $X_1$ and $X_2$? Why did you introduce $s_1$?). And finally, elaborate your example: what does the table represent, what does each row represent? (Also, the statement $0>Amount>1$ does not make any sense)
– Yann
Jan 26, 2021 at 14:53
• I don't know how to put the list of lists into an mathematical notation. But thank you for your feedback, I will try to change the formulation. Jan 26, 2021 at 14:54
• let me try to help. what I understand is you have a set of products $P=\lbrace p_i \rbrace$ and their respective amounts $a_i$. Each product has different features $f_j(p_i)$. Now, how does this feature influence the problem? what are the optimization variables? what is the actual question? If you have an optimization problem, it should be possible to bring it to the form of such
– Yann
Jan 26, 2021 at 15:15
• I've tried to change my question, hopefully it's more understandable now. Thanks alot for your help and feedback! Jan 26, 2021 at 17:12
• if I understand you correctly, you have multiple equations of the form $$\sum_{i=1}^{M} n_i \, f_{ij}=b_{j}$$, where $i$ iterates through the products, and $j$ iterates through the features, and you are looking for the $f_{ij}$'s?
– Yann
Jan 26, 2021 at 19:55

You can write your entire system in matrix notation. For each feature, you have a system of linear equations $$Ax=b$$, with $$A$$ a matrix containing the amounts of products $$a_{ij}=n_{ij}$$, $$x$$ the vector of unknown features $$f_j$$, and $$b$$ the vector of respective sums $$b_i$$.
• Note that $j$ iterates through your products, and $i$ iterates through your data-points, here