How to solve a binary linear program with cvxopt? Python
Question: I know how to solve a linear program with cvxopt, but I don't know how to make
it when the variables are all 0 or 1 (binary problem). Here is my attempt
code:

    
    
    #/usr/bin/env python3
    # -*- coding: utf-8 -*-
    
    
    from cvxopt.modeling import variable, op, solvers
    import matplotlib.pyplot as plt
    import numpy as np
    
    x1 = variable()
    x2 = variable()
    x3 = variable()
    x4 = variable()
    
    c1 = (x1+x2+x3+x4 <= 2)
    c2 = (-x1-x2+x3 <= 0)
    c3 = (55*x1+40*x2+76*x3+68*x4 <= 200)
    c4 = (x3+x4 <= 1)
    #here is the problem.
    c5 = (x1 == 0 or x1 == 1)
    c6 = (x2 == 0 or x2 == 1)
    c7 = (x3 == 0 or x3 == 1)
    c8 = (x4 == 0 or x4 == 1)
    
    lp1 = op(70*x1-60*x2-90*x3-80*x4, [c1, c2, c3, c4, c5, c6, c7, c8])
    lp1.solve()
    print('\nEstado: {}'.format(lp1.status))
    print('Valor óptimo: {}'.format(-round(lp1.objective.value()[0])))
    print('Óptimo x1: {}'.format(round(x1.value[0])))
    print('Óptimo x2: {}'.format(round(x2.value[0])))
    print('Óptimo x3: {}'.format(round(x3.value[0])))
    print('Óptimo x4: {}'.format(round(x4.value[0])))
    print('Mult óptimo primera restricción: {}'.format(c1.multiplier.value[0]))
    print('Mult óptimo segunda restricción: {}'.format(c2.multiplier.value[0]))
    print('Mult óptimo tercera restricción: {}'.format(c3.multiplier.value[0]))
    print('Mult óptimo cuarta restricción: {}\n'.format(c4.multiplier.value[0]))
    

The result is:

    
    
         pcost       dcost       gap    pres   dres   k/t
     0: -3.0102e-09 -2.0300e+02  2e+02  1e-02  8e-01  1e+00
     1: -3.5175e-11 -2.4529e+00  2e+00  1e-04  1e-02  1e-02
     2:  1.9739e-12 -2.4513e-02  2e-02  1e-06  1e-04  1e-04
     3:  5.0716e-13 -2.4512e-04  2e-04  1e-08  1e-06  1e-06
     4: -7.9906e-13 -2.4512e-06  2e-06  1e-10  1e-08  1e-08
    Terminated (singular KKT matrix).
    
    Estado: unknown
    Valor óptimo: 0
    Óptimo x1: 0
    Óptimo x2: 0
    Óptimo x3: 0
    Óptimo x4: 0
    Mult óptimo primera restricción: 1.1431670510974203e-07
    Mult óptimo segunda restricción: 0.9855547161745738
    Mult óptimo tercera restricción: 9.855074750509187e-09
    Mult óptimo cuarta restricción: 2.5159510552878724e-07
    

I've read the cvxopt doc, but i don't find anything about binary linear
problems.


Answer: cvxopt cannot solve binary linear programs. Given the size of your problem you
could try writing your own little branch and bound algorithm:

1) Solve the linear program

2) pick a fractional solution variable x_f and create two new problem "leafs"

2a) problem 1) with additional constraint x_f <= 0

2b) problem 1) with additional constraint x_f >= 1

Repeat...

(or use Excel solver)

