Optimisation / linear programming: how do I specify a constraint that a combination of some variables should be different from another

Answered

Justin Chua

March 03, 2020 13:57

• 
• 

I have a table of data of food items, about 200-300 of such food items. Each food item has a cost price, weight/volume, nutritional info (like total weight of protein, total weight of carbs etc.) per unit (eg. bottle, can, packet).

My objective is to minimise cost ie find the quantities of each of these food items (say in grams) that I should be buying (and consuming) such that my cost is minimised, subject to the constraint that these food items fulfil my nutritional needs. I have found this is by and large a linear programming problem.

However, my problem has now evolved into one in which I have to take into account that I need combinations of food items that are different day to day so I don't get bored. I do not mind my menu recurring as long as it is not recurring every day, so I can set it say to 7 different combinations of food, 1 for 1 day of the week. Hence I now have P X Q variables where P is the number of food items to choose from and Q is the number of days.

How then do I formulate a constraint such that the combinations of food for each day are different any other day? Note that the combinations, not just the quantity, should be different eg.

where y_i refers to Food Item i out of P Food Items

This should not be allowed: 5y₁+4y₁₈ for Day 1, 2y₁+13y₁₈ for Day 2. Even though they are different quantities, the exact same few products are chosen for both days.

However, mixing and matching with some of the products remaining the same are ok, so: 5y₁+4y₁₈ for Day 1, 2y₁+13y₂ for Day 2. Even though Product 1 is chosen for both days.

ALSO, how do I make sure the above model remains feasible?

0

• Official comment

  

  Simranjit Kaur

  • Gurobi Staff

  December 06, 2024 00:49

  This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
• 

  Eli Towle

  • Gurobi Staff

  March 06, 2020 18:56 Edited

  Hi Justin,

  The first step is to introduce binary variables that are equal to 1 if and only if you eat a food product on a particular day. We should assume that if you eat a food, you must eat at least \( m \) of it. If this does not hold, then the optimal solution would be to eat the same foods every day, while additionally eating some negligible \( \epsilon > 0 \) amount of a different food product each day to satisfy the condition that the exact same set of food products are not consumed.

  So, if \( P \) is the set of food products and \( Q \) the set of days, we introduce variables \( z \in \{0, 1\}^{P \times Q} \) and add the constraints:

  $$\begin{align*}m z_{ij} \leq y_{ij} \leq M_i z_{ij} \qquad \forall i \in P,\ j \in Q, \end{align*}$$

  where \( M_i \) is an upper bound on the amount of food \( i \in P \) you can consume. You can derive reasonable values for the \( M_i \) by considering your daily nutritional requirements and the nutrients provided by food \( i \).

  Then, we add constraints to ensure that the same foods are not eaten each day. I.e.:

  $$\begin{align*} \sum_{i \in P} | z_{ij} - z_{ik} | \geq 1 \qquad \forall j, k \in Q,\ j \neq k. \end{align*}$$

  You can model the absolute value using binary variables, or (e.g.) the abs_() helper function in the Python API.

  However, I think there is a better way to solve this problem. Let's consider the problem of optimizing food consumption for a single day. After adding variables \( z \in \{0, 1\}^P \) and the "variable bound" constraints, we solve the problem. Let \( (y^*, z^*) \) be the optimal solution. We add the following inequality to the problem:

  $$\begin{align*} \sum_{\substack{i \in P \colon \\ z^*_i = 1}} (1 - z_i) + \sum_{\substack{i \in P \colon \\ z^*_i = 0}} z_i \geq 1, \end{align*}.$$

  This inequality says that a different set of \( z \) variables must be used in the optimal solution. This is because the only vector in \( \{0,1\}^P \) cut off by the above inequality is precisely the vector \( z^* \). Thus, when we solve the model a second time, the new solution will correspond to a different set of foods. If we repeat this process for each day of the week, we will end up with seven solutions corresponding to the seven best food combinations.

  I hope this helps. Thanks!

  Eli

   

  0

Post is closed for comments.