# What kind of problem is this : LP , Multi-objective , other?

I started studying Operations Research (OR) recently and I faced a problem in which I struggled to model it using the traditional LP models. After some attempts, I'm not sure if such a problem is a linear one nor if it can be solved using LP methods.

Problem Description I need to find the minimum purchase amount (T) to buy a batch of products, observing a restriction that each product must be purchased at least x% of the total purchase amount.

Table describing products and restrictions

Data Corn(x1) Soy(x2) Wheat(x3) Rice (x4)
Minimum Bag Weight (kg) 100 100 100 100
Unitary Bag Price ($) 4,000 3,200 4,500 1,600 Perc(% of T) of each Product 32% 27% 15% 26% Critical Condition/Requirement The amount of bags of each product (x1,x2,x3,x4) must be integer, i.e., no fractional bag is allowed. This seemed to me a very unusual condition, once the total is the target value to be minimized and at the same time is still the basis value of a condition (the amount in which percentage of each product will be based on). The objective is to determine the minimum purchase amount to buy all of the products observing the percentage of the total purchase value for each one. What kind/category of OR problem is this and which technique/method should be used to solve it? Additional Details (an attempt to clarify the problem) 1-Minimum Bag weight 100kg ==> it means that amounts to be purchased must be integer (bags of 100kg) and not fractions (portions of the bag or kg). 2-Unitary bag Price ==> is the price of one bag and it contains 100kg 3-Perc(% of T) of each Product ==> it is the percentage of the total amount in value US$, that must be addressed to each product.

For example, suppose I have US$10,00 to buy those products. Then this value must be distribute according the table : Restriction Corn Soy Wheat Rice Total Min Perc% 32% 27% 15% 26% 100% Value US$ 3,200 2,700 1,500 2,600 10,000
Possible to buy? No No No Yes

however, the total amount of US$10,000 can only buy one product (Rice) because the others have bag price higher than the amount addressed to each product. Now, let's suppose we have the amount to buy at least one bag of each product, this amount would be US$ 13,300. However observe that with such amount the restriction Percent% of T (T=13,300) for each product is not attended !

Restriction Corn Soy Wheat Rice Total
Unitary Bag Price (\$) 4,000 3,200 4,500 1,600 --
Value paid 4,000 3,200 4,500 1,600 13,300
Perc% of Total 30% 24% 34% 12% 100%
Min Perc% required 32% 27% 15% 26% 100%
Attended Min Perc% No No No No --

This Min Perc% of Total , must be exactly the required number, not less, not more.

• Your problem is almost certainly and integer program rather than a linear program. That said, the description is rather confusing. Can you edit the question to make it a bit clearer? What is "minimum bag weight"? Is "Unitary Price Bag" mean to be price per bag? Is the last row of the table the minimum percentage of the total purchase that the product in the column must comprise? (If so, % by weight or % by bag count?)
– prubin
Apr 6 at 15:31
• Also, your last row sums to 100. If those are the "minimum" percentages for each product, that means each product must be exactly that percentage of the total purchase.
– prubin
Apr 6 at 15:33
• @JRG What prevents you from choosing X = (1, 1, 1, 1) with the total price of 13300? Do you have any budget limitations? Apr 6 at 15:34
• Since all bags weigh the same, can't you take resp 32, 27, 15 and 26 bags of these products? That will get you the exact ratios. To find a cheaper solution with fewer bags, divide these numbers by their greatest common divider. Apr 6 at 17:52
• Just to re-state something prubin already said in a different form - if you have to achieve the target percentages exactly then there may not be ANY feasible solutions unless the original source materials (their mixture proportions and bag sizes) happen to match your problem rather precisely. In general, this kind of mixing/blending problem has to accept some reasonable tolerances around the target proportions in order to stand a chance of finding a solution unless you are very lucky with your data. Apr 7 at 11:04

## 2 Answers

You can solve this as a mixed integer linear program. Let $$i$$ index the products (corn, soy, etc.) with $$c_i$$ the cost per bag of each product (4,000 for corn etc.) and $$p_i$$ the target percentage of the total purchase cost $$T$$ attributable to product $$i$$. We require that $$\sum_i p_i = 1.$$

Besides the nonnegative variable $$T$$ for total cost, you will have integer variables $$x_i$$ for the number of bags of product $$i$$ purchased. The mixed integer model is as follows: \begin{align*} \min\quad & T\\ \textrm{s.t. }\sum_{i}c_{i}x_{i} & =T\\ c_{i}x_{i} & =p_{i}T\quad\forall i\\ x_{i} & \ge1\quad\forall i. \end{align*} Note the lower bound of 1 for all purchase quantities $$x_i,$$ which is necessary to prevent the solver from choosing the trivial solution. (Buying nothing has minimal cost.)

• I'm glad to see this explanation, thank you. I'm digesting it and going deeper in MIP study to better understand how it works and how to model such kind of restrictions . I'll come back to you later. Thank you.
– JRG
Apr 14 at 15:58

You actually do not need to solve an optimization model to solve this, although the "direct" approach is also tedious.

Consider the constraint (excluding the lower bound on $$x_i$$) in my other answer. The form an underdetermined $$5\times 5$$ system of linear equations $$Ax = b$$ where $$A=\left[\begin{array}{ccccc} 4000 & 3200 & 4500 & 1600 & -1.00\\ 4000 & 0 & 0 & 0 & -.32\\ 0 & 3200 & 0 & 0 & -.27\\ 0 & 0 & 4500 & 0 & -.15\\ 0 & 0 & 0 & 1600 & -.26 \end{array}\right],$$ $$b = (0, 0, 0, 0, 0)$$ and the fifth component of $$x$$ is the total purchase cost. $$A$$ has rank 4. We add one more equation, saying that the total purchase cost is 1, which changes $$A$$ to $$Ax = b$$ where $$A=\left[\begin{array}{ccccc} 4000 & 3200 & 4500 & 1600 & -1.00\\ 4000 & 0 & 0 & 0 & -.32\\ 0 & 3200 & 0 & 0 & -.27\\ 0 & 0 & 4500 & 0 & -.15\\ 0 & 0 & 0 & 1600 & -.26\\ 0 & 0 & 0 & 0 & 1 \end{array}\right]$$ and $$b$$ to $$(0,0,0,0,0,1).$$

Although the system is undetermined, you can solve it (for example, using QR decomposition of $$A$$), obtaining the following value for $$x$$: $$x = (8.000000e-05, 8.437500e-05, 3.333333e-05, 1.625000e-04, 1.000000e+00).$$

Now you just need to find the smallest integer $$\lambda$$ for which $$\lambda \cdot x$$ is integer-valued. We need to multiply by $$10^5$$ to clear the exponents, by 3 to get rid of the fractional part of the wheat purchase, and by 16 to get rid of the other fractions. So $$\lambda = 48e^5$$ and $$\lambda \cdot x = (384, 405, 160, 780, 4800000),$$which agrees with the MIP solution.