Linear Programming Binary Variable Grouping

Question

I am new to Linear Programming, tried few sample cases.

Seeking help on solution/approach for below problem.

I am not sure if it's linear programming or I should look in other options.

Here I am trying to identify the designers with best cost to finish the complete dress.

The Conditions: Need to get complete dress I can select either Paul1 or Paul2 not both even though the combination of these two could be best cost.

Dress	Designer	Cost
Shirt	John	6.33
Trouser	John	6.76
Jacket	John	6.84
Shirt	Chris	6.62
Trouser	Chris	6.62
Jacket	Chris	6.62
Shirt	Paul 1	6.37
Trouser	Paul 1	6.37
Jacket	Paul 1	6.34
Shirt	Paul 2	6.52
Trouser	Paul 2	6.76
Jacket	Paul 2	6.20

Any help would be greatly appreciated.

Here is the model I tied to implement in excel solver.

Here is the result for best cost. I couldn't find a way to define condition to take either Paul1 or Paul2.

Realized that for Maths problems it's completely separate portal. Posted in https://math.stackexchange.com/

https://math.stackexchange.com/questions/4668967/linear-programming-binary-variable-grouping

Answer 1

Sure, this can be formulated as an LP. Here's an idea to start things off:

You have 2 distinct sets here that you will need to use in your formulation:

items = {shirt, trouser, jacket}

designers = { ... }

Then we need to imagine a useful decision variable.... Well, how about a binary variable that indicates a particular designer makes a particular item...

make[d, i] ∈ {0, 1}    1:  if designer d makes item i

The remainder of the expressions should flow from that.

Edit: paul vs paul

You'll need to introduce 2 new binary variables (squares in excel) that indicate whether each "paul" has been used and then link them to the usage of each paul and then tie the sum of them to less than or equal 1 to enforce the either-or.

sum(paul1 items) <= use_paul1 * 3
sum(paul2 items) <= use_paul2 * 3

then

use_paul1 + use_paul2 <= 1