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.

Christoph FG · Accepted Answer · 2015-06-30 13:40:55Z

1

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)

answered Jun 30, 2015 at 13:40

Christoph FG

512 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

How to solve a binary linear program with cvxopt? Python

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related