Converting Integer programming to binary in python

Question

See the image above to understand my explanation of the problem.

from scipy.optimize import linprog

a = [-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 I have written is above. The number in the output I am interested is fun : -2400.0 <-- This is the current result. This is not what I want though.

Here is the problem and what I am looking for.

In the picture, there are two tables. The table on the RHS is the integer part and the LHS table is the binary part. The answer that I want is fun : -2800.0, which is part of the 4th column in LHS table.

Let me tell you how I determined that answer. First, as you can see there are all possible combinations of 0's and 1's are written for all the three assignments in the LHS table. I have to find the best highest number from the 4th column LHS that satisfies all the conditions in RHS table. For ex: Starting with the top; numbers taken from LHS and RHS table. 1 means choose that assignment and 0 means don't choose. So the first row has 1 1 1 meaning choosing all the assignments. Now, we add all the numbers for day 0,1,and 2 and we can see that they all go above 600. Adding 200*1+100*1+400*1=700 which is greater than 600. Same thing for day 1 and 2. So, 2801 is not the number we want. Next, we choose 2800, and it does satisfy the total condition of every added number <= 600 because assignment1 is 0, so 200*0+100*1+400*1=500, which is less than 600, and same thing for the remaining two days.

I just don't understand how to put every single thing in python and get result of -2800 instead -2400.

There has to be a simple way with linprog.

The way I got the numbers in the 4th of LHS table was using the green highlighted numbers from RHS table, which are also on the last row of LHS table. I did =((B5+$B$13)+(C5*$C$13)+(D5*$D$13)) to get 2801 and so on for the remaining ones.

Without using linprog, I can't think anything better than the following code:

B = [800,1200,800]
A = [[200,100,400],[200,200,400],[200,300,200]]

for 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)

Are you trying to use a linear programming solver to solve a discrete problem? That's not going to work. — user2357112
– user2357112, Commented Sep 1, 2016 at 21:57
Isn't their a way to do it using linprog? If not, then I don't know a way to solve it. user2357112 ....i updated my answer with an additional code. — Master
– Master, Commented Sep 1, 2016 at 21:59
I did explain how I got 2801. Go ahead and run my first code, and you should have an idea about constraints and variables. — Master
– Master, Commented Sep 1, 2016 at 23:27
@Master I also don't understand your result of 2801. And your usage of linprog is at least weird. A should be 2d, b should be 1d! So (without too much analysis on my side), your LP-formulation does not make any sense to me, especially when seeing the tables in your post. — sascha
– sascha, Commented Sep 1, 2016 at 23:57
@ayhan I am sorry. I didn't mean to be rude to you. I apologize. — Master
– Master, Commented Sep 3, 2016 at 13:17

sascha · Accepted Answer · 2016-09-02 03:26:05Z

First of all: your question was very very badly phrased (and your usage of linprog is not common; Variable A is typically the 2d-one).

Usually i'm hesitant to work on these kind of questions (=very incomplete), but i think i got the problem now.

What's the big problem with your question/formulation?

You did not tell us, where the 4th column of the left table came from! Are these values fixed (independent on the remaining table), or are these somehow correlated?
After checking the values, i understood, that these values themself (let's call them z) are a linear-function of the decisions-variables of the following form:
- z = 1*x0 + 1200*x1 + 800*x2 + 800
- This is nowhere explained in your question and is important here!

How to handle the problem then?

Correct approach: ignore the constant offset of 800 & correct objective later

The following code (i'm using the variable-names in a common way) ignores the offset (a constant offset does not change the result regarding the decision-variables). Therefore, you would want to add the offset to your obtained solution later / or ignore the returned objective and calculate it yourself by the formula above!

from scipy.optimize import linprog
import numpy as 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 the objective, just add the offset and you receive your desired result of 2800!

Silly approach: add some variable which is fixed to describe offset

""" Alternative formulation
    We introduce a 4th variable W, which is set to 1 and introduce the offset
    into the objective
"""
from scipy.optimize import linprog
import numpy as np

a_ub = [[200, 100, 400, 0], [200, 200, 300, 0], [400, 400, 200, 0]]  # no upper bound for W 
b_ub = [600, 600, 600]
c = [-1, -1200, -800, -800]  # W*800 added to 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 will this work in general?

The Linear-programming approach will not work in general. As ayhan mentioned in the comments, a unimodular matrix would mean, that an LP-solver guarantees an optimal integer-solution. But without some rules about your data, this characteristic of unimodularity is not given in general!

Look at the following example code, which generates a random-instance and compares the result of a LP-solver & and a MIP-solver. The very first random-instance fails, because the LP-solution is continuous!

Of course you could stick to a MIP-solver then, but:

MIP-problems are hard in general
There is no MIP-solver within numpy/scipy

Code:

from scipy.optimize import linprog
import numpy as np
from cylp.cy import CyCbcModel, CyClpSimplex
from 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
    for i 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 and 0 nodes (0.00 seconds)
Cbc0001I Search completed - best objective -0, took 0 iterations and 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

Collectives™ on Stack Overflow

Converting Integer programming to binary in python

1 Answer 1

What's the big problem with your question/formulation?

How to handle the problem then?

Correct approach: ignore the constant offset of 800 & correct objective later

Silly approach: add some variable which is fixed to describe offset

But will this work in general?

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

What's the big problem with your question/formulation?

How to handle the problem then?

Correct approach: ignore the constant offset of 800 & correct objective later

Silly approach: add some variable which is fixed to describe offset

But will this work in general?

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related