Combination Problem with mulitiple variables

Question

I am new to this, but getting into math more and have a question regarding combinations and permutations with several variables involved.

I work for a sales company and this question is based on buying wholesale inventory.

Let's say you have a selection of 25 products...

Of those 25 products you have to select 9 (no repetitions)...

All products are divided into 5 sections...

The 5 sections are Refrigerators, Stereos, Monitors, Computers, and TV's...

For each combination of 9, 2 products must be refrigerators, 2 products must be stereos, 2 products must be monitors, 2 products must be computers, and 1 product must be a TV...

Each product has two variables, wholesale cost and review rating...

I want to calculate the highest possible review rating total for all 9 products together with a wholesale cost budget no higher than $60,000.

Here is a sample chart of cost and value:

Refrigerator 1 Cost: $8900 Rating: 40.3

Refrigerator 2 Cost: $8300 Rating: 35

Refrigerator 3 Cost: $7000 Rating: 33.5

Refrigerator 4 Cost: $7000 Rating: 33.2

Refrigerator 5 Cost: $5900 Rating: 27.2

Stereo 1 Cost: $8000 Rating: 41.3

Stereo 2 Cost: $8200 Rating: 35

Stereo 3 Cost: $7600 Rating: 31

Stereo 4 Cost: $6500 Rating: 27.6

Stereo 5 Cost: $6500 Rating: 24.7

Monitor 1 Cost: $11,400 Rating: 45.5

Monitor 2 Cost: $8700 Rating: 41.6

Monitor 3 Cost: $5300 Rating: 29.1

Monitor 4 Cost: $5700 Rating: 26.4

Monitor 5 Cost: $4900 Rating: 24.7

Computer 1 Cost: $10,800 Rating: 49.8

Computer 2 Cost: $6800 Rating: 31

Computer 3 Cost: $6600 Rating: 23.5

Computer 4 Cost: $5300 Rating: 23.2

Computer 5 Cost: $5300 Rating: 23

TV 1 Cost: $7300 Rating: 35.8

TV 2 Cost: $6700 Rating: 30.2

TV 3 Cost: $6000 Rating: 28

TV 4 Cost: $5400 Rating: 21.9

TV 5 Cost: $4300 Rating: 20.3

I'm not exactly sure how to calculate combinations when using variables such as categories allowed and staying under budget. Any help is very much appreciated. Thank you.

Answer 1

I have tackled your problem with MiniZinc:
(see below an alternative solution with lp_solve)

% SolverBackEnd = gc   (Gecode)

%  unique product section IDs
int: refrigerator = 1;
int: stereo = 2;
int: monitor = 3;
int: computer = 4;
int: TV = 5;

%  products
int: noOfProducts = 25;
set of int: Products = 1..noOfProducts;

var 1..noOfProducts: r1;
var 1..noOfProducts: r2;
var 1..noOfProducts: s1;
var 1..noOfProducts: s2;
var 1..noOfProducts: m1;
var 1..noOfProducts: m2;
var 1..noOfProducts: c1;
var 1..noOfProducts: c2;
var 1..noOfProducts: t1;

array[Products] of int: pSection =
   [refrigerator, refrigerator, refrigerator, refrigerator, refrigerator, 
    stereo, stereo, stereo, stereo, stereo, 
    monitor, monitor, monitor, monitor, monitor, 
    computer, computer, computer, computer, computer, 
    TV, TV, TV, TV, TV];

array[Products] of int: pCost =
  [ 8900, 8300, 7000, 7000, 5900,
    8000, 8200, 7600, 6500, 6500,
   11400, 8700, 5400, 5700, 4900,
   10800, 6800, 6600, 5300, 5300,
    7300, 6700, 6000, 5400, 4300];

array[Products] of int: pRating =
  [403, 350, 335, 332, 272,
   413, 350, 310, 276, 247,
   455, 416, 291, 264, 247,
   498, 310, 235, 232, 230,
   358, 302, 280, 219, 203];

%  two refrigerators         
constraint       
    (r1 < r2) /\ (pSection[r1] == refrigerator) /\ (pSection[r2] == refrigerator);

%  two stereos
constraint       
    (s1 < s2) /\ (pSection[s1] == stereo) /\ (pSection[s2] == stereo);

%  two monitors
constraint       
    (m1 < m2) /\ (pSection[m1] == monitor) /\ (pSection[m2] == monitor);

%  two computers
constraint       
    (c1 < c2) /\ (pSection[c1] == computer) /\ (pSection[c2] == computer);

%  one TV
constraint       
    (pSection[t1] == TV);

%  budget is limited
constraint
    60000 >= (pCost[r1] + pCost[r2] + pCost[s1] + pCost[s2] 
            + pCost[m1] + pCost[m2] + pCost[c1] + pCost[c2] + pCost[t1]);

%  strive to maximize rating
solve maximize (pRating[r1] + pRating[r2] + pRating[s1] + pRating[s2]
              + pRating[m1] + pRating[m2] + pRating[c1] + pRating[c2] + pRating[t1]);

