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())

I didnt how for CVXPY, so i tried to code this problem with CVXPY and i updated my question, thanks. — user3024655
– user3024655, Commented Jan 31, 2019 at 16:02

adrtam · Accepted Answer · 2019-01-31 16:23:53Z

1

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

answered Jan 31, 2019 at 16:23

adrtam

7,2712 gold badges15 silver badges28 bronze badges

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

6 Comments

user3024655 Over a year ago

Thank you for your ansmer ! But i still have the following error message x = cp.Variable(1, boolean=True), TypeError: __init__() got an unexpected keyword argument 'boolean' and I don't know how to solve it.

sascha Over a year ago

@user41037 Your are probably using an old version. Compare new API with old API. ECOS cannot solve that, ECOS_BB might do it; but it's not a real MIQP-solver and without the commercials you will have problems to get one usable from cvxpy (see this table).

user3024655 Over a year ago

Than you for your answer ! it works ! But my goal was to find the variables a,b,c,d that minimize the objective function. How one can handle it with cvxpy ? thank you.

adrtam Over a year ago

print(Y1.value), for example.

adrtam Over a year ago

delta = cp.Variable(4) and cp.sum(delta) == 1

|

John Hedengren · Accepted Answer · 2022-06-26 01:46:33Z

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)

Collectives™ on Stack Overflow

Mixed-Integer Quadratic Programming in Python

2 Answers 2

6 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related