Other multi value optimisation using brute force search?

Question

I've 6 list of company possible orders (a,b,c,d,e,f) in dollars.The price changes every week (13 weeks) as below.

a1_list = [1075000, 1075000, 1072500, 1072500, 1070000, 1070000, 1050000, 1535000, 1535000, 1015000, 1015000, 1000000, 1000000]

b1_list = [1275000, 1275000, 1278000, 1278000, 1242000, 1242000, 1266000, 1806000, 1806000, 1191000, 1191000, 1191000, 1191000]

c1_list = [1530000, 1530000, 1822500, 1822500, 1813500, 1813500, 1804500, 1773000, 1773000, 1746000, 1746000, 1710000, 1710000]

d1_list = [1005000, 1005000, 1005000, 1005000, 1005000, 1005000, 1005000, 960000, 960000, 960000, 960000,
 960000, 960000]

e1_list = [2436000, 2436000, 2905000, 2905000, 2877000, 2877000, 2849000, 2814000, 2814000, 2779000, 2779000, 2730000, 2730000]

f1_list = [1881000, 1881000, 1890000, 1890000, 1863000, 1863000, 1854000, 1822500, 1822500, 1804500, 1804500, 1786500, 1786500]

I can only choose 1 order from a company every time. That is, if I choose the the order for 1st week to be comp A, then company B, C, D, E and F must not be on week1. Every number in the list correspond to a particular week.

For example, for company A order, the price in week 1 and 2 will be 1075000. If the order is not made in week 1 or 2, but made in week 3 and 4, the price will be 1072500.

This is sort of an optimisation problem.

I wrote a manual calculation to calculate the best combination that give me the best profit.

Below are my codes:

import numpy as np
from scipy import optimize

price = np.array([
    [430,   425,    340,    402,    348,    418],
    [429,   426,    405,    402,    415,    420],
    [428,   414,    403,    402,    411,    414],
    [420,   422,    401,    402,    407,    412],
    [614,   602,    394,    384,    402,    405],
    [406,   397,    388,    384,    397,    401],
    [400,   397,    380,    384,    390,    397],
    ])

a1Q = 2500
a2Q = 4000
b1Q = 3000
b2Q = 3500
c1Q = 4500
c2Q = 5500
c3Q = 4000
d1Q = 2500
d2Q = 4000
e1Q = 7000
e2Q = 2000
f1Q = 4500
f2Q = 1000
 

a1_price = price[:,0]*a1Q
a2_price = price[:,0]*a2Q
b1_price = price[:,1]*b1Q
b2_price = price[:,1]*b2Q
c1_price = price[:,2]*c1Q
c2_price = price[:,2]*c2Q
c3_price = price[:,2]*c3Q
d1_price = price[:,3]*d1Q
d2_price = price[:,3]*d2Q
e1_price = price[:,4]*e1Q
e2_price = price[:,4]*e2Q
f1_price = price[:,5]*f1Q
f2_price = price[:,5]*f2Q