%  output the solution
output
["\n Refrigerator: " ++ show(pCost[r1]) ++ "  " ++ show(pRating[r1])] ++
["\n Refrigerator: " ++ show(pCost[r2]) ++ "  " ++ show(pRating[r2])] ++
["\n Stereo:       " ++ show(pCost[s1]) ++ "  " ++ show(pRating[s1])] ++
["\n Stereo:       " ++ show(pCost[s2]) ++ "  " ++ show(pRating[s2])] ++
["\n Monitor:      " ++ show(pCost[m1]) ++ "  " ++ show(pRating[m1])] ++
["\n Monitor:      " ++ show(pCost[m2]) ++ "  " ++ show(pRating[m2])] ++
["\n Computer:     " ++ show(pCost[c1]) ++ "  " ++ show(pRating[c1])] ++
["\n Computer:     " ++ show(pCost[c2]) ++ "  " ++ show(pRating[c2])] ++
["\n TV:           " ++ show(pCost[t1]) ++ "  " ++ show(pRating[t1])] ++
["\n----------------------------------"] ++
["\n              " ++ show(pCost[r1] + pCost[r2] + pCost[s1] + pCost[s2] 
             + pCost[m1] + pCost[m2] + pCost[c1] + pCost[c2] + pCost[t1]) 
 ++ " " ++ show(pRating[r1] + pRating[r2] + pRating[s1] + pRating[s2]
             + pRating[m1] + pRating[m2] + pRating[c1] + pRating[c2] + pRating[t1])];

The result:

 Refrigerator: 7000  335
 Refrigerator: 7000  332
 Stereo:       8000  413
 Stereo:       8200  350
 Monitor:      5400  291
 Monitor:      4900  247
 Computer:     6800  310
 Computer:     5300  232
 TV:           7300  358
----------------------------------
              59900 2868

I have translated the float type ratings to integer type ratings to circumvent a problem with float arrays in MiniZinc. Hopefully, there exist more elegant ways to model such problems in MiniZinc.

---

Alternative solution with lp_solve

Writing the problem as linear programming model:

/*  Maximize the sum of ratings  */
max: 40.3 r1 +35.0 r2 +33.5 r3 +33.2 r4 +27.2 r5
    +41.3 s1 +35.0 s2 +31.0 s3 +27.6 s4 +24.7 s5
    +45.5 m1 +41.6 m2 +29.1 m3 +26.4 m4 +24.7 m5
    +49.8 c1 +31.0 c2 +23.5 c3 +23.2 c4 +23.0 c5
    +35.8 t1 +30.2 t2 +28.0 t3 +21.9 t4 +20.3 t5;

/*  Constraints for number of selected units per product section  */
r1 + r2 + r3 + r4 + r5 = 2;
s1 + s2 + s3 + s4 + s5 = 2;
m1 + m2 + m3 + m4 + m5 = 2;
c1 + c2 + c3 + c4 + c5 = 2;
t1 + t2 + t3 + t4 + t5 = 1;

/*  Each product may either be selected once or not selected at all  */
0 <= r1 <= 1;
0 <= r2 <= 1;
0 <= r3 <= 1;
0 <= r4 <= 1;
0 <= r5 <= 1;
0 <= s1 <= 1;
0 <= s2 <= 1;
0 <= s3 <= 1;
0 <= s4 <= 1;
0 <= s5 <= 1;
0 <= m1 <= 1;
0 <= m2 <= 1;
0 <= m3 <= 1;
0 <= m4 <= 1;
0 <= m5 <= 1;
0 <= c1 <= 1;
0 <= c2 <= 1;
0 <= c3 <= 1;
0 <= c4 <= 1;
0 <= c5 <= 1;
0 <= t1 <= 1;
0 <= t2 <= 1;
0 <= t3 <= 1;
0 <= t4 <= 1;
0 <= t5 <= 1;

/*  Budget constraint  */
8900 r1 +8300 r2 +7000 r3 +7000 r4 +5900 r5
+8000 s1 +8200 s2 +7600 s3 +6500 s4 +6500 s5
+11400 m1 +8700 m2 +5400 m3 +5700 m4 +4900 m5
+10800 c1 +6800 c2 +6600 c3 +5300 c4 +5300 c5
+7300 t1 +6700 t2 +6000 t3 +5400 t4 +4300 t5 <= 60000;

/*  All volume variables are integers  */
int r1, r2, r3, r4, r5;
int s1, s2, s3, s4, s5;
int m1, m2, m3, m4, m5;
int c1, c2, c3, c4, c5;
int t1, t2, t3, t4, t5;

Result:

Actual values of the variables:

r1 0
r2 0
r3 1
r4 1
r5 0
s1 1
s2 1
s3 0
s4 0
s5 0
m1 0
m2 0
m3 1
m4 0
m5 1
c1 0
c2 1
c3 0
c4 1
c5 0
t1 1
t2 0
t3 0
t4 0
t5 0

The sum of ratings is $286.8$, the sum of costs is \$ $59900$.