Mixed-Integer Quadratic Programming in Python

Question

I would like to solve in Python the following Mixed-Integer Quadratic Programming in Python. Nevertheless, I'm not familiar with the optimization toolboxes of Python.

Can someone provide an example of code with the vectors X1, X2, X3, X4 given as below ?

X1 = np.array([3,10,20,10])
X2 = np.array([5,1,3,4])
X3 = np.array([2,3,1,4])
X4 = np.array([10,0,1,2])

The MIQP is written as :

I tried to solve it with CVXPY but i encoutered problem with the boolean variable x = cp.Variable(1, boolean=True):

import numpy
import numpy as np
import cvxpy as cp

X1 = np.array([3,10,20,10])
X2 = np.array([5,1,3,4])
X3 = np.array([2,3,1,4])
X4 = np.array([10,0,1,2])

M = 100

x = cp.Variable(1, boolean=True)
Y1 = cp.Parameter(4)
Y2 = cp.Parameter(4)
a = cp.Parameter(1)
b = cp.Parameter(1)
c = cp.Parameter(1)
d = cp.Parameter(1)
delta = cp.Variable(1)

constraints = [Y1 <= X1 - a, 
           Y1 <= X2 - b, 
           Y1 >= X1 - a - M*delta,
           Y1 >= X2 - b - M*(1-delta),
           Y2 <= X3 - c, 
           Y2 <= X4 - d, 
           Y2 >= X3 - c - M*delta,
           Y2 >= X4 - d - M*(1-delta),
           0 <= a, a <= 10,
           0 <= b, b <= 5,
           0 <= c, c <= 5,
           0 <= d, d <= 10,
           delta == x]

obj = cp.Minimize(cp.sum_squares(Y1-Y2))
prob = cp.Problem(obj, constraints)
print(prob.solve())

Answer 1

Gekko with the APOPT solver can handle MIQP problems in addition to more general Nonlinear Mixed Integer Programming (MINLP). The solution is:

 ---------------------------------------------------
 Solver         :  APOPT (v1.0)
 Solution time  :   2.610000000277068E-002 sec
 Objective      :    70.0000000000000     
 Successful solution
 ---------------------------------------------------
 
x:  1.0
obj:  70.0

Here is the Python script:

import numpy as np
from gekko import GEKKO
m = GEKKO()
X1 = m.Param([3,10,20,10])
X2 = m.Param([5,1,3,4])
X3 = m.Param([2,3,1,4])
X4 = m.Param([10,0,1,2])
M = 100
p = m.Array(m.FV,4,lb=0,ub=10); a,b,c,d=p
b.upper = 5; c.upper = 5
for pi in p:
    pi.STATUS=1
x = m.FV(lb=0,ub=1,integer=True); x.STATUS=1
Y1,Y2 = m.Array(m.Var,2)
delta = m.FV(); delta.STATUS=1

m.Equations([Y1 <= X1 - a, 
             Y1 <= X2 - b, 
             Y1 >= X1 - a - M*delta,
             Y1 >= X2 - b - M*(1-delta),
             Y2 <= X3 - c, 
             Y2 <= X4 - d, 
             Y2 >= X3 - c - M*delta,
             Y2 >= X4 - d - M*(1-delta),
             delta == x])

m.Minimize((Y1-Y2)**2)
m.options.IMODE=2
m.options.SOLVER=1
m.solve()
print('x: ', x.value[0])
print('obj: ', m.options.OBJFCNVAL)

Answer 2

In cvxpy, parameter is something you have a value to set to it. In your problem, basically all symbols other than the X1 to X4 are variables. So do a global replace of cp.Parameter to cp.Variable will work.

Then, I found the result to be

$ python3 cvxtest.py
69.99998471073722