Forum Discussion
FICO
5 years agoCommunity Manager
Bug report: addVariable() has quadratic time complexity on QCQP's
Hi, I'm using the Python API of Xpress and I noticed that addVariable() has quadratic time complexity when the problem is a QCQP. This code here demonstrates the issue: import timeit
def create_...
FICO
5 years agoCommunity Manager
Thanks Michaja. It is a performance issue that is due to the extra overhead we need in order to link variables with quadratic constraints---it is indeed within the getVariable() call that most of the time is spent. We will fix this issue in a future release, but please note that for efficiency it would be far better to aggregate both the generation of variables and the insertion of constraints, as in the following code:
def create_qcqp(size):
import xpress as xp
p = xp.problem()
x = [[xp.var(name=f"v{i}"), xp.var(name=f"w{i}")] for i in range(size)]
p.addVariable(x)
p.addConstraint(x[i][0]**2 + x[i][1]**2 <= 0 for i in range(size))These are the times I get using your script with the modified function above (on a decent laptop):
2,000: 0.020
4,000: 0.039
8,000: 0.077
16,000: 0.152
32,000: 0.301
64,000: 0.619
128,000: 1.271
256,000: 2.700
512,000: 5.643
1,024,000: 11.469Related Content
Related Content
Quadratic Optimization
Hello! I have the following problem: I want to minimize a least square problem with restrictions using quadratic module from xpress MP. The model has the following form: F:=sum(i in 1..N) (y(i)-...14 years agoPlace FICO® Xpress Optimization ForumFICO® Xpress Optimization Forum1 unread comment1 unread0Views0likes1CommentMixed-Integer Quadratically-Constrained Programming (MIQCP)
Hello, I would like to solve a MIQCP problem in Xpress Python Interface, but I cannot find the online document prescribing the noticeble points need to be pay attention prior to solving such type of...7 years agoPlace FICO® Xpress Optimization ForumFICO® Xpress Optimization Forum4 unread comments4 unread0Views0likes4CommentsIs it possible to disable the implicit factor of 0.5 in the optimization objectives quadratic part?
Through trial and error, I figured out, that the XPress optimizer is using an implicit factor of 0.5 in the quadratic part of the optimization objective (which doesn't show up in the mps dumps btw.) ...3 years agoPlace FICO® Xpress Optimization ForumFICO® Xpress Optimization Forum4 unread comments4 unread0Views0likes4Comments