Converting Integer programming to binary in python
<p><a href="http://i.stack.imgur.com/TpuQy.png" rel="nofollow"><img src="http://i.stack.imgur.com/TpuQy.png" alt="Excel Image"></a></p>

<p>See the image above to understand my explanation of the problem.</p>

<pre><code>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)
</code></pre>

<p>The code I have written is above. The number in the output I am interested is <code>fun : -2400.0</code> &lt;-- This is the current result. This is not what I want though.</p>

<p>Here is the problem and what I am looking for.</p>

<p>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 <code>fun : -2800.0</code>, which is part of the 4th column in LHS table.</p>

<p>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 &lt;= 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.</p>

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

<p>There has to be a simple way with linprog.</p>

<p>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.</p>

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

<pre><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)
</code></pre>

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

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

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

<ul>
<li>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?</li>
<li>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:

<ul>
<li><code>z = 1*x0 + 1200*x1 + 800*x2 + 800</code></li>
<li><strong>This is nowhere explained in your question and is important here!</strong></li>
</ul></li>
</ul>

<h2>How to handle the problem then?</h2>

<h3>Correct approach: ignore the constant offset of 800 &amp; correct objective later</h3>

<p>The following code (i'm using the variable-names in a common way) ignores the offset (<strong>a constant offset does not change the result regarding the decision-variables</strong>). 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!</p>

<pre><code>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)
</code></pre>

<p>Result:</p>

<pre><code>*** 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.])
</code></pre>

<p>After negating the objective, just add the offset and you receive your desired result of 2800!</p>

<h3>Silly approach: add some variable which is fixed to describe offset</h3>

<pre><code>""" 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)
</code></pre>

<p>Result:</p>

<pre><code>*** 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.])
</code></pre>

<h2>But will this work in general?</h2>

<p><strong>The Linear-programming approach will not work in general</strong>. 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!</p>

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

<p>Of course you could stick to a MIP-solver then, but:</p>

<ul>
<li>MIP-problems are hard in general</li>
<li>There is no MIP-solver within numpy/scipy</li>
</ul>

<p>Code:</p>

<pre><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 &lt;= b_ub
    for i in range(n):
        model += 0 &lt;= x[i] &lt;= 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()
</code></pre>

<p>Output:</p>

<pre><code>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 &lt;module&gt;
solve_random_until_unequal()
File "so_linprog_v3.py", line 43, in solve_random_until_unequal
assert np.isclose(lp_obj, mip_obj)
AssertionError
</code></pre>

python binary integer linear-programming