Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
274 views
in Technique[技术] by (71.8m points)

mathematical optimization - How to convert quadratic to linear program?

I have an optimization problem that has in the objective function 2 multiplied variables, making the model quadratic.

I am currently using zimpl, to parse the model, and glpk to solve it. As they don't support quadratic programming, I would need to convert this to an MILP.

. The first variable is real, in range [0, 1], the second one is real, from range 0 to inf. This one could without a problem be integer.

The critical part in the objective function looks like this:

max ... + var1 * var2 + ...

I had similar problems in the constraints, but they were easily solvable.

How could I solve this kind of a problem in the objective function?

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

Models in this form are actually called bilinear optimization problems. The typical approach to linearizing bilinear terms is through something called the McCormick envelope.

Consider variables x and y, where you want x*y in the objective of your maximization problem. If we assume x and y are bounded by xL <= x <= xU and yL <= y <= yU, then we can replace x*y with w, an upper bound for the quantity, with the following constraints (you can see the derivation here):

w <= xU*y + x*yL - xU*yL
w <= x*yU + xL*y - xL*yU
xL <= x <= xU
yL <= y <= yL

Note that these constraints are all linear in the decision variables. There are corresponding lower bounds in the McCormick envelope, but since you're maximizing they're unimportant in your case.

If you want a tighter bound on x*y, you can split up the interval on one of the variables (I'll use x here) into ranges [xL1, xU1], [xL2, xU2], ..., [xLn, xUn], introducing auxiliary continuous variables {x1, x2, ..., xn} and {w1, w2, ..., wn} as well as auxiliary binary variables {z1, z2, ..., zn}, which will indicate which range of x values was selected. The constraints above could be replaced by (I'll show the index 1 case, but you would need these for all n indices):

w1 <= xU1*y + x1*yL - xU1*yL*z1
w1 <= x1*yU + xL1*y - xL1*yU*z1
xL*z1 <= x1 <= xU*z1

Basically you will have x1=0 and w1 <= 0 whenever z1=0 (aka this part of the range is not selected), and you will have the normal McCormick envelope if z1=1 (aka this part of the range is selected).

The last step is to generate x and w out of range-specific versions of these variables. This can be done with:

x = x1 + x2 + ... + xn
w = w1 + w2 + ... + wn

The larger you make n, the more accurate of an estimation you will have for the bilinear term. However large values of n will affect the tractability of solving your model.

One final note -- you indicate that one of your variables in unbounded, but the McCormick envelope requires bounds on both variables. You should fix bounds, solve, and if your optimal value is at the boundary then you should re-solve with a different boundary.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...