Approximation for a system of linear functions

Question

There is a list of food and it's composition. For example,
salmon: protein - 64 g, fats - 14 g, carbohydrate - 0 g per 100 g of food;
nuts: protein - 20 g, fats - 53 g, carbohydrate - 21 g per 100 g of food;
cereal: protein - 4 g, fats - 1 g, carbohydrate - 91 g per 100 g of food.
there is a diet that I must adhere to.
Protein - between 140 and 171 g per day,
fats - between 54 and 66 g per day,
carbohydrate - between 207 and 253 g per day.
Today I ate 150 g of nuts and 240 g of cereal and exceeded the fats and carbohydrate limits. But i still lack protein.
Therefore, I must eat foods that minimize my intake of fats and carbohydrates and satisfy my protein needs. However, I am willing to sacrifice protein intake, as the harm from exceeding the limits for fat and carbohydrate intake can be excessive. We will assume that the harm from excess or shortage of any nutrient is the same. Thus, it is necessary to find a solution that will be equally close to the required constraints. I suppose this task can be expressed as a system of target linear functions $$ \left\{ \begin{array}{c} a_{11}x_1 + ... + a_{1n}x_n - b_{1min} \to min, \\ a_{11}x_1 + ... + a_{1n}x_n - b_{1max} \to max, \\ ... \\ a_{m1}x_1 + ... + a_{mn}x_n - b_{mmin} \to min\\ a_{m1}x_1 + ... + a_{mn}x_n - b_{mmax} \to max\\ \end{array} \right. $$ It is necessary to find such values of products $x_{i}\geqslant0, i = 1,...,n$, where n is count of products, $a_{ji}$ - count of nutrient j in product i, $j = 1,...,m$, where m is count of nutrients, b is daily nutrient intake limit, that would most satisfy the given conditions. The criteria cannot be sorted in descending order of importance. So the method of successive concessions is not suitable. Is there such a method?

Answer 1

You have an infeasible set of LP constraints $b_L \leq Ax\leq b_U$ and want to find a solution with a minimal number of violations.

The exact approach would require the introduction binary variables and require a big-M model leading to a MILP. Let $\delta_L$ and $\delta_U$ be binary vectors indicating if the lower and upper constraints are violated, the the big-M model is $b_L-M\delta_L \leq Ax \leq b_U + M\delta_U$. Minimizing the sum of $\delta_L+\delta_U$ gives the minimum number of violations. On top of this you can add more constraints and terms in the objective to put emphasis on certain aspects and to various solutions.

Here is a test in the MATLAB Toolbox YALMIP (disclaimer, developed by me)

n = 5;
m = 10;
A = rand(m,n);
bL = 5*rand(m,1);
bU = bL + 5*rand(m,1);

% Will be infeasible in most cases
x = sdpvar(n,1);
Model = [x >= 0, bL <= A*x <= bU];
optimize(Model)

% Minmize #violations
M = 100; % Should be derived thouroughly
dU = binvar(m,1);
dL = binvar(m,1);
Model = [x >= 0, bL-M*dL <= A*x <= bU+M*dU];
optimize(Model,sum(dU)+sum(dL))
value([dL dU])

A commonly used heuristic is to simply add a continuous slack instead. It will often be sparse

dU = sdpvar(m,1);
dL = sdpvar(m,1);
Model = [x >= 0, dU >=0, dL >=0, bL-dL <= A*x <= bU+dU];
optimize(Model,sum(dU)+sum(dL))
value([dL dU])