[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] Quadratic Programming
From: |
Meketon, Marc |
Subject: |
Re: [Help-glpk] Quadratic Programming |
Date: |
Thu, 24 Sep 2015 10:35:01 -0500 |
If the objective function is of the form:
sum{i in I} x[i]*x[i]
then you might be able to use a piece-wise linear formulation to approximate a
quadratic objective function.
For example (assuming the "x" above is non-negative)
#
------------------------------------------------------------------------------
# Parabolic deviation parameters
#
------------------------------------------------------------------------------
param NUM_PIECEWISE_LINEAR_BREAKPOINTS default 20;
param PIECEWISE_LINEAR_GAP_SIZE default 2;
set DEV_SECTIONS := 1..NUM_PIECEWISE_LINEAR_BREAKPOINTS;
var x{ i in I, s in DEV_SECTIONS }, >= 0.0, <= if s <
NUM_PIECEWISE_LINEAR_BREAKPOINTS then PIECEWISE_LINEAR_GAP_SIZE else BIG_NUMBER;
For constraints, wherever you would have "x[i]" replace it with
sum{ i in I, s in DEV_SECTIONS } x[ i, s ]
For the objective, use:
sum{ i in I, s in DEV_SECTIONS } x[ i, s ]*s
If your "x" is a free variable, then it gets a bit more complicated in that you
would need two sets of variables:
var xp{ i in I, s in DEV_SECTIONS }, >= 0.0, <= if s <
NUM_PIECEWISE_LINEAR_BREAKPOINTS then PIECEWISE_LINEAR_GAP_SIZE else BIG_NUMBER;
var xn{ i in I, s in DEV_SECTIONS }, >= 0.0, <= if s <
NUM_PIECEWISE_LINEAR_BREAKPOINTS then PIECEWISE_LINEAR_GAP_SIZE else BIG_NUMBER;
and the constraints would need to replace x[i] with
sum{ i in I, s in DEV_SECTIONS } (xp[ i, s ]-xn[i, s])
and the objective would be
sum{ i in I, s in DEV_SECTIONS } (xp[ i, s ]+xn[i, s])*s
-----Original Message-----
From: address@hidden [mailto:address@hidden On Behalf Of Andrew Makhorin
Sent: Thursday, September 24, 2015 6:28 AM
To: address@hidden
Cc: address@hidden
Subject: Re: [Help-glpk] Quadratic Programming
> I wonder if itâ€™s possible to solve an optimisation problem with linear
> constraints and quadratic objective function (the problem is convex)
> by glpk.
>
No, glpk does not support solving non-linear problems.
_______________________________________________
Help-glpk mailing list
address@hidden
https://lists.gnu.org/mailman/listinfo/help-glpk
This e-mail and any attachments may be confidential or legally privileged. If
you received this message in error or are not the intended recipient, you
should destroy the e-mail message and any attachments or copies, and you are
prohibited from retaining, distributing, disclosing or using any information
contained herein. Please inform us of the erroneous delivery by return e-mail.
Thank you for your cooperation.