Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
With only $C(25, 9)= 2042975$ possibilities, this is probably easiest solved by writing a short program, e.g. in Python, to try all the combinations. –  augurar Feb 28 at 2:05

1 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$.

share|improve this answer
    
WOW! Axel this is amazing! Thank you so much, this encourages me to look into programs to find out how to solve these questions of which I have many from work. Very much appreciated! –  user131961 Mar 8 at 7:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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