a1_list = [a1_price[0]]*2 + [a1_price[1]]*2 + [a1_price[2]]*2 + [a1_price[3]] + [a1_price[4]]*2 + [a1_price[5]]*2 + [a1_price[6]]*2
a2_list = [a2_price[0]]*2 + [a2_price[1]]*2 + [a2_price[2]]*2 + [a2_price[3]] + [a2_price[4]]*2 + [a2_price[5]]*2 + [a2_price[6]]*2
b1_list = [b1_price[0]]*2 + [b1_price[1]]*2 + [b1_price[2]]*2 + [b1_price[3]] + [b1_price[4]]*2 + [b1_price[5]]*2 + [b1_price[6]]*2
b2_list = [b2_price[0]]*2 + [b2_price[1]]*2 + [b2_price[2]]*2 + [b2_price[3]] + [b2_price[4]]*2 + [b2_price[5]]*2 + [b2_price[6]]*2
c1_list = [c1_price[0]]*2 + [c1_price[1]]*2 + [c1_price[2]]*2 + [c1_price[3]] + [c1_price[4]]*2 + [c1_price[5]]*2 + [c1_price[6]]*2
c2_list = [c2_price[0]]*2 + [c2_price[1]]*2 + [c2_price[2]]*2 + [c2_price[3]] + [c2_price[4]]*2 + [c2_price[5]]*2 + [c2_price[6]]*2
c3_list = [c3_price[0]]*2 + [c3_price[1]]*2 + [c3_price[2]]*2 + [c3_price[3]] + [c3_price[4]]*2 + [c3_price[5]]*2 + [c3_price[6]]*2
d1_list = [d1_price[0]]*2 + [d1_price[1]]*2 + [d1_price[2]]*2 + [d1_price[3]] + [d1_price[4]]*2 + [d1_price[5]]*2 + [d1_price[6]]*2
d2_list = [d2_price[0]]*2 + [d2_price[1]]*2 + [d2_price[2]]*2 + [d2_price[3]] + [d2_price[4]]*2 + [d2_price[5]]*2 + [d2_price[6]]*2
e1_list = [e1_price[0]]*2 + [e1_price[1]]*2 + [e1_price[2]]*2 + [e1_price[3]] + [e1_price[4]]*2 + [e1_price[5]]*2 + [e1_price[6]]*2
e2_list = [e2_price[0]]*2 + [e2_price[1]]*2 + [e2_price[2]]*2 + [e2_price[3]] + [e2_price[4]]*2 + [e2_price[5]]*2 + [e2_price[6]]*2
f1_list = [f1_price[0]]*2 + [f1_price[1]]*2 + [f1_price[2]]*2 + [f1_price[3]] + [f1_price[4]]*2 + [f1_price[5]]*2 + [f1_price[6]]*2
f2_list = [f2_price[0]]*2 + [f2_price[1]]*2 + [f2_price[2]]*2 + [f2_price[3]] + [f2_price[4]]*2 + [f2_price[5]]*2 + [f2_price[6]]*2

best = 0
ind_a1,ind_b1,ind_c1,ind_d1,ind_e1,ind_f1 = 0,0,0,0,0,0

for a1 in a1_list:
    # print(f'A: {ind_a}')
    # ind_a+=1
    ind_b1 = 0
    # ind_c=0
    for b1 in b1_list:
        
        if ind_b1 != ind_a1:
            
            # print(ind_b)
            # total = a + b
            ind_c1 = 0
            
            for c1 in c1_list:
                
                if ind_c1 != ind_a1 and ind_c1 != ind_b1:
                    
                    
                    ind_d1 = 0
                    
                    for d1 in d1_list:
                        
                        if ind_d1 != ind_a1 \
                            and ind_d1 != ind_b1 \
                                and ind_d1!= ind_c1:
                            
                            ind_e1 = 0                               
                            
                            for e1 in e1_list:
                                
                                if ind_e1 != ind_a1 \
                                    and ind_e1 != ind_b1 \
                                        and ind_e1!= ind_c1 \
                                            and ind_e1!= ind_d1:
                                    
                                    ind_f1 = 0
                                    
                                    for f1 in f1_list:
                                        
                                        if ind_f1 != ind_a1 \
                                            and ind_f1 != ind_b1 \
                                                and ind_f1!= ind_c1 \
                                                    and ind_f1!= ind_d1 \
                                                        and ind_f1!= ind_e1:
                                    
                                            total = a1 + b1 + c1 + d1 + e1 + f1
                        
                                            if total >best:
                                                best = total
                                                print(a1,b1,c1,d1,e1,f1, ind_a1,ind_b1,ind_c1,ind_d1,ind_e1,ind_f1)
                                                print(best)
                                                
                                        ind_f1 +=1
                                ind_e1 +=1
                        ind_d1 += 1
                ind_c1+=1            
        ind_b1+=1
    ind_a1+=1
        

