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

Question

The comments in Optimisation of food items problem - how do I find the cheapest combination? and Optimisation / linear programming: can I specify combinatorial constraints? have been very helpful.

To recap: I have P number of food items to choose from, and 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.

I am now using Gurobi and AMPL to do this, so any answer that can be specified in AMPL or in the interfaces of Gurobi will be greatly appreciated. However, if this is not possible, this is also ok.

Answer 1

You will need binary variables and big-M constraints, as in my answer to the second linked question. To match that question more closely, let bounded decision variable $x_{i,d}\in [0,M_{i,d}]$ be the amount of food $i$ on day $d$, and let binary decision variable $y_{i,d}$ indicate whether $x_{i,d}>0$. For each food $i$ and pair $(d_j,d_k)$ of days with $d_j < d_k$, let binary decision variable $z_{i,d_j,d_k}$ indicate whether those days differ with respect to food $i$ (that is, food $i$ appears one exactly one of the two days). Let $\epsilon>0$ be a small constant. The linear constraints are: $$ \epsilon\ y_{i,d} \le x_{i,d} \le M_{i,d} y_{i,d} \\ z_{i,d_j,d_k} \le y_{i,d_j} + y_{i,d_k} \le 2-z_{i,d_j,d_k} \\ \sum_i z_{i,d_j,d_k} \ge 1 $$ The first constraint enforces $x_{i,j,d}>0 \iff y_{i,d}=1$. The second constraint enforces $z_{i,d_j,d_k}=1\implies y_{i,d_j} + y_{i,d_k}=1$. The third constraint enforces $z_{i,d_j,d_k}=1$ for at least one $i$.