Suppose you have 3 coins in a list A = [coin1, coin2, coin3] and each coin has values in 3 currencies, e.g.
coin1 = {'EUR': 80000, 'USD': 0, 'GBP': 0},
coin2 = {'EUR': 10000, 'USD': 100000, 'GBP': 0},
coin3 = {'EUR': 10000, 'USD': 0, 'GBP': 100000}.
In total you have a value of 100'000 in each currency
Now, we randomly draw 3 values (one for each currency) that you have to pay, e.g. payment = [3000, 2900, 3150]
Given an objective function, the solver should select which coins from the list A I need to select in order to pay payment.
The only constraints are that the total value (in each currency) of the selected coins should be larger than the payment (in each currency).
After the payment, the selected coins are removed from A and the change is added to list A as one new coin. Here the Gekko solver returns a negative change value, i.e. it does not select those coins that cover the payment in each currency (details below:) Also after each payment there is a random deposit, i.e. one coin is added to A with similar values that you paid. (think of somebody paying you)
Now we call the currencies v_0, v_1, v_2.
The objective function is simply 1/(1 + total_input_in_currency_v0 - payment[0]) + 1/(1 + total_input_in_currency_v1 - payment[1]) + 1/(1 + total_input_in_currency_v2 - payment[2]):
Note that the total input in a currency depends on which coins where selected. The decision variable is x which is 0 or 1 for each coin (1 for selected, 0 for not selected)
Here is the main routine:
if __name__ == "__main__":
np.random.seed(2)
coin1 = {
'v_0': 80000,
'v_1': 0,
'v_2': 0
}
coin2 = {
'v_0': 10000,
'v_1': 100000,
'v_2': 0
}
coin3 = {
'v_0': 10000,
'v_1': 0,
'v_2': 100000
}
A = [coin1, coin2, coin3] # set of coins
for it in range(2): # two iterations
payment = abs(np.random.poisson(3000, 3)).tolist() # random payment values
x, change = optimize(np.array(A), payment) # optimization routine
A = [A[i] for i in range(len(x)) if x[i][0] != 1.0] # only keep not-selected coins in A
A.append(change) # Add the change
deposit = abs(np.random.poisson(3000, 3)).tolist()
d = {
'v_0': deposit[0],
'v_1': deposit[1],
'v_2': deposit[2],
}
A.append(d) # Add a deposit
The optimization routine is here:
def optimize(A, payment):
m = GEKKO()
x = [m.Var(lb=0, ub=1, integer=True) for i in range(len(A))]
input_tot = []
input_tot_values = []
# Calculate total input values for each currency
for j in range(3):
s = 0
for i in range(len(A)):
s = s + A[i][f'v_{j}'] * x[i]
input_tot.append(s)
input_tot_values.append(m.Intermediate(s)) # Intermediate s.t. we have evaluated expressions
# Constraints that the total input should be larger than the payment
m.Equation(equation=input_tot[0] > payment[0] + 1)
m.Equation(equation=input_tot[1] > payment[1] + 1)
m.Equation(equation=input_tot[2] > payment[2] + 1)
# objective function
obj = 1 / (1 + input_tot[0] - payment[0]) + 1 / (1 + input_tot[1] - payment[1]) + 1 / (1 + input_tot[2] - payment[2])
m.Maximize(obj)
m.options.SOLVER = 1
m.solve()
print(x)
change = {
'v_0': input_tot_values[0][0] - payment[0],
'v_1': input_tot_values[1][0] - payment[1],
'v_2': input_tot_values[2][0] - payment[2]
}
print('+++++++++++++++++++++++++++++++++++++++++')
print(f'Payment: {payment}')
print(f'Total Input: {input_tot_values}')
print(f'Change: {change}')
print('+++++++++++++++++++++++++++++++++++++++++')
return x, change
The final output in the second iteration is the following:
Each time step contains
Objects : 0
Constants : 0
Variables : 6
Intermediates: 3
Connections : 0
Equations : 7
Residuals : 4
Number of state variables: 6
Number of total equations: - 3
Number of slack variables: - 3
---------------------------------------
Degrees of freedom : 0
----------------------------------------------
Steady State Optimization with APOPT Solver
----------------------------------------------
[...]
No additional trial points, returning the best integer solution
Successful solution
---------------------------------------------------
Solver : APOPT (v1.0)
Solution time : 7.390000000305008E-002 sec
Objective : -6.992753623188407E-002
Successful solution
---------------------------------------------------
[[0.0], [0.0], [1.0]]
+++++++++++++++++++++++++++++++++++++++++
Payment: [2930, 2944, 3066]
Total Input: [[2949.0], [2967.0], [3019.0]]
Change: {'v_0': 19.0, 'v_1': 23.0, 'v_2': -47.0}
+++++++++++++++++++++++++++++++++++++++++
where we see that the total input for currency v_2 is less than the payment and hence resulting in a negative change. i.e. Gekko not satisfying the constraint.
Set the APOPT solver option for integer tolerance to a more stringent value such as minlp_integer_tol 1.0e-5. The default is 1e-2 so a value of 0.005 still qualifies as an integer value.
m.solver_options = ['minlp_integer_tol 1.0e-5']
This resolves the problem with negative change.
[[0.0], [1.0], [0.0]]
+++++++++++++++++++++++++++++++++++++++++
Payment: [2930, 2944, 3066]
Total Input: [[17010.0], [96992.0], [97012.0]]
Change: {'v_0': 14080.0, 'v_1': 94048.0, 'v_2': 93946.0}
+++++++++++++++++++++++++++++++++++++++++
Here is the complete script that solves as expected:
import numpy as np
from gekko import GEKKO
def optimize(A, payment):
m = GEKKO()
x = [m.Var(lb=0, ub=1, integer=True) for i in range(len(A))]
input_tot = []
# Calculate total input values for each currency
for j in range(3):
s = 0
for i in range(len(A)):
s = s + A[i][f'v_{j}'] * x[i]
input_tot.append(m.Intermediate(s))
# Constraints that the total input should be larger than the payment
m.Equation(input_tot[0] > payment[0] + 1)
m.Equation(input_tot[1] > payment[1] + 1)
m.Equation(input_tot[2] > payment[2] + 1)
# objective function
obj = 1 / (1 + input_tot[0] - payment[0]) \
+ 1 / (1 + input_tot[1] - payment[1]) \
+ 1 / (1 + input_tot[2] - payment[2])
m.Maximize(obj)
m.options.SOLVER = 1
m.solver_options = ['minlp_integer_tol 1.0e-5']
m.solve(disp=False)
m.open_folder()
print(x)
change = {
'v_0': input_tot[0][0] - payment[0],
'v_1': input_tot[1][0] - payment[1],
'v_2': input_tot[2][0] - payment[2]
}
print('+++++++++++++++++++++++++++++++++++++++++')
print(f'Payment: {payment}')
print(f'Total Input: {input_tot}')
print(f'Change: {change}')
print('+++++++++++++++++++++++++++++++++++++++++')
return x, change
np.random.seed(2)
coin1 = {
'v_0': 80000,
'v_1': 0,
'v_2': 0
}
coin2 = {
'v_0': 10000,
'v_1': 100000,
'v_2': 0
}
coin3 = {
'v_0': 10000,
'v_1': 0,
'v_2': 100000
}
A = [coin1, coin2, coin3] # set of coins
for it in range(2): # two iterations
payment = abs(np.random.poisson(3000, 3)).tolist() # random payment values
x, change = optimize(np.array(A), payment) # optimization routine
A = [A[i] for i in range(len(x)) if x[i][0] != 1.0] # only keep not-selected coins in A
A.append(change) # Add the change
deposit = abs(np.random.poisson(3000, 3)).tolist()
d = {
'v_0': deposit[0],
'v_1': deposit[1],
'v_2': deposit[2],
}
A.append(d) # Add a deposit
Additional information is available on Solver options.