I'm wondering if there's a simpler and cleaner way to solve this problem, or to use built in scipy optimization functions like scipy.optimize.minimize or scipy.optimize.brute?

This is actually a portion of a huge problem optimisation function that I'm solving.

Just to give you an idea (but may be irrelevant to this question), below are some plot. I'm trying to maximize the revenue.

Any help would be greatly appreciated.

Answer 1

This problem is best solved using munkres algorithm (or otherwise known as the Hungarian algorithm).

To get an idea how this algorithm works,

you can watch the video below.

https://www.youtube.com/watch?v=cQ5MsiGaDY8

To do it in Python, first install munkres library.

pip install munkres

You can refer here for more information.

http://software.clapper.org/munkres/

Below is my sample code to solve this problem without looping 6 billion+ times (13 variables) --> O(n!). With munkres algorithm, it's O(n^3). Apparently, there're tricks to optimized the values through some mathematical matrix reduction technique. The video above will give you some idea.

from munkres import Munkres, print_matrix
import sys

matrix = [
    a1_list,
    b1_list,
    c1_list,
    d1_list,
    e1_list,
    f1_list,
    a2_list,
    b2_list,
    c2_list,
    d2_list,
    e2_list,
    f2_list,
    c3_list,
          ]

cost_matrix = []
for row in matrix:
    cost_row = []
    for col in row:
        cost_row += [sys.maxsize - col]
    cost_matrix += [cost_row]

m = Munkres()
indexes = m.compute(cost_matrix)
print_matrix(matrix, msg='Highest profit through this matrix:')
total = 0
for row, column in indexes:
    value = matrix[row][column]
    total += value
    print(f'({row}, {column}) -> {value}')

print(f'total profit={total}')

You'll get result as below.

Highest profit through this matrix:
[1575000, 1575000, 1072500, 1072500, 1070000, 1070000, 1050000, 1035000, 1035000, 1015000, 1015000, 1000000, 1000000]
[1275000, 1275000, 1278000, 1278000, 1242000, 1242000, 1266000, 1806000, 1806000, 1191000, 1191000, 1191000, 1191000]
[1530000, 1530000, 1822500, 1822500, 1813500, 1813500, 1804500, 1773000, 1773000, 1746000, 1746000, 1710000, 1710000]
[1005000, 1005000, 1005000, 1005000, 1005000, 1005000, 1005000,  960000,  960000,  960000,  960000,  960000,  960000]
[2436000, 2436000, 2905000, 2905000, 2877000, 2877000, 2849000, 2814000, 2814000, 2779000, 2779000, 2730000, 2730000]
[1881000, 1881000, 1890000, 1890000, 1863000, 1863000, 1854000, 1822500, 1822500, 1804500, 1804500, 1786500, 1786500]
[2520000, 2520000, 1716000, 1716000, 1712000, 1712000, 1680000, 1656000, 1656000, 1624000, 1624000, 1600000, 1600000]
[1487500, 1487500, 1491000, 1491000, 1449000, 1449000, 1477000, 2107000, 2107000, 1389500, 1389500, 1389500, 1389500]
[1870000, 1870000, 2227500, 2227500, 2216500, 2216500, 2205500, 2167000, 2167000, 2134000, 2134000, 2090000, 2090000]
[1608000, 1608000, 1608000, 1608000, 1608000, 1608000, 1608000, 1536000, 1536000, 1536000, 1536000, 1536000, 1536000]
(0, 0) -> 1575000
(1, 7) -> 1806000
(2, 4) -> 1813500
(3, 12) -> 960000
(4, 3) -> 2905000
(5, 2) -> 1890000
(6, 1) -> 2520000
(7, 8) -> 2107000
(8, 5) -> 2216500
(9, 6) -> 1608000
total profit=19401000