# Reduction of Unnecessary Parameters and Variables in an MIP

Let's observe an example constraint:

$$\sum \limits^E_{e\ \in \ A_a \ \cap \ B_b \ \cap \ C_c} x_{e,a,b,c} \geq n_{a,b,c} \; \; \; \forall a \in A,b \in B,c \in C$$

with $$e \in E$$ an element and $$A_a$$ a set containing elements e with the attribute a, $$B_b$$ a set containing elements e with the attribute b and $$C_c$$ a set containing elements e with the attribute c and $$n$$ a parameter and $$x$$ a decision variable.

• Is it even possible to write this constraint only for the combinations that exist without using the following part $$\forall a \in A,b \in B,c \in C$$ ?

An example could be $$E$$ a set of airplanes, $$A$$ a set of altitude capabilities, $$B$$ a set of different wheelbase and $$C$$ a set of colors. Not all combinations exist.

• If not, what happens to a solver when for a parameter $$n_{a,b,c}$$ and decision variable $$x_{e,a,b,c}$$ there is no combination set from the user? Do these appear for the solver?

The goal is to avoid unnecessary zero parameters and variables.

• Do you need indices $a,b,c$ for your decision variable? Maybe you only need $e$ as an index. Can you give a little more context on the underlying problem. This would make it easier to get a better understanding of your question. For example: What should the constraint represent? Which decisions are encoded in variable $x$? Jul 10 '19 at 15:29
• @JakobS you could use the same method to a scheduling problem. $e$ may be an employee, $a$ a certain shift, $b$ a day and $c$ a skill of the employee. The constraint could be the demand of employees for a certain shift, day and skill. With $x$ its decided which employees get chosen. Jul 10 '19 at 15:42
• Then I would omit $c$ in the decision variable as skill is directly linked to the employee, right? You could (as was already answered by EhsanK) precompute the sets of all valid employees for all potential combinations (e.g. create a dictionary with containing the valid employees for a given combination of shift, day and skill). Jul 10 '19 at 15:48
• @JakobS An employee may have different skills. Furthermore, $c$ is just one from the rest indices. By "create a dictionary" do you mean to merge $a$ and $b$ to one index? Jul 10 '19 at 15:56
• Yes, but for each employee you know beforehand which skills they have. You can precompute for each skill the relevant employees - so a dictionary with for example $D[c]=\{e_1,e_5,e_6,\ldots,e_{123}\}$. Jul 11 '19 at 6:32

Because I see that your summation goes over all $$e$$ in the intersection of the sets, (from an implementation standpoint) I would approach this problem by first creating the intersection set which contains the desired parameters. So, think of it like several loops where you check whether element $$e$$ exists in each of the sets $$A, B$$, and $$C$$ and then you add $$e$$ that exists in all (intersection) as your decision variable. Now, rather than all those loops, first, create the desired set (let's call it $$D$$) and then only iterate over $$D$$. That works for $$n$$ too. If you save them in a dictionary or hash table (again, implementation-wise), you are avoiding all the unnecessary $$0$$ parameters and variables creation.
• Are you suggesting to reduce the problem to two indices? One for $e$ and one for the combination of the attributes? Jul 10 '19 at 15:47
• yes, so essentially you want to find the element $e$ in that intersection and the indices of $n$ are exactly the same as the intersection. So, you are summing over all the $\sum_{e} x_{ed} \ge n_{d} \quad \forall d \in D$ where $D$ was the intersection set.