see image above understand explanation of problem.
from scipy.optimize import linprog = [-800,-1200,-800] b = [[200,100,400],[200,200,400],[200,300,200]] c = [600,600,600] result = linprog(a,b,c) print(result) the code have written above. number in output interested fun : -2400.0 <-- current result. not want though.
here problem , looking for.
in picture, there 2 tables. table on rhs integer part , lhs table binary part. answer want fun : -2800.0, part of 4th column in lhs table.
let me tell how determined answer. first, can see there possible combinations of 0's , 1's written 3 assignments in lhs table. have find best highest number 4th column lhs satisfies conditions in rhs table. ex: starting top; numbers taken lhs , rhs table. 1 means choose assignment , 0 means don't choose. first row has 1 1 1 meaning choosing assignments. now, add numbers day 0,1,and 2 , can see go above 600. adding 200*1+100*1+400*1=700 greater 600. same thing day 1 , 2. so, 2801 not number want. next, choose 2800, , satisfy total condition of every added number <= 600 because assignment1 0, 200*0+100*1+400*1=500, less 600, , same thing remaining 2 days.
i don't understand how put every single thing in python , result of -2800 instead -2400.
there has simple way linprog.
the way got numbers in 4th of lhs table using green highlighted numbers rhs table, on last row of lhs table. did =((b5+$b$13)+(c5*$c$13)+(d5*$d$13)) 2801 , on remaining ones.
without using linprog, can't think better following code:
b = [800,1200,800] = [[200,100,400],[200,200,400],[200,300,200]] num in a[0],a[1],a[2]: t0 = num[0]*1 + num[1]*1 + num[2]*1 t1 = num[0]*0 + num[1]*1 + num[2]*1 print(t0)
first of all: your question very badly phrased (and usage of linprog not common; variable a typically 2d-one).
usually i'm hesitant work on these kind of questions (=very incomplete), think got problem now.
what's big problem question/formulation?
- you did not tell us, 4th column of left table came from! these values fixed (independent on remaining table), or these somehow correlated?
- after checking values, understood, these values themself (let's call them z) linear-function of decisions-variables of following form:
z = 1*x0 + 1200*x1 + 800*x2 + 800- this explained in question , important here!
how handle problem then?
correct approach: ignore constant offset of 800 & correct objective later
the following code (i'm using variable-names in common way) ignores offset (a constant offset not change result regarding decision-variables). therefore, want add offset obtained solution later / or ignore returned objective , calculate formula above!
from scipy.optimize import linprog import numpy np a_ub = [[200, 100, 400], [200, 200, 300], [400, 400, 200]] b_ub = [600, 600, 600] c = [-1, -1200, -800] result = linprog(c,a_ub,b_ub, bounds=(0,1)) print('*** result: (negated, offset of 800 missing) ***\n') print(result) result:
*** result: (negated, offset of 800 missing) *** fun: -2000.0 message: 'optimization terminated successfully.' nit: 3 slack: array([ 100., 100., 0., 1., 0., 0.]) status: 0 success: true x: array([ 0., 1., 1.]) after negating objective, add offset , receive desired result of 2800!
silly approach: add variable fixed describe offset
""" alternative formulation introduce 4th variable w, set 1 , introduce offset objective """ scipy.optimize import linprog import numpy np a_ub = [[200, 100, 400, 0], [200, 200, 300, 0], [400, 400, 200, 0]] # no upper bound w b_ub = [600, 600, 600] c = [-1, -1200, -800, -800] # w*800 added objective a_eq = [[0, 0, 0, 1]] # w=1 fixed b_eq = [1] # "" "" result = linprog(c,a_ub,b_ub, a_eq, b_eq, bounds=(0,1)) print('*** alternative result (negated, including offset): ***\n') print(result) result:
*** alternative result (negated, including offset): *** fun: -2800.0 message: 'optimization terminated successfully.' nit: 4 slack: array([ 100., 100., 0., 1., 0., 0., 0.]) status: 0 success: true x: array([ 0., 1., 1., 1.]) but work in general?
the linear-programming approach not work in general. ayhan mentioned in comments, unimodular matrix mean, lp-solver guarantees optimal integer-solution. without rules data, characteristic of unimodularity not given in general!
look @ following example code, generates random-instance , compares result of lp-solver & , mip-solver. first random-instance fails, because lp-solution continuous!
of course stick mip-solver then, but:
- mip-problems hard in general
- there no mip-solver within numpy/scipy
code:
from scipy.optimize import linprog import numpy np cylp.cy import cycbcmodel, cyclpsimplex cylp.py.modeling.cylpmodel import cylpmodel, cylparray np.random.seed(1) def solve_lp(a_ub, b_ub, c): result = linprog(c,a_ub,b_ub, bounds=(0,1)) print(result) return result.fun def solve_mip(a_ub, b_ub, c): a_ub, b_ub, c = np.matrix(a_ub), np.array(b_ub), np.array(c) n = b_ub.shape[0] model = cylpmodel() x = model.addvariable('x', n, isint=true) model += a_ub*x <= b_ub in range(n): model += 0 <= x[i] <= 1 c = cylparray(c) model.objective = c*x s = cyclpsimplex(model) cbcmodel = s.getcbcmodel() cbcmodel.branchandbound() print('sol: ', cbcmodel.primalvariablesolution['x']) print('obj: ', cbcmodel.objectivevalue) return cbcmodel.objectivevalue def solve_random_until_unequal(): while true: a_ub = np.random.randint(0, 1000, size=(3,3)) b_ub = np.random.randint(0, 1000, size=3) c = [-1, -1200, -800] lp_obj = solve_lp(a_ub, b_ub, c) mip_obj = solve_mip(a_ub, b_ub, c) print('a_ub: ', a_ub) print('b_ub: ', b_ub) assert np.isclose(lp_obj, mip_obj) solve_random_until_unequal() output:
fun: -225.29335071707953 message: 'optimization terminated successfully.' nit: 1 slack: array([ 9.15880052e+02, 0.00000000e+00, 7.90482399e+00, 1.00000000e+00, 8.12255541e-01, 1.00000000e+00]) status: 0 success: true x: array([ 0. , 0.18774446, 0. ]) clp0000i optimal - objective value 0 clp0000i optimal - objective value 0 node 0 depth 0 unsatisfied 0 sum 0 obj 0 guess 0 branching on -1 clp0000i optimal - objective value 0 cbc0004i integer solution of -0 found after 0 iterations , 0 nodes (0.00 seconds) cbc0001i search completed - best objective -0, took 0 iterations , 0 nodes (0.00 seconds) cbc0035i maximum depth 0, 0 variables fixed on reduced cost clp0000i optimal - objective value 0 clp0000i optimal - objective value 0 ('sol: ', array([ 0., 0., 0.])) ('obj: ', -0.0) ('a_ub: ', array([[ 37, 235, 908], [ 72, 767, 905], [715, 645, 847]])) ('b_ub: ', array([960, 144, 129])) traceback (most recent call last): file "so_linprog_v3.py", line 45, in <module> solve_random_until_unequal() file "so_linprog_v3.py", line 43, in solve_random_until_unequal assert np.isclose(lp_obj, mip_obj) assertionerror 
Comments
Post a Comment