0

I would like to solve the following problem, where I would want to know which numbers in the "Values" column adds up to the "Find" value (129.18).

I want to solve this using numpy's lingprog function, where I would assign 0 or 1 as the multiplier, such that the solution would give 1 for the values 4.28 & 124.90, and 0 for the rest of the values. The multiplier values can only be 0 or 1 (integers).

The issue is I have no Math background and I don't think I understand the examples in http://www.vision.ime.usp.br/~igor/articles/optimization-linprog.html and the documentation under https://docs.scipy.org

Values    Multiplier    Product        Find: 129.18

4.28 **   1             4.28           
135.81    1             135.81
124.90 ** 1             124.90
293.51    1             293.51
7981.13   1             7981.13

The code I have so far is:

import numpy as np
from scipy.optimize import linprog
from numpy.linalg import solve

A = np.array([[1,1,1,1,1]])
B = np.array([129.18])

c = np.array([4.28, 135.81, 124.9, 293.51, 7981.13])

res = linprog(c,
          A_eq=A,
          b_eq=B,
          bounds=(0, 1)
          )
print('Optimal value:', res.fun, '\nX:', res.x)
print(res)

Obviously this is not working. How should I change the code so it meets my criteria?

1st time poster, but long time beneficiary of stackoverflow :) - thanks for any help that I can get on this question!

Cheers,

Warren Weckesser
  • 110,654
  • 19
  • 194
  • 214
gwoo
  • 31
  • 7
  • 2
    *"The multiplier values can only be 0 or 1 (integers)."* Then `linprog` won't work for this problem. `linprog` assumes the variables over which it optimizes are continuous. It does not solve the [integer programming](https://en.wikipedia.org/wiki/Integer_programming) problem. – Warren Weckesser Aug 28 '17 at 06:25
  • Assuming `linprog` *would* work for your problem, you'd need to exchange the values of `A` and `c` because your constraint is `sum(values * x) = product`. This will solve the problem, but you will get `x` between 1 and 0. – MB-F Aug 28 '17 at 06:29
  • Thanks @WarrenWeckesser. Is there any way Python can solve this type of integer problem? – gwoo Aug 29 '17 at 05:43
  • Thanks @kazemakase. I don't think I understand. I tried swapping 'A' and 'c' but the code doesn't compile after the swap – gwoo Aug 29 '17 at 05:44
  • @gwoo swap just the values, the shape is fine: `A = np.array([[4.28, 135.81, 124.9, 293.51, 7981.13]])` and `c = np.array([1,1,1,1,1])`. But although this should work it will not give you the results you expect. – MB-F Aug 29 '17 at 06:25
  • thanks @kazemakase, got it compiled - and will try to explore around and see how I can solve this problem :) – gwoo Aug 30 '17 at 04:09
  • @kazemakase you pointed me to the right direction - was searching further and found this https://stackoverflow.com/questions/26305704/python-mixed-integer-linear-programming :) cheers – gwoo Aug 30 '17 at 04:51

0 Answers0