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

Question

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.

Answer 1

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.)

Answer 2

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.