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.

Was it helpful?

Solution

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)

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top