2
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • $\begingroup$ 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$? $\endgroup$
    – JakobS
    Jul 10, 2019 at 15:29
  • $\begingroup$ @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. $\endgroup$
    – Georgios
    Jul 10, 2019 at 15:42
  • $\begingroup$ 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). $\endgroup$
    – JakobS
    Jul 10, 2019 at 15:48
  • $\begingroup$ @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? $\endgroup$
    – Georgios
    Jul 10, 2019 at 15:56
  • $\begingroup$ 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}\}$. $\endgroup$
    – JakobS
    Jul 11, 2019 at 6:32

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Are you suggesting to reduce the problem to two indices? One for $e$ and one for the combination of the attributes? $\endgroup$
    – Georgios
    Jul 10, 2019 at 15:47
  • $\begingroup$ 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. $\endgroup$
    – EhsanK ♦
    Jul 10, 2019 at 15:59
  • $\begingroup$ Why is this though not the same thing as the constraint I modeled above? I never defined a parameter for a combination that does not exist and I am only choosing elements from the intersection, so would a solver even produce a decision variable and a parameter for this combination? The answer of yours is similar to 2) of my post here or.stackexchange.com/questions/904/… $\endgroup$
    – Georgios
    Jul 10, 2019 at 16:15
  • $\begingroup$ 1) you asked about how not to use those 3 indices. By pre-populating the desired indices you get just one set rather than 3 sets. 2) Maybe this is already what you do, but if you create them, as I said above, by iterating through all the sets one at a time (e.g. nested loops), then definitely pre-populating the intersection will give you a speed boost. 3) For cases when you don't have a combination param from the user, then you don't have the pre-populated intersection set of that combination and you don't need to worry about iterating over it or generating the vars or constrs for that matter. $\endgroup$
    – EhsanK ♦
    Jul 10, 2019 at 16:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.