Paolo;
Your first issue of INJi * WITHi =3D 0 complementarity is easily =
modeled by adding two binary variables for each quantity i.e., yINJi and =
yWITHi then you need three constraints:
1. =
INJi <=3D uINJi * yINJi
2. =
WITHi <=3D uWITHi * yWITHi
3. =
yINHi + yWITHi =3D 1 or <=3D 1
4. =
yINJi, yWITHi are binary
The first two constraints are semi-continuous and third is a SOS1/GUB =
where the “u” prefix is the upper bound on the =
quantities. A lower bound is an exercise for =
you.
Your second issue requires piecewise linear approximation of the cost =
curves due to most likely economizes/diseconomies-of-scale. You =
will need to define regions of linearity and create extra binary =
variables for these regions with either SOS1 or SOS2 constraints =
depending on how you implement the “separable programming” =
aspects.
I hope this helps - Jeff
From:=
=
help-glpk-bounces+jeff.kelly=3Dhoneywell.com@gnu.org =
[mailto:help-glpk-bounces+jeff.kelly=3Dhoneywell.com@gnu.org] On =
Behalf Of Paolo Rossi
Sent: Monday, April 04, 2011 1:48 =
PM
To: help-glpk@gnu.org
Subject: [Help-glpk] LP =
problem with variable coeffcients (parametric =
LPsimplex)
I =
am trying to replicate the modelling Byers, 2006. Commodity Storage =
Valuation: A linear optimization based on Traded Instruments, Energy =
Economics. The author is quite concise on how the model has been =
specified but it says that he used LpSolve
=
The paper assesses the =
value of a gas storage facility. The value is a function =
of:
- =
; Injected quantity: =
&=
nbsp; &n=
bsp; INJ
- =
; Withdrawn quantity: =
&=
nbsp; =
WITH
- =
; Price =
paid for injections: =
&=
nbsp; Pi
- =
; Price =
paid for withdrawals: =
&=
nbsp; Pw
- =
; cost =
ofinjecting one unit of gas: =
ci
- =
; cost =
of withdrawing one unit of gas: cw
=
If one takes two periods, =
=
Max -INJ1 =
x pi,1 + WITH1 x pw,1 =
– ci,1 x INJ1 – cw,1 x =
WITH1 – INJ2 x pi,2 =
+ WITH2 x pw,2 – ci,2 x INJ2– cw,2 x =
WITH2
=
Constraints
- =
; For =
each time period i, if INJi > 0 then WITHi =3D 0 and if WITHi > 0 =
then INJi =3D 0 - you can either withdraw or inject. I thought of using =
a binary variable but then I realised that it would need to multiply =
INJi and WITHi so I got stuck as it would violate linearity of objective =
functions
- =
;
=
- =
; For =
each time period I, cw,I and ci,I (cost of withdrawing and cost of =
injecting) are a function of the gas stored in the facility. The =
right curve here would be something similar to an exponential function =
through the origin for ci, i.e. the more gas you have in the facility =
the more it costs to push an extra unit of gas in. If one works with =
strep functions, the formulation would be something =
like
ci =3D =
1 if sum of (inj – with ) over the =
periods up to i is =
<=3D 3
&nbs=
p; 2 if sum of =
(inj – with ) over the periods up to i =
is > 3 and =
<=3D 6
&nbs=
p; 3 if sum of =
(inj – with ) over the periods up to i =
is > =
6
=
For cw, the curve would be =
symmetric to the one above.
cw =
=3D 3 if sum of (inj – with ) over the =
periods up to i =
is =
<=3D 3
&nbs=
p; 2 if sum of =
(inj – with ) over the periods up to i =
is > 3 =
and <=3D 6
&nbs=
p; 1 if sum of =
(inj – with ) over the periods up to i =
is > =
6
=
I am pretty stuck here so =
thanks a lot for any help
------_=_NextPart_001_01CBF2F5.564679D3--
From MAILER-DAEMON Mon Apr 04 15:09:35 2011
Received: from mailman by lists.gnu.org with archive (Exim 4.43)
id 1Q6p9b-0008A0-Ow
for mharc-help-glpk@gnu.org; Mon, 04 Apr 2011 15:09:35 -0400
Received: from [140.186.70.92] (port=44667 helo=eggs.gnu.org)
by lists.gnu.org with esmtp (Exim 4.43) id 1Q6p9Y-00089n-UP
for help-glpk@gnu.org; Mon, 04 Apr 2011 15:09:34 -0400
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
(envelope-from
) id 1Q6p9X-0005Sn-4K
for help-glpk@gnu.org; Mon, 04 Apr 2011 15:09:32 -0400
Received: from mail-qy0-f169.google.com ([209.85.216.169]:63263)
by eggs.gnu.org with esmtp (Exim 4.71)
(envelope-from ) id 1Q6p9W-0005Sj-Uk
for help-glpk@gnu.org; Mon, 04 Apr 2011 15:09:31 -0400
Received: by qyk2 with SMTP id 2so1417206qyk.0
for ; Mon, 04 Apr 2011 12:09:30 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=googlemail.com; s=gamma;
h=domainkey-signature:mime-version:in-reply-to:references:date
:message-id:subject:from:to:cc:content-type;
bh=nepbMZopW01HMdsqlecpeXlEWwvewUJ8YHNmMoTdv6o=;
b=HQu20d0WXAD/B2jJlrHDeYaHBqFIbq/Zdrfs/zi55X2cOir16mLSzmA6Cyy5IWi47v
59STzBDDUhtLhz4AOj5Dan9HPHMpZ18qtuFI2F3KkDt9/fVNeCoG/ThqrCnCTQMEJ/Se
4z/gD3rUkIE4RFJYDpXQYsuvpfOc+2WILHsEs=
DomainKey-Signature: a=rsa-sha1; c=nofws; d=googlemail.com; s=gamma;
h=mime-version:in-reply-to:references:date:message-id:subject:from:to
:cc:content-type;
b=vNqx97y1qkkPPslqqnp3qTpLClJTrpHmLDnFwZX1g7NTHnEJ6dFRXggdoFx1FFQz46
v9VJBuTMwOv0gzW3GiHxiNr+vtcZwyLP/ghzX3gCpO8fGbJiHaRBnIQ6kvbOCtP9YM61
ah7sl6vnaKEviT+jeyCFI2HVh66G2BFqKIlWs=
MIME-Version: 1.0
Received: by 10.229.17.130 with SMTP id s2mr6081772qca.22.1301944170377; Mon,
04 Apr 2011 12:09:30 -0700 (PDT)
Received: by 10.229.217.138 with HTTP; Mon, 4 Apr 2011 12:09:30 -0700 (PDT)
In-Reply-To: <893E047B49F4AC409A76C4E407A3F7DE028ABBCD@DE08EV1001.global.ds.honeywell.com>
References:
<893E047B49F4AC409A76C4E407A3F7DE028ABBCD@DE08EV1001.global.ds.honeywell.com>
Date: Mon, 4 Apr 2011 20:09:30 +0100
Message-ID:
Subject: Re: [Help-glpk] LP problem with variable coeffcients (parametric
LPsimplex)
From: Paolo Rossi
To: "Kelly, Jeff (ON0F)"
Content-Type: multipart/alternative; boundary=0015175ce232caf2ab04a01c7f43
X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 2)
X-Received-From: 209.85.216.169
Cc: help-glpk@gnu.org
X-BeenThere: help-glpk@gnu.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: "Users list for GLPK \(GNU Linear Programming Kit\)"
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
X-List-Received-Date: Mon, 04 Apr 2011 19:09:34 -0000
--0015175ce232caf2ab04a01c7f43
Content-Type: text/plain; charset=windows-1252
Content-Transfer-Encoding: quoted-printable
Hi Jeff,
thanks for that. I had figured it out in the meantime (while cradling my so=
n
to sleep!) that the first one could be solved by something like
INJi <=3D MaxInj * BInj
Withi <=3D MaxWith * BWith
BInj + BWith =3D 1
which is I think exactly what you mention. So thank you very much for your
reply, as I was wondering if my reasoning was making sense! At the very
beginning I thought I'd need to introduce BInj*INJi in the objective
function - that is why I stopped due to the introduction of non-linearity i=
n
the objective function.
I get the hint from your remark on my second question but I really have to
think about how to implement it. Sorry my background is not in operations
Research..
Paolo
On 4 April 2011 19:23, Kelly, Jeff (ON0F) wrote:
> Paolo;
>
>
>
> Your first issue of INJi * WITHi =3D 0 complementarity is easily modeled =
by
> adding two binary variables for each quantity i.e., yINJi and yWITHi then
> you need three constraints:
>
> 1. INJi <=3D uINJi * yINJi
>
> 2. WITHi <=3D uWITHi * yWITHi
>
> 3. yINHi + yWITHi =3D 1 or <=3D 1
>
> 4. yINJi, yWITHi are binary
>
> The first two constraints are semi-continuous and third is a SOS1/GUB whe=
re
> the =93u=94 prefix is the upper bound on the quantities. A lower bound i=
s an
> exercise for you.
>
>
>
> Your second issue requires piecewise linear approximation of the cost
> curves due to most likely economizes/diseconomies-of-scale. You will nee=
d
> to define regions of linearity and create extra binary variables for thes=
e
> regions with either SOS1 or SOS2 constraints depending on how you impleme=
nt
> the =93separable programming=94 aspects.
>
>
>
> I hope this helps - Jeff
>
>
>
>
>
> *From:* help-glpk-bounces+jeff.kelly=3Dhoneywell.com@gnu.org [mailto:
> help-glpk-bounces+jeff.kelly=3Dhoneywell.com@gnu.org] *On Behalf Of *Paol=
o
> Rossi
> *Sent:* Monday, April 04, 2011 1:48 PM
> *To:* help-glpk@gnu.org
> *Subject:* [Help-glpk] LP problem with variable coeffcients (parametric
> LPsimplex)
>
>
>
> Hi everyone,
>
>
>
> I am trying to replicate the modelling Byers, 2006. Commodity Storage
> Valuation: A linear optimization based on Traded Instruments, Energy
> Economics. The author is quite concise on how the model has been specifie=
d
> but it says that he used LpSolve
>
>
>
> The paper assesses the value of a gas storage facility. The value is a
> function of:
>
> - Injected quantity: INJ
>
> - Withdrawn quantity: WITH
>
> - Price paid for injections: Pi
>
> - Price paid for withdrawals: Pw
>
> - cost ofinjecting one unit of gas: ci
>
> - cost of withdrawing one unit of gas: cw
>
>
>
> If one takes two periods,
>
>
>
> Max -INJ1 x pi,1 + WITH1 x pw,1 =96 ci,1 x INJ1 =96 cw,1 x =
WITH1
> =96 INJ2 x pi,2 + WITH2 x pw,2 =96 ci,2 x INJ2=96 cw,2 x WITH2
>
>
>
> Constraints
>
> - For each time period i, if INJi > 0 then WITHi =3D 0 and if WI=
THi
> > 0 then INJi =3D 0 - you can either withdraw or inject. I thought of usi=
ng a
> binary variable but then I realised that it would need to multiply INJi a=
nd
> WITHi so I got stuck as it would violate linearity of objective functions
>
> -
>
> - For each time period I, cw,I and ci,I (cost of withdrawing and
> cost of injecting) are a function of the gas stored in the facility. The
> right curve here would be something similar to an exponential function
> through the origin for ci, i.e. the more gas you have in the facility the
> more it costs to push an extra unit of gas in. If one works with strep
> functions, the formulation would be something like
>
> ci =3D 1 if sum of (inj =96 with ) over the periods up to i is
> <=3D 3
>
> 2 if sum of (inj =96 with ) over the periods up to i
> is > 3 and <=3D 6
>
> 3 if sum of (inj =96 with ) over the periods up to i
> is > 6
>
>
>
> For cw, the curve would be symmetric to the one above.
>
> cw =3D 3 if sum of (inj =96 with ) over the periods up to i is
> <=3D 3
>
> 2 if sum of (inj =96 with ) over the periods up to i
> is > 3 and <=3D 6
>
> 1 if sum of (inj =96 with ) over the periods up to i
> is > 6
>
>
>
> I am pretty stuck here so thanks a lot for any help
>
>
>
> Paolo
>
>
>
>
>
--0015175ce232caf2ab04a01c7f43
Content-Type: text/html; charset=windows-1252
Content-Transfer-Encoding: quoted-printable
Hi Jeff,
=A0
thanks for that. I had figured it out in the meantime (while cradling =
my son to sleep!) that the first one could be solved by something like
=A0
INJi <=3D MaxInj * =
BInj
Withi <=3D MaxWith =
* BWith
BInj + BWith =3D 1
=A0
which is I think exact=
ly what you mention. So thank you very much=A0 for your reply, as I was won=
dering if my reasoning was making sense!=A0At the very beginning I thought =
I'd need to introduce BInj*INJi in the objective function - that is why I stopped due to the intro=
duction of non-linearity in the objective function.
=A0
I get the hint from your remark on my second ques=
tion but=A0I really have to think about how to implement it. Sorry my backg=
round is not in operations Research..
=A0
Paolo=A0
=A0
=A0
On 4 April 2011 19:23, Kelly, Jeff (ON0F)
<jeff.kelly@hone=
ywell.com> wrote:
Paol=
o;
=A0<=
/span>
Your=
first issue of INJi * WITHi =3D 0 complementarity is easily modeled by add=
ing two binary variables for each quantity i.e., yINJi and yWITHi then you =
need three constraints:
1.=A0=A0=A0=
=A0=A0=A0 INJi <=3D uINJi * yINJi
2.=A0=A0=A0=
=A0=A0=A0 WITHi <=3D uWITHi * yWITHi
3.=A0=A0=A0=
=A0=A0=A0 yINHi + yWITHi =3D 1 or <=3D 1
4.=A0=A0=A0=
=A0=A0=A0 yINJi, yWITHi are binary
The =
first two constraints are semi-continuous and third is a SOS1/GUB where the=
=93u=94 prefix is the upper bound on the quantities.=A0 A lower bound is a=
n exercise for you.
=A0<=
/span>
Your=
second issue requires piecewise linear approximation of the cost curves du=
e to most likely economizes/diseconomies-of-scale.=A0 You will need to defi=
ne regions of linearity and create extra binary variables for these regions=
with either SOS1 or SOS2 constraints depending on how you implement the =
=93separable programming=94 aspects.
=A0<=
/span>
I ho=
pe this helps - Jeff
=A0<=
/span>
=A0<=
/span>
=A0
I am trying to replicate the modelling Byers, =
2006. Commodity Storage Valuation: A linear optimization based on Traded In=
struments, Energy Economics. The author is quite concise on how the model h=
as been specified but it says that he used LpSolve
=A0
The paper assesses the value of a gas storage =
facility. The value is a function of:
-=A0=A0=A0=A0=A0=A0=A0=A0=A0 Injected quantity: =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 INJ
-=A0=A0=A0=A0=A0=A0=A0=A0=A0 =A0Withdrawn quantity: =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=
=A0=A0=A0=A0=A0=A0=A0=A0=A0 WITH
-=A0=A0=A0=A0=A0=A0=A0=A0=A0 Price paid for injections: =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=
=A0=A0=A0=A0=A0 Pi
-=A0=A0=A0=A0=A0=A0=A0=A0=A0 Price paid for withdrawals: =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=
=A0 Pw
-=A0=A0=A0=A0=A0=A0=A0=A0=A0 cost ofinjecting one unit of gas: =A0=A0=A0=A0=A0=A0=A0 ci
-=A0=A0=A0=A0=A0=A0=A0=A0=A0 cost of withdrawing one unit of gas: cw
=A0
If one takes two periods,
=A0
Max=A0=A0=A0 -INJ1 x pi,1=A0=A0 +=A0=A0 WITH1 =
x pw,1=A0=A0 =96=A0=A0 ci,1 x INJ1=A0=A0 =96=A0 cw,1 x WITH1=A0 =96=A0=A0 I=
NJ2 x pi,2=A0=A0=A0 +=A0=A0 WITH2 x pw,2=A0 =96=A0 ci,2 x INJ2=96 cw,2 x WI=
TH2
=A0
Constraints
-=A0=A0=A0=A0=A0=A0=A0=A0=A0 For each time period i, if INJi > 0 then WITHi =3D 0 and if WITHi=
> 0 then INJi =3D 0 - you can either withdraw or inject. I thought of u=
sing a binary variable but then I realised that it would need to multiply I=
NJi and WITHi so I got stuck as it would violate linearity of objective fun=
ctions
-=A0=A0=A0=A0=A0=A0=A0=A0=A0 =A0
-=A0=A0=A0=A0=A0=A0=A0=A0=A0 For each time period I, cw,I and ci,I (cost of withdrawing and cost =
of injecting) are a function of the gas stored in the facility.=A0 The righ=
t curve here would be something similar to an exponential function through =
the origin for ci, i.e. the more gas you have in the facility the more it c=
osts to push an extra unit of gas in. If one works with strep functions, th=
e formulation would be something like
ci =3D=A0 =A0=A0=A0 1=A0 if sum of (inj =96 wi=
th ) over the periods up to i=A0 is=A0=A0=A0=A0=A0=A0=A0=A0 <=3D 3
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 2=A0 i=
f sum of (inj =96 with ) over the periods up to i is=A0=A0=A0=A0=A0=A0=A0=
=A0=A0 > 3 and <=3D 6
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 3=A0 i=
f sum of (inj =96 with ) over the periods up to i is=A0=A0=A0=A0=A0=A0=A0=
=A0=A0 >=A0 6
=A0
For cw, the curve would be symmetric to the on=
e above.
cw =3D=A0 =A0=A0 3=A0 if sum of (inj =96 with =
) over the periods up to i is=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 <=3D 3
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 2=A0 i=
f sum of (inj =96 with ) over the periods up to i is=A0=A0=A0=A0=A0=A0=A0=
=A0=A0=A0 > 3 and <=3D 6
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 1=A0 i=
f sum of (inj =96 with ) over the periods up to i is=A0=A0=A0=A0=A0=A0=A0=
=A0=A0 >=A0 6
=A0
I am pretty stuck here so thanks a lot for any=
help
=A0
--0015175ce232caf2ab04a01c7f43--
From MAILER-DAEMON Mon Apr 04 15:15:27 2011
Received: from mailman by lists.gnu.org with archive (Exim 4.43)
id 1Q6pFH-0004k9-8h
for mharc-help-glpk@gnu.org; Mon, 04 Apr 2011 15:15:27 -0400
Received: from [140.186.70.92] (port=42694 helo=eggs.gnu.org)
by lists.gnu.org with esmtp (Exim 4.43) id 1Q6pFC-0004cK-Kq
for help-glpk@gnu.org; Mon, 04 Apr 2011 15:15:26 -0400
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
(envelope-from )
id 1Q6pF8-0006wM-W0
for help-glpk@gnu.org; Mon, 04 Apr 2011 15:15:22 -0400
Received: from de08ip008.honeywell.com ([199.61.24.27]:45717)
by eggs.gnu.org with esmtp (Exim 4.71)
(envelope-from )
id 1Q6pF8-0006vZ-Om
for help-glpk@gnu.org; Mon, 04 Apr 2011 15:15:18 -0400
Received-SPF: Neutral identity=mailfrom; client-ip=10.216.13.129;
receiver=DE08IP008.honeywell.com;
envelope-from="jeff.kelly@honeywell.com";
x-sender="jeff.kelly@honeywell.com"; x-conformance=spf_only;
x-record-type="v=spf1"
Received-SPF: None identity=helo; client-ip=10.216.13.129;
receiver=DE08IP008.honeywell.com;
envelope-from="jeff.kelly@honeywell.com";
x-sender="postmaster@de08ex6001.global.ds.honeywell.com";
x-conformance=spf_only
X-SBRS: None
X-SenderGroup: Relay_to_Internet
X-MailFlowPolicy: $Relay
X-Attachment_Filename: None
X-Attachment_Filesize: None
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AuwAAKEXmk0K2A2B/2dsb2JhbACCYJVAQIYGAYd0wWGDKAQBgj4EkQQU
X-IronPort-AV: E=Sophos;i="4.63,299,1299481200";
d="scan'208,217";a="266111341"
Received: from unknown (HELO de08ex6001.global.ds.honeywell.com)
([10.216.13.129])
by DE08IP008.honeywell.com with ESMTP; 04 Apr 2011 12:15:17 -0700
Received: from DE08EV1001.global.ds.honeywell.com ([10.216.13.115]) by
de08ex6001.global.ds.honeywell.com with Microsoft
SMTPSVC(6.0.3790.4675); Mon, 4 Apr 2011 15:15:16 -0400
x-mimeole: Produced By Microsoft Exchange V6.5
Content-class: urn:content-classes:message
MIME-Version: 1.0
Content-Type: multipart/alternative;
boundary="----_=_NextPart_001_01CBF2FC.A1810323"
Subject: RE: [Help-glpk] LP problem with variable coeffcients (parametric
LPsimplex)
Date: Mon, 4 Apr 2011 15:15:16 -0400
Message-ID: <893E047B49F4AC409A76C4E407A3F7DE028ABCE3@DE08EV1001.global.ds.honeywell.com>
In-Reply-To:
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
Thread-Topic: [Help-glpk] LP problem with variable coeffcients (parametric
LPsimplex)
Thread-Index: Acvy+9pa7Zn/UswXTW25B8+zAfZRLAAAC6qA
References: <893E047B49F4AC409A76C4E407A3F7DE028ABBCD@DE08EV1001.global.ds.honeywell.com>
From: "Kelly, Jeff (ON0F)"
To: "Paolo Rossi"
X-OriginalArrivalTime: 04 Apr 2011 19:15:16.0842 (UTC)
FILETIME=[A1AE34A0:01CBF2FC]
X-detected-operating-system: by eggs.gnu.org: Genre and OS details not
recognized.
X-Received-From: 199.61.24.27
Cc: help-glpk@gnu.org
X-BeenThere: help-glpk@gnu.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: "Users list for GLPK \(GNU Linear Programming Kit\)"
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
X-List-Received-Date: Mon, 04 Apr 2011 19:15:26 -0000
This is a multi-part message in MIME format.
------_=_NextPart_001_01CBF2FC.A1810323
Content-Type: text/plain;
charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
Paolo;
=20
That's ok, I'm a chemical engineer.
=20
Unless you want to write your own MISLP you will have to linearize your
cost profiles and then have the binaries select what region or segment
the costs should be in. It is actually a relatively easy thing to do.
=20
Jeff
=20
From: Paolo Rossi [mailto:statmailinglists@googlemail.com]=20
Sent: Monday, April 04, 2011 3:10 PM
To: Kelly, Jeff (ON0F)
Cc: help-glpk@gnu.org
Subject: Re: [Help-glpk] LP problem with variable coeffcients
(parametric LPsimplex)
=20
Hi Jeff,
=20
thanks for that. I had figured it out in the meantime (while cradling my
son to sleep!) that the first one could be solved by something like
=20
INJi <=3D MaxInj * BInj
Withi <=3D MaxWith * BWith
BInj + BWith =3D 1
=20
which is I think exactly what you mention. So thank you very much for
your reply, as I was wondering if my reasoning was making sense! At the
very beginning I thought I'd need to introduce BInj*INJi in the
objective function - that is why I stopped due to the introduction of
non-linearity in the objective function.
=20
I get the hint from your remark on my second question but I really have
to think about how to implement it. Sorry my background is not in
operations Research..
=20
Paolo=20
=20
=20
On 4 April 2011 19:23, Kelly, Jeff (ON0F)
wrote:
Paolo;
=20
Your first issue of INJi * WITHi =3D 0 complementarity is easily modeled
by adding two binary variables for each quantity i.e., yINJi and yWITHi
then you need three constraints:
1. INJi <=3D uINJi * yINJi=20
2. WITHi <=3D uWITHi * yWITHi
3. yINHi + yWITHi =3D 1 or <=3D 1
4. yINJi, yWITHi are binary
The first two constraints are semi-continuous and third is a SOS1/GUB
where the "u" prefix is the upper bound on the quantities. A lower
bound is an exercise for you.
=20
Your second issue requires piecewise linear approximation of the cost
curves due to most likely economizes/diseconomies-of-scale. You will
need to define regions of linearity and create extra binary variables
for these regions with either SOS1 or SOS2 constraints depending on how
you implement the "separable programming" aspects.
=20
I hope this helps - Jeff
=20
=20
From: help-glpk-bounces+jeff.kelly=3Dhoneywell.com =
@gnu.org [mailto:help-glpk-bounces+jeff.kelly
=3Dhoneywell.com
@gnu.org ] On Behalf Of Paolo
Rossi
Sent: Monday, April 04, 2011 1:48 PM
To: help-glpk@gnu.org
Subject: [Help-glpk] LP problem with variable coeffcients (parametric
LPsimplex)
=20
Hi everyone,
=20
I am trying to replicate the modelling Byers, 2006. Commodity Storage
Valuation: A linear optimization based on Traded Instruments, Energy
Economics. The author is quite concise on how the model has been
specified but it says that he used LpSolve
=20
The paper assesses the value of a gas storage facility. The value is a
function of:
- Injected quantity: INJ
- Withdrawn quantity: WITH
- Price paid for injections: Pi
- Price paid for withdrawals: Pw
- cost ofinjecting one unit of gas: ci
- cost of withdrawing one unit of gas: cw
=20
If one takes two periods,=20
=20
Max -INJ1 x pi,1 + WITH1 x pw,1 - ci,1 x INJ1 - cw,1 x
WITH1 - INJ2 x pi,2 + WITH2 x pw,2 - ci,2 x INJ2- cw,2 x WITH2
=20
Constraints
- For each time period i, if INJi > 0 then WITHi =3D 0 and if
WITHi > 0 then INJi =3D 0 - you can either withdraw or inject. I thought
of using a binary variable but then I realised that it would need to
multiply INJi and WITHi so I got stuck as it would violate linearity of
objective functions
- =20
- For each time period I, cw,I and ci,I (cost of withdrawing
and cost of injecting) are a function of the gas stored in the facility.
The right curve here would be something similar to an exponential
function through the origin for ci, i.e. the more gas you have in the
facility the more it costs to push an extra unit of gas in. If one works
with strep functions, the formulation would be something like
ci =3D 1 if sum of (inj - with ) over the periods up to i is
<=3D 3
2 if sum of (inj - with ) over the periods up to i is
> 3 and <=3D 6
3 if sum of (inj - with ) over the periods up to i is
> 6
=20
For cw, the curve would be symmetric to the one above.=20
cw =3D 3 if sum of (inj - with ) over the periods up to i is
<=3D 3
2 if sum of (inj - with ) over the periods up to i is
> 3 and <=3D 6
1 if sum of (inj - with ) over the periods up to i is
> 6
=20
I am pretty stuck here so thanks a lot for any help
=20
Paolo
=20
=20
=20
------_=_NextPart_001_01CBF2FC.A1810323
Content-Type: text/html;
charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
Paolo;
That’s ok, I’m a chemical =
engineer.
Unless you want to write your own MISLP you will have to linearize =
your cost profiles and then have the binaries select what region or =
segment the costs should be in. It is actually a relatively easy =
thing to do.
Jeff
From:=
=
Paolo Rossi [mailto:statmailinglists@googlemail.com]
Sent: =
Monday, April 04, 2011 3:10 PM
To: Kelly, Jeff =
(ON0F)
Cc: help-glpk@gnu.org
Subject: Re: =
[Help-glpk] LP problem with variable coeffcients (parametric =
LPsimplex)
thanks for that. I had figured it out in the meantime =
(while cradling my son to sleep!) that the first one could be solved by =
something like
INJi =
<=3D MaxInj * BInj
Withi =
<=3D MaxWith * BWith
which is I think exactly what =
you mention. So thank you very much for your reply, as I was =
wondering if my reasoning was making sense! At the very beginning I =
thought I'd need to introduce BInj*INJi in the objective function - that =
is why I stopped due to the introduction of non-linearity in the =
objective function.
I get the hint from your remark =
on my second question but I really have to think about how to =
implement it. Sorry my background is not in operations =
Research..
On 4 April 2011 19:23, Kelly, Jeff (ON0F) <jeff.kelly@honeywell.com>=
wrote:
Paolo;
Your first issue of INJi * =
WITHi =3D 0 complementarity is easily modeled by adding two binary =
variables for each quantity i.e., yINJi and yWITHi then you need three =
constraints:
1. &nb=
sp; INJi <=3D =
uINJi * yINJi
2. &nb=
sp; WITHi <=3D =
uWITHi * yWITHi
3. &nb=
sp; yINHi + yWITHi =
=3D 1 or <=3D 1
4. &nb=
sp; yINJi, yWITHi =
are binary
The first two constraints are =
semi-continuous and third is a SOS1/GUB where the “u” prefix =
is the upper bound on the quantities. A lower bound is an exercise =
for you.
Your second issue requires =
piecewise linear approximation of the cost curves due to most likely =
economizes/diseconomies-of-scale. You will need to define regions =
of linearity and create extra binary variables for these regions with =
either SOS1 or SOS2 constraints depending on how you implement the =
“separable programming” aspects.
I hope this helps - =
Jeff
<=
/o:p>
I am trying =
to replicate the modelling Byers, 2006. Commodity Storage Valuation: A =
linear optimization based on Traded Instruments, Energy Economics. The =
author is quite concise on how the model has been specified but it says =
that he used LpSolve
<=
/o:p>
The paper =
assesses the value of a gas storage facility. The value is a function =
of:
- =
; Injected quantity: =
&=
nbsp; &n=
bsp; INJ
- =
; Withdrawn quantity: =
&=
nbsp; =
WITH
- =
; Price paid for injections: =
&=
nbsp; Pi
- =
; Price paid for withdrawals: =
&=
nbsp; Pw
- =
; cost ofinjecting one unit of gas: =
ci
- =
; cost of withdrawing one unit of gas: cw
<=
/o:p>
If one =
takes two periods,
<=
/o:p>
Max &nb=
sp; -INJ1 x pi,1 + WITH1 x =
pw,1 – ci,1 x INJ1 =
– cw,1 x WITH1 – INJ2 x =
pi,2 + WITH2 x pw,2 – =
ci,2 x INJ2– cw,2 x WITH2
<=
/o:p>
Constraints<=
o:p>
- =
; For each time period i, if INJi > 0 then WITHi =3D 0 =
and if WITHi > 0 then INJi =3D 0 - you can either withdraw or inject. =
I thought of using a binary variable but then I realised that it would =
need to multiply INJi and WITHi so I got stuck as it would violate =
linearity of objective functions
- =
;
- =
; For each time period I, cw,I and ci,I (cost of =
withdrawing and cost of injecting) are a function of the gas stored in =
the facility. The right curve here would be something similar to =
an exponential function through the origin for ci, i.e. the more gas you =
have in the facility the more it costs to push an extra unit of gas in. =
If one works with strep functions, the formulation would be something =
like
ci =
=3D 1 if sum of (inj – with ) over =
the periods up to i =
is <=3D =
3
=
=
2 if sum of (inj – with ) over the periods up to i =
is > 3 and =
<=3D 6
=
=
3 if sum of (inj – with ) over the periods up to i =
is > =
6
For cw, the =
curve would be symmetric to the one above.
cw =
=3D 3 if sum of (inj – with ) over the =
periods up to i =
is =
<=3D 3
=
=
2 if sum of (inj – with ) over the periods up to i =
is > 3 =
and <=3D 6
=
=
1 if sum of (inj – with ) over the periods up to i =
is > =
6
<=
/o:p>
I am pretty =
stuck here so thanks a lot for any help
<=
/o:p>
------_=_NextPart_001_01CBF2FC.A1810323--
From MAILER-DAEMON Mon Apr 04 17:24:26 2011
Received: from mailman by lists.gnu.org with archive (Exim 4.43)
id 1Q6rG6-00044J-Bu
for mharc-help-glpk@gnu.org; Mon, 04 Apr 2011 17:24:26 -0400
Received: from [140.186.70.92] (port=41843 helo=eggs.gnu.org)
by lists.gnu.org with esmtp (Exim 4.43) id 1Q6rG0-00041m-Iz
for help-glpk@gnu.org; Mon, 04 Apr 2011 17:24:25 -0400
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
(envelope-from
) id 1Q6rFw-0000F0-Im
for help-glpk@gnu.org; Mon, 04 Apr 2011 17:24:18 -0400
Received: from mail-qy0-f169.google.com ([209.85.216.169]:39712)
by eggs.gnu.org with esmtp (Exim 4.71)
(envelope-from ) id 1Q6rFw-0000Eu-70
for help-glpk@gnu.org; Mon, 04 Apr 2011 17:24:16 -0400
Received: by qyk2 with SMTP id 2so1506770qyk.0
for ; Mon, 04 Apr 2011 14:24:15 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=googlemail.com; s=gamma;
h=domainkey-signature:mime-version:in-reply-to:references:date
:message-id:subject:from:to:cc:content-type;
bh=RDbfiNZAZkN8ZWOiWYDLumFN5cBpug3kNs5okkCDKN0=;
b=wTD15Pr9QzUkxQp89RpMc4qtt8Hh6japolRBcBzXZfC01FDQZPZHECTY1PoUSVK9gG
BjyGAFHlrkjifh5fV9nTYvYnetJjcTru8bizaEqn8LgCoG5ve7BwdiZrbUd9o6EPf1nU
YGFOjoCCjndkhBfMeeSzqlBat9jmGc0k4cPXc=
DomainKey-Signature: a=rsa-sha1; c=nofws; d=googlemail.com; s=gamma;
h=mime-version:in-reply-to:references:date:message-id:subject:from:to
:cc:content-type;
b=ZpCztwuUyLcwd6ttLMjIU65/z3cub7yFLrwYbv3yvtXgeSGwIVjc+SPxxWyqlT2LxQ
MVToYOVMjBD5HlLfoVpmUj6WlUyn/AlldOxd1jCQF8i/PY0pGLrd0nKtmqVZf8j/rO5t
NvojKscejfhyNfpGSpMVq4Ztj1lVHgRgQzD/0=
MIME-Version: 1.0
Received: by 10.229.101.168 with SMTP id c40mr5676092qco.98.1301952255558;
Mon, 04 Apr 2011 14:24:15 -0700 (PDT)
Received: by 10.229.217.138 with HTTP; Mon, 4 Apr 2011 14:24:15 -0700 (PDT)
In-Reply-To: <893E047B49F4AC409A76C4E407A3F7DE028ABCE3@DE08EV1001.global.ds.honeywell.com>
References:
<893E047B49F4AC409A76C4E407A3F7DE028ABBCD@DE08EV1001.global.ds.honeywell.com>
<893E047B49F4AC409A76C4E407A3F7DE028ABCE3@DE08EV1001.global.ds.honeywell.com>
Date: Mon, 4 Apr 2011 22:24:15 +0100
Message-ID:
Subject: Re: [Help-glpk] LP problem with variable coeffcients (parametric
LPsimplex)
From: Paolo Rossi
To: "Kelly, Jeff (ON0F)"
Content-Type: multipart/alternative; boundary=0016364edfc4b5033704a01e611d
X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 2)
X-Received-From: 209.85.216.169
Cc: help-glpk@gnu.org
X-BeenThere: help-glpk@gnu.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: "Users list for GLPK \(GNU Linear Programming Kit\)"
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
X-List-Received-Date: Mon, 04 Apr 2011 21:24:25 -0000
--0016364edfc4b5033704a01e611d
Content-Type: text/plain; charset=windows-1252
Content-Transfer-Encoding: quoted-printable
Jeff,
With your help and some googling I am now at the next step. I hope so, at
least!
Suppose that my cost function depends on a SOS with 4 variables, i.e. 4
regions where I decide to linearise my cost function. When I say cost
function I mean a function describing total cost of production if productio=
n
falls into that region, not unitary cost of production as I meant in my
original post.
I understand I need 4 mutually exclusive binary variables, say INVi
(inventory)
INV1 + INV2 + INV3 + INV4 =3D 1.
I have been thinking how to model the relationship between the value of the
variable switching the binary INV on and off and the threshold values at
which the binaries INV get switched on/off. Let=92s call these thresholds T=
0,
T1, T2, T3 and T4 so that when the switching variable x is between T0 and T=
1
INV1 gets switched on.
if x >=3DT0 and if x < T1, INV1 is on, if T1 <=3D x < T2, INV2 etc.
My constraints would look like
x >=3D T0 x INV1, x <=3D T1*INV1
x >=3D T1 x INV2, x <=3D T2 x INV2
=85
x >=3D T3 x INV4, x <=3D T4 x INV4
Do they make sense?
I actually saw on the net that this can be simplified to
T1* INV1 + T2* INV2+ T3* INV3 + T4 * INV4=96 x =3D 0 with x > 0, X being th=
e
switching variable
but it would be nice to know if my reasoning makes sense.
The cost function which goes into the objective function is
becomes lc(x1) * INV1 + lc(x2) * INV2 + lc(x3) * INV3 + lc(x4) * INV4. So,
being pedant, the cost function is actually not linearised but approximated
by a step function. Is this true?
So in terms of the objective function, max total profits =3D max [ total
revenues - total costs] =3D max [total revenues - lc(x1) * INV1 + lc(x2) *
INV2 + lc(x3) * INV3 + lc(x4) * INV4 ].
If I wanted to use cost per unit of production, rather than total cost, I
would need to multiply an expression similar to lc(x1) * INV1 + lc(x2) *
INV2 + lc(x3) * INV3 + lc(x4) * INV4 (at least in spirit) by the variable x=
.
That would make my problem non-linear. Is this the reason why it is better
to model total costs?
Finally, this works for one time-period only, so if I have N time periods, =
I
need N sets of mutually exclusive variables so that in each time period ith
only one varibale in the ith set is on. My cost function becomes Sum with i
from 1 to N (lc(x1) * INVi1 + lc(xi2) * INVi2 + lc(xi3) * INVi3 + lc(xi4) *
INVi4). I am assuming the thresholds constants across time periods, which
suits me fine.
Is this correct?
Thanks a lot for your help. I am exhausted. I cannot wait to start analysin=
g
data instead of doing this type of thinking!
Thanks again,
Paolo
On 4 April 2011 20:15, Kelly, Jeff (ON0F) wrote:
> Paolo;
>
>
>
> That=92s ok, I=92m a chemical engineer.
>
>
>
> Unless you want to write your own MISLP you will have to linearize your
> cost profiles and then have the binaries select what region or segment th=
e
> costs should be in. It is actually a relatively easy thing to do.
>
>
>
> Jeff
>
>
>
> *From:* Paolo Rossi [mailto:statmailinglists@googlemail.com]
> *Sent:* Monday, April 04, 2011 3:10 PM
> *To:* Kelly, Jeff (ON0F)
> *Cc:* help-glpk@gnu.org
> *Subject:* Re: [Help-glpk] LP problem with variable coeffcients
> (parametric LPsimplex)
>
>
>
> Hi Jeff,
>
>
>
> thanks for that. I had figured it out in the meantime (while cradling my
> son to sleep!) that the first one could be solved by something like
>
>
>
> INJi <=3D MaxInj * BInj
>
> Withi <=3D MaxWith * BWith
>
> BInj + BWith =3D 1
>
>
>
> which is I think exactly what you mention. So thank you very much for yo=
ur
> reply, as I was wondering if my reasoning was making sense! At the very
> beginning I thought I'd need to introduce BInj*INJi in the objective
> function - that is why I stopped due to the introduction of non-linearity=
in
> the objective function.
>
>
>
> I get the hint from your remark on my second question but I really have t=
o
> think about how to implement it. Sorry my background is not in operations
> Research..
>
>
>
> Paolo
>
>
>
>
>
>
> On 4 April 2011 19:23, Kelly, Jeff (ON0F)
> wrote:
>
> Paolo;
>
>
>
> Your first issue of INJi * WITHi =3D 0 complementarity is easily modeled =
by
> adding two binary variables for each quantity i.e., yINJi and yWITHi then
> you need three constraints:
>
> 1. INJi <=3D uINJi * yINJi
>
> 2. WITHi <=3D uWITHi * yWITHi
>
> 3. yINHi + yWITHi =3D 1 or <=3D 1
>
> 4. yINJi, yWITHi are binary
>
> The first two constraints are semi-continuous and third is a SOS1/GUB whe=
re
> the =93u=94 prefix is the upper bound on the quantities. A lower bound i=
s an
> exercise for you.
>
>
>
> Your second issue requires piecewise linear approximation of the cost
> curves due to most likely economizes/diseconomies-of-scale. You will nee=
d
> to define regions of linearity and create extra binary variables for thes=
e
> regions with either SOS1 or SOS2 constraints depending on how you impleme=
nt
> the =93separable programming=94 aspects.
>
>
>
> I hope this helps - Jeff
>
>
>
>
>
> *From:* help-glpk-bounces+jeff.kelly=3Dhoneywell.com@gnu.org [mailto:
> help-glpk-bounces+jeff.kelly=3Dhoneywell.com@gnu.org] *On Behalf Of *Paol=
o
> Rossi
> *Sent:* Monday, April 04, 2011 1:48 PM
> *To:* help-glpk@gnu.org
> *Subject:* [Help-glpk] LP problem with variable coeffcients (parametric
> LPsimplex)
>
>
>
> Hi everyone,
>
>
>
> I am trying to replicate the modelling Byers, 2006. Commodity Storage
> Valuation: A linear optimization based on Traded Instruments, Energy
> Economics. The author is quite concise on how the model has been specifie=
d
> but it says that he used LpSolve
>
>
>
> The paper assesses the value of a gas storage facility. The value is a
> function of:
>
> - Injected quantity: INJ
>
> - Withdrawn quantity: WITH
>
> - Price paid for injections: Pi
>
> - Price paid for withdrawals: Pw
>
> - cost ofinjecting one unit of gas: ci
>
> - cost of withdrawing one unit of gas: cw
>
>
>
> If one takes two periods,
>
>
>
> Max -INJ1 x pi,1 + WITH1 x pw,1 =96 ci,1 x INJ1 =96 cw,1 x =
WITH1
> =96 INJ2 x pi,2 + WITH2 x pw,2 =96 ci,2 x INJ2=96 cw,2 x WITH2
>
>
>
> Constraints
>
> - For each time period i, if INJi > 0 then WITHi =3D 0 and if WI=
THi
> > 0 then INJi =3D 0 - you can either withdraw or inject. I thought of usi=
ng a
> binary variable but then I realised that it would need to multiply INJi a=
nd
> WITHi so I got stuck as it would violate linearity of objective functions
>
> -
>
> - For each time period I, cw,I and ci,I (cost of withdrawing and
> cost of injecting) are a function of the gas stored in the facility. The
> right curve here would be something similar to an exponential function
> through the origin for ci, i.e. the more gas you have in the facility the
> more it costs to push an extra unit of gas in. If one works with strep
> functions, the formulation would be something like
>
> ci =3D 1 if sum of (inj =96 with ) over the periods up to i is
> <=3D 3
>
> 2 if sum of (inj =96 with ) over the periods up to i
> is > 3 and <=3D 6
>
> 3 if sum of (inj =96 with ) over the periods up to i
> is > 6
>
>
>
> For cw, the curve would be symmetric to the one above.
>
> cw =3D 3 if sum of (inj =96 with ) over the periods up to i is
> <=3D 3
>
> 2 if sum of (inj =96 with ) over the periods up to i
> is > 3 and <=3D 6
>
> 1 if sum of (inj =96 with ) over the periods up to i
> is > 6
>
>
>
> I am pretty stuck here so thanks a lot for any help
>
>
>
> Paolo
>
>
>
>
>
>
>
--0016364edfc4b5033704a01e611d
Content-Type: text/html; charset=windows-1252
Content-Transfer-Encoding: quoted-printable
Jeff,
=A0
With your help and some go=
ogling I am now at the next step. I hope so, at least!
=A0
Suppose that my cost funct=
ion depends on a SOS with 4 variables, i.e. 4 regions where I decide to lin=
earise my cost function. When I say cost function I mean a function describ=
ing total cost of production if production falls into that region, not unit=
ary cost of production as I meant in my original post.
=A0
I understand I need 4 mutu=
ally exclusive binary variables, say INVi (inventory)
INV1 + INV2 + INV3 + INV4 =
=3D 1.
=A0
I have been thinking how t=
o model the relationship between the value of the variable switching the bi=
nary INV on and off and the threshold values at which the binaries INV get =
switched on/off. Let=92s call these thresholds T0, T1, T2, T3 and T4 so tha=
t when the switching variable x is between T0 and T1 INV1 gets switched on.=
=A0
if x >=3DT0 and if x &l=
t; T1, INV1 is on, if T1 <=3D x < T2, INV2 etc.
=A0
My constraints would look =
like
x >=3D T0 x INV1, x <=3D T1*INV1
x >=3D T1 x INV2,=A0 x <=3D T2 x INV2
=85
x >=3D T3 x INV4,=A0 x <=3D T4 x INV4
=A0
Do they make sense?=
I actually saw on the net =
that this can be simplified to
T1* INV1 + T2* INV2+ T3* I=
NV3 + T4 * INV4=96 x =3D 0 with x > 0, X being the switching variable
=A0
but it would be nice to kn=
ow if my reasoning makes sense.
=A0
The cost function which go=
es into the objective function is
becomes lc(x1) * INV1 + lc=
(x2) * INV2 + lc(x3) * INV3 + lc(x4) * INV4. So, being pedant, the cost fun=
ction is actually not linearised but approximated by a step function. Is th=
is true?
=A0
So in terms of the objecti=
ve function, max total profits =3D max [ total revenues - total costs] =3D =
max=A0[total revenues - lc(x1) * INV1 + lc(x2) * INV2 + lc(x3) * INV3 + lc(=
x4) * INV4 ].
=A0
If I wanted to use cost pe=
r unit of production, rather than=A0 total cost,=A0I would need to multiply=
an expression similar to lc(x1) * INV1 + lc(x2) * INV2 + lc(x3) * INV3 + l=
c(x4) * INV4=A0(at least in spirit) by the variable x. That would make my p=
roblem non-linear. Is this the reason why it is better to model total costs=
?
=A0=A0
Finally, this works for on=
e time-period only, so if I have=A0N time periods, I need N sets of mutuall=
y exclusive variables so that in each time period ith only one varibale in =
the ith set is on. My cost function becomes Sum with=A0i from 1 to=A0N (lc(=
x1) * INVi1 + lc(xi2) * INVi2 + lc(xi3) * INVi3 + lc(xi4) * INVi4). I am as=
suming the thresholds constants across time periods, which suits me fine.
Is this correct?
=A0
Thanks a lot for your help=
. I am exhausted. I cannot wait to start analysing data instead of doing th=
is type of thinking!
=A0
Thanks again,=A0
Paolo
On 4 April 2011 20:15, Kelly, Jeff (ON0F)
<jeff.kelly@hone=
ywell.com> wrote:
Paol=
o;
=A0<=
/span>
That=
=92s ok, I=92m a chemical engineer.
=A0<=
/span>
Unle=
ss you want to write your own MISLP you will have to linearize your cost pr=
ofiles and then have the binaries select what region or segment the costs s=
hould be in.=A0 It is actually a relatively easy thing to do.
=A0<=
/span>
Jeff=
=A0<=
/span>
From:<=
span style=3D"FONT-SIZE: 10pt"> Paolo Rossi [mailto:statmailinglists@googlemail.c=
om]
Sent: Monday, April 04, 2011 3:10 PM
To: Kelly, Jeff (ON0F=
)
Cc: help=
-glpk@gnu.org
Subject: Re: [Help-glpk] LP problem with variab=
le coeffcients (parametric LPsimplex)
=A0
thanks for that. I had figured it out in the meantim=
e (while cradling my son to sleep!) that the first one could be solved by s=
omething like
With=
i <=3D MaxWith * BWith
whic=
h is I think exactly what you mention. So thank you very much=A0 for your r=
eply, as I was wondering if my reasoning was making sense!=A0At the very be=
ginning I thought I'd need to introduce BInj*INJi in the objective func=
tion - that is why I stopped due to the introduction of non-linearity in th=
e objective function.
I ge=
t the hint from your remark on my second question but=A0I really have to th=
ink about how to implement it. Sorry my background is not in operations Res=
earch..
On 4 April 2011 19:23, Kelly, Jeff (ON0F) <jeff.kelly@honeywel=
l.com> wrote:
Paol=
o;
=A0<=
/span>
Your=
first issue of INJi * WITHi =3D 0 complementarity is easily modeled by add=
ing two binary variables for each quantity i.e., yINJi and yWITHi then you =
need three constraints:
1.=A0=A0=A0=A0=
=A0=A0 INJi <=3D =
uINJi * yINJi
2.=A0=A0=A0=A0=
=A0=A0 WITHi <=3D=
uWITHi * yWITHi
3.=A0=A0=A0=A0=
=A0=A0 yINHi + yWITH=
i =3D 1 or <=3D 1
4.=A0=A0=A0=A0=
=A0=A0 yINJi, yWITHi=
are binary
The =
first two constraints are semi-continuous and third is a SOS1/GUB where the=
=93u=94 prefix is the upper bound on the quantities.=A0 A lower bound is a=
n exercise for you.
=A0<=
/span>
Your=
second issue requires piecewise linear approximation of the cost curves du=
e to most likely economizes/diseconomies-of-scale.=A0 You will need to defi=
ne regions of linearity and create extra binary variables for these regions=
with either SOS1 or SOS2 constraints depending on how you implement the =
=93separable programming=94 aspects.
=A0<=
/span>
I ho=
pe this helps - Jeff
=A0<=
/span>
=A0<=
/span>
=A0
I am trying to replicate the modelling Byers, 2006. =
Commodity Storage Valuation: A linear optimization based on Traded Instrume=
nts, Energy Economics. The author is quite concise on how the model has bee=
n specified but it says that he used LpSolve
=A0
The paper assesses the value of a gas storage facili=
ty. The value is a function of:
-=A0=A0=A0=A0=A0=A0=A0=A0=A0 Injected qua=
ntity: =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=
=A0=A0=A0=A0=A0=A0=A0=A0 INJ
-=A0=A0=A0=A0=A0=A0=A0=A0=A0 =A0Withdrawn=
quantity: =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=
=A0=A0=A0 WITH
-=A0=A0=A0=A0=A0=A0=A0=A0=A0 Price paid f=
or injections: =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 Pi
-=A0=A0=A0=A0=A0=A0=A0=A0=A0 Price paid f=
or withdrawals: =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 Pw
-=A0=A0=A0=A0=A0=A0=A0=A0=A0 cost ofinjec=
ting one unit of gas: =A0=A0=A0=A0=A0=A0=A0 ci
-=A0=A0=A0=A0=A0=A0=A0=A0=A0 cost of with=
drawing one unit of gas: cw
=A0
If one takes two periods,
=A0
Max=A0=A0=A0 -INJ1 x pi,1=A0=A0 +=A0=A0 WITH1 x pw,1=
=A0=A0 =96=A0=A0 ci,1 x INJ1=A0=A0 =96=A0 cw,1 x WITH1=A0 =96=A0=A0 INJ2 x =
pi,2=A0=A0=A0 +=A0=A0 WITH2 x pw,2=A0 =96=A0 ci,2 x INJ2=96 cw,2 x WITH2
=A0
Constraints
-=A0=A0=A0=A0=A0=A0=A0=A0=A0 For each tim=
e period i, if INJi > 0 then WITHi =3D 0 and if WITHi > 0 then INJi =
=3D 0 - you can either withdraw or inject. I thought of using a binary vari=
able but then I realised that it would need to multiply INJi and WITHi so I=
got stuck as it would violate linearity of objective functions
-=A0=A0=A0=A0=A0=A0=A0=A0=A0 =A0
-=A0=A0=A0=A0=A0=A0=A0=A0=A0 For each tim=
e period I, cw,I and ci,I (cost of withdrawing and cost of injecting) are a=
function of the gas stored in the facility.=A0 The right curve here would =
be something similar to an exponential function through the origin for ci, =
i.e. the more gas you have in the facility the more it costs to push an ext=
ra unit of gas in. If one works with strep functions, the formulation would=
be something like
ci =3D=A0 =A0=A0=A0 1=A0 if sum of (inj =96 with ) o=
ver the periods up to i=A0 is=A0=A0=A0=A0=A0=A0=A0=A0 <=3D 3
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 2=A0 if sum =
of (inj =96 with ) over the periods up to i is=A0=A0=A0=A0=A0=A0=A0=A0=A0 &=
gt; 3 and <=3D 6
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 3=A0 if sum =
of (inj =96 with ) over the periods up to i is=A0=A0=A0=A0=A0=A0=A0=A0=A0 &=
gt;=A0 6
=A0
For cw, the curve would be symmetric to the one abov=
e.
cw =3D=A0 =A0=A0 3=A0 if sum of (inj =96 with ) over=
the periods up to i is=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 <=3D 3
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 2=A0 if sum =
of (inj =96 with ) over the periods up to i is=A0=A0=A0=A0=A0=A0=A0=A0=A0=
=A0 > 3 and <=3D 6
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 1=A0 if sum =
of (inj =96 with ) over the periods up to i is=A0=A0=A0=A0=A0=A0=A0=A0=A0 &=
gt;=A0 6
=A0
I am pretty stuck here so thanks a lot for any help<=
/p>
=A0
=A0
--0016364edfc4b5033704a01e611d--
From MAILER-DAEMON Mon Apr 04 17:37:25 2011
Received: from mailman by lists.gnu.org with archive (Exim 4.43)
id 1Q6rSf-00068S-0G
for mharc-help-glpk@gnu.org; Mon, 04 Apr 2011 17:37:25 -0400
Received: from [140.186.70.92] (port=38918 helo=eggs.gnu.org)
by lists.gnu.org with esmtp (Exim 4.43) id 1Q6rSa-00066Z-0K
for help-glpk@gnu.org; Mon, 04 Apr 2011 17:37:23 -0400
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
(envelope-from ) id 1Q6rSX-0002px-PN
for help-glpk@gnu.org; Mon, 04 Apr 2011 17:37:19 -0400
Received: from mail-qy0-f176.google.com ([209.85.216.176]:50445)
by eggs.gnu.org with esmtp (Exim 4.71)
(envelope-from ) id 1Q6rSX-0002pk-Cs
for help-glpk@gnu.org; Mon, 04 Apr 2011 17:37:17 -0400
Received: by qyk30 with SMTP id 30so4797203qyk.0
for ; Mon, 04 Apr 2011 14:37:16 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=googlemail.com; s=gamma;
h=domainkey-signature:mime-version:in-reply-to:references:date
:message-id:subject:from:to:cc:content-type;
bh=BUF2pxLWMIU5njF6Tao5pmpV3npzshIw4QCs5KfrYPQ=;
b=cyUq8WBRdMvN0Y6mC/7ad4g4l5Sm2xJE/uW8AaB3Y2bJNShOgvkchqFBMJsqB2UU37
vWZ2fVkO1Rt202SsAwsXWa5xuTGX0OIo6I/lFFUaJHjuPRgpo5ihpRelbI5JuPdACVqP
PPzDLZ3CRJXZ64VikCn5w571EDaDC786ESDw4=
DomainKey-Signature: a=rsa-sha1; c=nofws; d=googlemail.com; s=gamma;
h=mime-version:in-reply-to:references:date:message-id:subject:from:to
:cc:content-type;
b=xZcKe2v88mZIFPWNWSoVPYhaDRAjM/ii/IAeOPFTW6wnG9nkjhYU2hYjHAxAlwsUZD
Dn4g2KVuQEIWqpCR/23h8+RounLNfUhep0C8VAPDskFB68xAzRS5ZA07l1pxTJ+SFS0Q
L+y/ErLFbB2XMvIZIsxNaKYk4/2l9Ujb80FP4=
MIME-Version: 1.0
Received: by 10.229.141.68 with SMTP id l4mr1136972qcu.136.1301953035296; Mon,
04 Apr 2011 14:37:15 -0700 (PDT)
Received: by 10.229.217.138 with HTTP; Mon, 4 Apr 2011 14:37:15 -0700 (PDT)
In-Reply-To:
References:
<893E047B49F4AC409A76C4E407A3F7DE028ABBCD@DE08EV1001.global.ds.honeywell.com>
<893E047B49F4AC409A76C4E407A3F7DE028ABCE3@DE08EV1001.global.ds.honeywell.com>
Date: Mon, 4 Apr 2011 22:37:15 +0100
Message-ID:
Subject: Re: [Help-glpk] LP problem with variable coeffcients (parametric
LPsimplex)
From: Paolo Rossi
To: "Kelly, Jeff (ON0F)"
Content-Type: multipart/alternative; boundary=90e6ba308c5a2ee20004a01e900f
X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 2)
X-Received-From: 209.85.216.176
Cc: help-glpk@gnu.org
X-BeenThere: help-glpk@gnu.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: "Users list for GLPK \(GNU Linear Programming Kit\)"
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
X-List-Received-Date: Mon, 04 Apr 2011 21:37:23 -0000
--90e6ba308c5a2ee20004a01e900f
Content-Type: text/plain; charset=windows-1252
Content-Transfer-Encoding: quoted-printable
Actually after reading my mail
Sum with i from 1 to N (lc(x1) * INVi1 + lc(xi2) * INVi2 + lc(xi3) * INVi3 =
+
lc(xi4) * INVi4)
should be
Sum with i from 1 to N (lc(T1) * INVi1 + lc(T2) * INVi2 + lc(T3) * INVi3 +
lc(T4) * INVi4).
where Ts are the thresholds which don't change across time, hence no need t=
o
add the i as an index
lc stays for linearised cost.
Paolo
On 4 April 2011 22:24, Paolo Rossi wrote:
> Jeff,
>
>
> With your help and some googling I am now at the next step. I hope so, at
> least!
>
>
>
> Suppose that my cost function depends on a SOS with 4 variables, i.e. 4
> regions where I decide to linearise my cost function. When I say cost
> function I mean a function describing total cost of production if product=
ion
> falls into that region, not unitary cost of production as I meant in my
> original post.
>
>
>
> I understand I need 4 mutually exclusive binary variables, say INVi
> (inventory)
>
> INV1 + INV2 + INV3 + INV4 =3D 1.
>
>
>
> I have been thinking how to model the relationship between the value of t=
he
> variable switching the binary INV on and off and the threshold values at
> which the binaries INV get switched on/off. Let=92s call these thresholds=
T0,
> T1, T2, T3 and T4 so that when the switching variable x is between T0 and=
T1
> INV1 gets switched on.
>
>
>
> if x >=3DT0 and if x < T1, INV1 is on, if T1 <=3D x < T2, INV2 etc.
>
>
>
> My constraints would look like
>
> x >=3D T0 x INV1, x <=3D T1*INV1
>
> x >=3D T1 x INV2, x <=3D T2 x INV2
>
> =85
>
> x >=3D T3 x INV4, x <=3D T4 x INV4
>
>
>
> Do they make sense?
>
> I actually saw on the net that this can be simplified to
>
> T1* INV1 + T2* INV2+ T3* INV3 + T4 * INV4=96 x =3D 0 with x > 0, X being =
the
> switching variable
>
>
>
> but it would be nice to know if my reasoning makes sense.
>
>
>
> The cost function which goes into the objective function is
>
> becomes lc(x1) * INV1 + lc(x2) * INV2 + lc(x3) * INV3 + lc(x4) * INV4. So=
,
> being pedant, the cost function is actually not linearised but approximat=
ed
> by a step function. Is this true?
>
>
>
> So in terms of the objective function, max total profits =3D max [ total
> revenues - total costs] =3D max [total revenues - lc(x1) * INV1 + lc(x2) =
*
> INV2 + lc(x3) * INV3 + lc(x4) * INV4 ].
>
>
>
> If I wanted to use cost per unit of production, rather than total cost, =
I
> would need to multiply an expression similar to lc(x1) * INV1 + lc(x2) *
> INV2 + lc(x3) * INV3 + lc(x4) * INV4 (at least in spirit) by the variable=
x.
> That would make my problem non-linear. Is this the reason why it is bette=
r
> to model total costs?
>
>
>
> Finally, this works for one time-period only, so if I have N time periods=
,
> I need N sets of mutually exclusive variables so that in each time period
> ith only one varibale in the ith set is on. My cost function becomes Sum
> with i from 1 to N (lc(x1) * INVi1 + lc(xi2) * INVi2 + lc(xi3) * INVi3 +
> lc(xi4) * INVi4). I am assuming the thresholds constants across time
> periods, which suits me fine.
>
> Is this correct?
>
>
>
> Thanks a lot for your help. I am exhausted. I cannot wait to start
> analysing data instead of doing this type of thinking!
>
>
>
> Thanks again,
>
> Paolo
>
>
> On 4 April 2011 20:15, Kelly, Jeff (ON0F) wro=
te:
>
>> Paolo;
>>
>>
>>
>> That=92s ok, I=92m a chemical engineer.
>>
>>
>>
>> Unless you want to write your own MISLP you will have to linearize your
>> cost profiles and then have the binaries select what region or segment t=
he
>> costs should be in. It is actually a relatively easy thing to do.
>>
>>
>>
>> Jeff
>>
>>
>>
>> *From:* Paolo Rossi [mailto:statmailinglists@googlemail.com]
>> *Sent:* Monday, April 04, 2011 3:10 PM
>> *To:* Kelly, Jeff (ON0F)
>> *Cc:* help-glpk@gnu.org
>> *Subject:* Re: [Help-glpk] LP problem with variable coeffcients
>> (parametric LPsimplex)
>>
>>
>>
>> Hi Jeff,
>>
>>
>>
>> thanks for that. I had figured it out in the meantime (while cradling my
>> son to sleep!) that the first one could be solved by something like
>>
>>
>>
>> INJi <=3D MaxInj * BInj
>>
>> Withi <=3D MaxWith * BWith
>>
>> BInj + BWith =3D 1
>>
>>
>>
>> which is I think exactly what you mention. So thank you very much for
>> your reply, as I was wondering if my reasoning was making sense! At the =
very
>> beginning I thought I'd need to introduce BInj*INJi in the objective
>> function - that is why I stopped due to the introduction of non-linearit=
y in
>> the objective function.
>>
>>
>>
>> I get the hint from your remark on my second question but I really have =
to
>> think about how to implement it. Sorry my background is not in operation=
s
>> Research..
>>
>>
>>
>> Paolo
>>
>>
>>
>>
>>
>>
>> On 4 April 2011 19:23, Kelly, Jeff (ON0F)
>> wrote:
>>
>> Paolo;
>>
>>
>>
>> Your first issue of INJi * WITHi =3D 0 complementarity is easily modeled=
by
>> adding two binary variables for each quantity i.e., yINJi and yWITHi the=
n
>> you need three constraints:
>>
>> 1. INJi <=3D uINJi * yINJi
>>
>> 2. WITHi <=3D uWITHi * yWITHi
>>
>> 3. yINHi + yWITHi =3D 1 or <=3D 1
>>
>> 4. yINJi, yWITHi are binary
>>
>> The first two constraints are semi-continuous and third is a SOS1/GUB
>> where the =93u=94 prefix is the upper bound on the quantities. A lower =
bound is
>> an exercise for you.
>>
>>
>>
>> Your second issue requires piecewise linear approximation of the cost
>> curves due to most likely economizes/diseconomies-of-scale. You will ne=
ed
>> to define regions of linearity and create extra binary variables for the=
se
>> regions with either SOS1 or SOS2 constraints depending on how you implem=
ent
>> the =93separable programming=94 aspects.
>>
>>
>>
>> I hope this helps - Jeff
>>
>>
>>
>>
>>
>> *From:* help-glpk-bounces+jeff.kelly=3Dhoneywell.com@gnu.org [mailto:
>> help-glpk-bounces+jeff.kelly=3Dhoneywell.com@gnu.org] *On Behalf Of *Pao=
lo
>> Rossi
>> *Sent:* Monday, April 04, 2011 1:48 PM
>> *To:* help-glpk@gnu.org
>> *Subject:* [Help-glpk] LP problem with variable coeffcients (parametric
>> LPsimplex)
>>
>>
>>
>> Hi everyone,
>>
>>
>>
>> I am trying to replicate the modelling Byers, 2006. Commodity Storage
>> Valuation: A linear optimization based on Traded Instruments, Energy
>> Economics. The author is quite concise on how the model has been specifi=
ed
>> but it says that he used LpSolve
>>
>>
>>
>> The paper assesses the value of a gas storage facility. The value is a
>> function of:
>>
>> - Injected quantity: INJ
>>
>> - Withdrawn quantity: WITH
>>
>> - Price paid for injections: Pi
>>
>> - Price paid for withdrawals: Pw
>>
>> - cost ofinjecting one unit of gas: ci
>>
>> - cost of withdrawing one unit of gas: cw
>>
>>
>>
>> If one takes two periods,
>>
>>
>>
>> Max -INJ1 x pi,1 + WITH1 x pw,1 =96 ci,1 x INJ1 =96 cw,1 x
>> WITH1 =96 INJ2 x pi,2 + WITH2 x pw,2 =96 ci,2 x INJ2=96 cw,2 x=
WITH2
>>
>>
>>
>> Constraints
>>
>> - For each time period i, if INJi > 0 then WITHi =3D 0 and if
>> WITHi > 0 then INJi =3D 0 - you can either withdraw or inject. I thought=
of
>> using a binary variable but then I realised that it would need to multip=
ly
>> INJi and WITHi so I got stuck as it would violate linearity of objective
>> functions
>>
>> -
>>
>> - For each time period I, cw,I and ci,I (cost of withdrawing an=
d
>> cost of injecting) are a function of the gas stored in the facility. Th=
e
>> right curve here would be something similar to an exponential function
>> through the origin for ci, i.e. the more gas you have in the facility th=
e
>> more it costs to push an extra unit of gas in. If one works with strep
>> functions, the formulation would be something like
>>
>> ci =3D 1 if sum of (inj =96 with ) over the periods up to i is
>> <=3D 3
>>
>> 2 if sum of (inj =96 with ) over the periods up to i
>> is > 3 and <=3D 6
>>
>> 3 if sum of (inj =96 with ) over the periods up to i
>> is > 6
>>
>>
>>
>> For cw, the curve would be symmetric to the one above.
>>
>> cw =3D 3 if sum of (inj =96 with ) over the periods up to i is
>> <=3D 3
>>
>> 2 if sum of (inj =96 with ) over the periods up to i
>> is > 3 and <=3D 6
>>
>> 1 if sum of (inj =96 with ) over the periods up to i
>> is > 6
>>
>>
>>
>> I am pretty stuck here so thanks a lot for any help
>>
>>
>>
>> Paolo
>>
>>
>>
>>
>>
>>
>>
>
>
--90e6ba308c5a2ee20004a01e900f
Content-Type: text/html; charset=windows-1252
Content-Transfer-Encoding: quoted-printable
Actually after reading my mail
=A0
Sum with i from 1 to N (lc(x1) * INVi1 + lc(xi2) * INVi2 + lc(xi3) * I=
NVi3 + lc(xi4) * INVi4)
should be
Sum with i from 1 to N (lc(T1) * INVi1 + lc(T2) * INVi2 + lc(T3) * INV=
i3 + lc(T4) * INVi4).
=A0
where Ts are the thresholds which don't change across time, hence=
=A0no need to add the i as an index
=A0
lc stays for linearised cost.
=A0
=A0
Paolo
=A0
=A0
On 4 April 2011 22:24, Paolo Rossi
<statmailinglist=
s@googlemail.com> wrote:
Jeff,
=A0
With your hel=
p and some googling I am now at the next step. I hope so, at least!<=
/span>
=A0
Suppose that =
my cost function depends on a SOS with 4 variables, i.e. 4 regions where I =
decide to linearise my cost function. When I say cost function I mean a fun=
ction describing total cost of production if production falls into that reg=
ion, not unitary cost of production as I meant in my original post.<=
/span>
=A0
I understand =
I need 4 mutually exclusive binary variables, say INVi (inventory)
INV1 + INV2 +=
INV3 + INV4 =3D 1.
=A0
I have been t=
hinking how to model the relationship between the value of the variable swi=
tching the binary INV on and off and the threshold values at which the bina=
ries INV get switched on/off. Let=92s call these thresholds T0, T1, T2, T3 =
and T4 so that when the switching variable x is between T0 and T1 INV1 gets=
switched on.
=A0
if x >=3DT=
0 and if x < T1, INV1 is on, if T1 <=3D x < T2, INV2 etc.
=A0
My constraint=
s would look like
x >=3D T0 =
x INV1, x <=3D T1*INV1
x >=3D T1 =
x INV2,=A0 x <=3D T2 x INV2
=85
x >=3D T3 =
x INV4,=A0 x <=3D T4 x INV4
=A0
Do they make =
sense?
I actually sa=
w on the net that this can be simplified to
T1* INV1 + T2=
* INV2+ T3* INV3 + T4 * INV4=96 x =3D 0 with x > 0, X being the switchin=
g variable
=A0
but it would =
be nice to know if my reasoning makes sense.
=A0
The cost func=
tion which goes into the objective function is
becomes lc(x1=
) * INV1 + lc(x2) * INV2 + lc(x3) * INV3 + lc(x4) * INV4. So, being pedant,=
the cost function is actually not linearised but approximated by a step fu=
nction. Is this true?
=A0
So in terms o=
f the objective function, max total profits =3D max [ total revenues - tota=
l costs] =3D max=A0[total revenues - lc(x1) * INV1 + lc(x2) * INV2 + lc(x3)=
* INV3 + lc(x4) * INV4 ].
=A0
If I wanted t=
o use cost per unit of production, rather than=A0 total cost,=A0I would nee=
d to multiply an expression similar to lc(x1) * INV1 + lc(x2) * INV2 + lc(x=
3) * INV3 + lc(x4) * INV4=A0(at least in spirit) by the variable x. That wo=
uld make my problem non-linear. Is this the reason why it is better to mode=
l total costs?
=A0=A0
Finally, this=
works for one time-period only, so if I have=A0N time periods, I need N se=
ts of mutually exclusive variables so that in each time period ith only one=
varibale in the ith set is on. My cost function becomes Sum with=A0i from =
1 to=A0N (lc(x1) * INVi1 + lc(xi2) * INVi2 + lc(xi3) * INVi3 + lc(xi4) * IN=
Vi4). I am assuming the thresholds constants across time periods, which sui=
ts me fine.
Is this corre=
ct?
=A0
Thanks a lot =
for your help. I am exhausted. I cannot wait to start analysing data instea=
d of doing this type of thinking!
=A0
Thanks again,=
=A0
Paolo<=
/span>
On 4 April 2011 20:15, Kelly, Jeff (ON0F)
<jeff.kelly@honeywell.com> wrote:
Paol=
o;
=A0<=
/span>
That=
=92s ok, I=92m a chemical engineer.
=A0<=
/span>
Unle=
ss you want to write your own MISLP you will have to linearize your cost pr=
ofiles and then have the binaries select what region or segment the costs s=
hould be in.=A0 It is actually a relatively easy thing to do.
=A0<=
/span>
Jeff=
=A0<=
/span>
From:<=
span style=3D"FONT-SIZE: 10pt"> Paolo Rossi [mailto:statmailinglists@googlemail.c=
om]
Sent: Monday, April 04, 2011 3:10 PM
To: Kelly, Jeff (ON0F=
)
Cc: help=
-glpk@gnu.org
Subject: Re: [Help-glpk] LP problem with variab=
le coeffcients (parametric LPsimplex)
=A0
thanks for that. I had figured it out in the meantim=
e (while cradling my son to sleep!) that the first one could be solved by s=
omething like
With=
i <=3D MaxWith * BWith
whic=
h is I think exactly what you mention. So thank you very much=A0 for your r=
eply, as I was wondering if my reasoning was making sense!=A0At the very be=
ginning I thought I'd need to introduce BInj*INJi in the objective func=
tion - that is why I stopped due to the introduction of non-linearity in th=
e objective function.
I ge=
t the hint from your remark on my second question but=A0I really have to th=
ink about how to implement it. Sorry my background is not in operations Res=
earch..
On 4 April 2011 19:23, Kelly, Jeff (ON0F) <jeff.kelly@honeywel=
l.com> wrote:
Paol=
o;
=A0<=
/span>
Your=
first issue of INJi * WITHi =3D 0 complementarity is easily modeled by add=
ing two binary variables for each quantity i.e., yINJi and yWITHi then you =
need three constraints:
1.=A0=A0=A0=A0=
=A0=A0 INJi <=3D =
uINJi * yINJi
2.=A0=A0=A0=A0=
=A0=A0 WITHi <=3D=
uWITHi * yWITHi
3.=A0=A0=A0=A0=
=A0=A0 yINHi + yWITH=
i =3D 1 or <=3D 1
4.=A0=A0=A0=A0=
=A0=A0 yINJi, yWITHi=
are binary
The =
first two constraints are semi-continuous and third is a SOS1/GUB where the=
=93u=94 prefix is the upper bound on the quantities.=A0 A lower bound is a=
n exercise for you.
=A0<=
/span>
Your=
second issue requires piecewise linear approximation of the cost curves du=
e to most likely economizes/diseconomies-of-scale.=A0 You will need to defi=
ne regions of linearity and create extra binary variables for these regions=
with either SOS1 or SOS2 constraints depending on how you implement the =
=93separable programming=94 aspects.
=A0<=
/span>
I ho=
pe this helps - Jeff
=A0<=
/span>
=A0<=
/span>
=A0
I am trying to replicate the modelling Byers, 2006. =
Commodity Storage Valuation: A linear optimization based on Traded Instrume=
nts, Energy Economics. The author is quite concise on how the model has bee=
n specified but it says that he used LpSolve
=A0
The paper assesses the value of a gas storage facili=
ty. The value is a function of:
-=A0=A0=A0=A0=A0=A0=A0=A0=A0 Injected qua=
ntity: =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=
=A0=A0=A0=A0=A0=A0=A0=A0 INJ
-=A0=A0=A0=A0=A0=A0=A0=A0=A0 =A0Withdrawn=
quantity: =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=
=A0=A0=A0 WITH
-=A0=A0=A0=A0=A0=A0=A0=A0=A0 Price paid f=
or injections: =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 Pi
-=A0=A0=A0=A0=A0=A0=A0=A0=A0 Price paid f=
or withdrawals: =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 Pw
-=A0=A0=A0=A0=A0=A0=A0=A0=A0 cost ofinjec=
ting one unit of gas: =A0=A0=A0=A0=A0=A0=A0 ci
-=A0=A0=A0=A0=A0=A0=A0=A0=A0 cost of with=
drawing one unit of gas: cw
=A0
If one takes two periods,
=A0
Max=A0=A0=A0 -INJ1 x pi,1=A0=A0 +=A0=A0 WITH1 x pw,1=
=A0=A0 =96=A0=A0 ci,1 x INJ1=A0=A0 =96=A0 cw,1 x WITH1=A0 =96=A0=A0 INJ2 x =
pi,2=A0=A0=A0 +=A0=A0 WITH2 x pw,2=A0 =96=A0 ci,2 x INJ2=96 cw,2 x WITH2
=A0
Constraints
-=A0=A0=A0=A0=A0=A0=A0=A0=A0 For each tim=
e period i, if INJi > 0 then WITHi =3D 0 and if WITHi > 0 then INJi =
=3D 0 - you can either withdraw or inject. I thought of using a binary vari=
able but then I realised that it would need to multiply INJi and WITHi so I=
got stuck as it would violate linearity of objective functions
-=A0=A0=A0=A0=A0=A0=A0=A0=A0 =A0
-=A0=A0=A0=A0=A0=A0=A0=A0=A0 For each tim=
e period I, cw,I and ci,I (cost of withdrawing and cost of injecting) are a=
function of the gas stored in the facility.=A0 The right curve here would =
be something similar to an exponential function through the origin for ci, =
i.e. the more gas you have in the facility the more it costs to push an ext=
ra unit of gas in. If one works with strep functions, the formulation would=
be something like
ci =3D=A0 =A0=A0=A0 1=A0 if sum of (inj =96 with ) o=
ver the periods up to i=A0 is=A0=A0=A0=A0=A0=A0=A0=A0 <=3D 3
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 2=A0 if sum =
of (inj =96 with ) over the periods up to i is=A0=A0=A0=A0=A0=A0=A0=A0=A0 &=
gt; 3 and <=3D 6
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 3=A0 if sum =
of (inj =96 with ) over the periods up to i is=A0=A0=A0=A0=A0=A0=A0=A0=A0 &=
gt;=A0 6
=A0
For cw, the curve would be symmetric to the one abov=
e.
cw =3D=A0 =A0=A0 3=A0 if sum of (inj =96 with ) over=
the periods up to i is=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 <=3D 3
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 2=A0 if sum =
of (inj =96 with ) over the periods up to i is=A0=A0=A0=A0=A0=A0=A0=A0=A0=
=A0 > 3 and <=3D 6
=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 1=A0 if sum =
of (inj =96 with ) over the periods up to i is=A0=A0=A0=A0=A0=A0=A0=A0=A0 &=
gt;=A0 6
=A0
I am pretty stuck here so thanks a lot for any help<=
/p>
=A0
=A0
--90e6ba308c5a2ee20004a01e900f--
From MAILER-DAEMON Tue Apr 05 08:03:08 2011
Received: from mailman by lists.gnu.org with archive (Exim 4.43)
id 1Q74yS-0008Cy-9g
for mharc-help-glpk@gnu.org; Tue, 05 Apr 2011 08:03:08 -0400
Received: from [140.186.70.92] (port=58535 helo=eggs.gnu.org)
by lists.gnu.org with esmtp (Exim 4.43) id 1Q74yO-0008CS-UG
for help-glpk@gnu.org; Tue, 05 Apr 2011 08:03:07 -0400
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
(envelope-from ) id 1Q74yN-0002DH-KD
for help-glpk@gnu.org; Tue, 05 Apr 2011 08:03:04 -0400
Received: from out3.smtp.messagingengine.com ([66.111.4.27]:57479)
by eggs.gnu.org with esmtp (Exim 4.71)
(envelope-from ) id 1Q74yN-0002As-EC
for help-glpk@gnu.org; Tue, 05 Apr 2011 08:03:03 -0400
Received: from compute3.internal (compute3.nyi.mail.srv.osa [10.202.2.43])
by gateway1.messagingengine.com (Postfix) with ESMTP id 21CBC20F17;
Tue, 5 Apr 2011 08:03:01 -0400 (EDT)
Received: from web2.messagingengine.com ([10.202.2.212])
by compute3.internal (MEProxy); Tue, 05 Apr 2011 08:03:01 -0400
DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=messagingengine.com;
h=message-id:from:to:mime-version:content-transfer-encoding:content-type:subject:date;
s=smtpout; bh=7YkYwF68Fwt5bsJaGu03QK69aqQ=;
b=nCB+DdvTAt/t0GT1nS4oZNMofGeyRxZrq9hFeKAosMiR0pbKMLxfCU0q0kcCxzgYSXSH85A+8zEIyQG37nm5L8vMrz88QtbuQ2GnQrJAXLGjItiWkvx1H+SaNndU2H67+Yi8c6pBfs2+rXRmXIU2j/ZOpLqNjy+oBnPpk0JrJQg=
Received: by web2.messagingengine.com (Postfix, from userid 99)
id ECFC53459B4; Tue, 5 Apr 2011 08:03:00 -0400 (EDT)
Message-Id: <1302004980.25774.1437633533@webmail.messagingengine.com>
X-Sasl-Enc: JMS1BABuFvnSiqrxk+lhPKH/xYvjJZqqOQpJsAI28sIF 1302004980
From: "Nigel Galloway"
To: "help-glpk" , "Noli Sicad" , "glpk
xypron"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Type: text/plain; charset="us-ascii"
X-Mailer: MessagingEngine.com Webmail Interface
Date: Tue, 05 Apr 2011 05:03:00 -0700
X-detected-operating-system: by eggs.gnu.org: Genre and OS details not
recognized.
X-Received-From: 66.111.4.27
Cc:
Subject: [Help-glpk] Running glpk in Internet Explorer
X-BeenThere: help-glpk@gnu.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: "Users list for GLPK \(GNU Linear Programming Kit\)"
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
X-List-Received-Date: Tue, 05 Apr 2011 12:03:07 -0000
Further to our discussions on extending Safari with glpk I have compiled
a version of KuKu to extend Internet Explorer using glpk to solve. The
software can be downloaded:
https://sourceforge.net/projects/kuku3/files/KuKu3.0.1.7z/download
You will require a version of libglpk.dll which reads gzipped mps files,
you may compile this or a suitable version is:
https://sourceforge.net/projects/iajaarh/files/libglpk/libglpk.dll/download
I would place this in C:\windows\system.
When unzipped KuKu3.0.1.7z should produce a directory C:\KuKu3. Navigate
to C:\KuKu3\iesudoku. Drop the fie iesudoku.xbap (xaml browser
application) onto internet explorer. Allow it to install any .NET
dependancies. Then use it to solve Sudoku problems.
According to WikiPedia:
With the release of .NET Framework 3.5 SP1 which includes an XBAP
extension, they also run in Mozilla Firefox.
But this is for further study.
--
Nigel Galloway
nigel_galloway@operamail.com
--
http://www.fastmail.fm - Send your email first class
From MAILER-DAEMON Tue Apr 05 17:26:53 2011
Received: from mailman by lists.gnu.org with archive (Exim 4.43)
id 1Q7Dm1-0005R8-L0
for mharc-help-glpk@gnu.org; Tue, 05 Apr 2011 17:26:53 -0400
Received: from [140.186.70.92] (port=39172 helo=eggs.gnu.org)
by lists.gnu.org with esmtp (Exim 4.43) id 1Q7Dlz-0005QJ-I1
for help-glpk@gnu.org; Tue, 05 Apr 2011 17:26:52 -0400
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
(envelope-from ) id 1Q7Dly-000350-AA
for help-glpk@gnu.org; Tue, 05 Apr 2011 17:26:51 -0400
Received: from mowmgw02.mow.com ([79.141.33.246]:51642)
by eggs.gnu.org with esmtp (Exim 4.71)
(envelope-from ) id 1Q7Dly-000343-0c
for help-glpk@gnu.org; Tue, 05 Apr 2011 17:26:50 -0400
X-IronPort-AV: E=Sophos;i="4.63,306,1299456000";
d="scan'208,217";a="338189956"
Received: from unknown (HELO owgusdfwhub01.owg.ds.corp) ([10.23.60.54])
by mowmgw02.mow.com with ESMTP/TLS/RC4-MD5; 05 Apr 2011 22:23:31 +0100
Received: from OWGUSDFWMBX03.owg.ds.corp ([10.23.60.10]) by
owgusdfwhub01.owg.ds.corp ([10.23.60.54]) with mapi;
Tue, 5 Apr 2011 16:26:43 -0500
From: "Meketon, Marc"
To: "help-glpk@gnu.org"
Date: Tue, 5 Apr 2011 16:26:36 -0500
Thread-Topic: DIMACS, mincost and GLPSOL
Thread-Index: Acvz2CTzhglSe1KuTiO+9pDuQ3GGww==
Message-ID: <04B026E012A010408111AFE9C67000A122FDF79321@owgusdfwmbx03>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
acceptlanguage: en-US
Content-Type: multipart/alternative;
boundary="_000_04B026E012A010408111AFE9C67000A122FDF79321owgusdfwmbx03_"
MIME-Version: 1.0
X-detected-operating-system: by eggs.gnu.org: Genre and OS details not
recognized.
X-Received-From: 79.141.33.246
Subject: [Help-glpk] DIMACS, mincost and GLPSOL
X-BeenThere: help-glpk@gnu.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: "Users list for GLPK \(GNU Linear Programming Kit\)"
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
X-List-Received-Date: Tue, 05 Apr 2011 21:26:52 -0000
--_000_04B026E012A010408111AFE9C67000A122FDF79321owgusdfwmbx03_
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
I am trying to run an assignment problem. I created the DIMACS "mincost" f=
ile, I used the "glpsol --mincost filename" option. Everything runs, but I=
'm not sure if it's using the out-of-kilter algorithm or the Simplex. It k=
inda seems like the simplex, see below for the first few lines and last few=
lines. If it is using the Simplex, does GLPSOL have an option for call th=
e out-of-kilter method? I couldn't find it in the documentation.
GLPSOL: GLPK LP/MIP Solver, v4.45
Parameter(s) specified in the command line:
--mincost aa.lp --log log.txt --output out.txt --write solution.txt
Reading min-cost flow problem data from `aa.lp'...
Flow network has 30490 nodes and 3257988 arcs
3288479 lines were read
GLPK Simplex Optimizer, v4.45
30490 rows, 3257988 columns, 6515976 non-zeros
Preprocessing...
19360 rows, 3252321 columns, 6504642 non-zeros
Scaling...
A: min|aij| =3D 1.000e+000 max|aij| =3D 1.000e+000 ratio =3D 1.000e+000
Problem data seem to be well scaled
Constructing initial basis...
Size of triangular part =3D 19346
0: obj =3D 1.208490761e+009 infeas =3D 1.828e+004 (14)
500: obj =3D 1.181597022e+009 infeas =3D 1.653e+004 (13)
...
*269500: obj =3D 6.601862690e+008 infeas =3D 0.000e+000 (3)
*269719: obj =3D 6.601862010e+008 infeas =3D 0.000e+000 (3)
OPTIMAL SOLUTION FOUND
Time used: 10526.6 secs
Memory used: 2543.0 Mb (2666503012 bytes)
Writing basic solution to `out.txt'...
Writing basic solution to `solution.txt'...
3288480 lines were written
________________________________
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, yo=
u should destroy the e-mail message and any attachments or copies, and you =
are prohibited from retaining, distributing, disclosing or using any inform=
ation contained herein. Please inform us of the erroneous delivery by retur=
n e-mail. Thank you for your cooperation.
--_000_04B026E012A010408111AFE9C67000A122FDF79321owgusdfwmbx03_
Content-Type: text/html; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
I a=
m trying to run an assignment problem. I created the DIMACS "min=
cost" file, I used the "glpsol --mincost filename" option.&n=
bsp; Everything runs, but I'm not sure if it's using the out-of-kilter
algorithm or the Simplex. It kinda seems like the simplex, see below=
for the first few lines and last few lines. If it is using the =
Simplex, does GLPSOL have an option for call the out-of-kilter method? =
; I couldn't find it in the documentation.
GLPSOL: GLPK LP/MIP Solver, v4.45
Parameter(s) specified in the command line:
--mincost aa.lp --log log.txt --output out.txt --write solution.txt
Reading min-cost flow problem data from `aa.lp'...
Flow network has 30490 nodes and 3257988 arcs
3288479 lines were read
GLPK Simplex Optimizer, v4.45
30490 rows, 3257988 columns, 6515976 non-zeros
Preprocessing...
19360 rows, 3252321 columns, 6504642 non-zeros
Scaling...
A: min|aij| =3D 1.000e+000 max|aij| =3D 1.000e+000 =
; ratio =3D 1.000e+000
Problem data seem to be well scaled
Constructing initial basis...
Size of triangular part =3D 19346
0: obj =3D 1.208490761e+009 =
infeas =3D 1.828e+004 (14)
500: obj =3D 1.181597022e+009 infeas =3D=
1.653e+004 (13)
...
*269500: obj =3D 6.601862690e+008 infeas =3D 0.000e+=
000 (3)
*269719: obj =3D 6.601862010e+008 infeas =3D 0.000e+000=
(3)
OPTIMAL SOLUTION FOUND
Time used: 10526.6 secs
Memory used: 2543.0 Mb (2666503012 bytes)
Writing basic solution to `out.txt'...
Writing basic solution to `solution.txt'...
3288480 lines were written
This e-mail and any attachme=
nts 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 a=
ny information contained herein. Please inform us of the erroneous delivery=
by return e-mail. Thank you for your cooperation.
--_000_04B026E012A010408111AFE9C67000A122FDF79321owgusdfwmbx03_--
From MAILER-DAEMON Tue Apr 05 18:10:06 2011
Received: from mailman by lists.gnu.org with archive (Exim 4.43)
id 1Q7ERq-0006fP-MV
for mharc-help-glpk@gnu.org; Tue, 05 Apr 2011 18:10:06 -0400
Received: from [140.186.70.92] (port=35414 helo=eggs.gnu.org)
by lists.gnu.org with esmtp (Exim 4.43) id 1Q7ERn-0006ew-Vu
for help-glpk@gnu.org; Tue, 05 Apr 2011 18:10:04 -0400
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
(envelope-from ) id 1Q7ERm-0001Jv-SX
for help-glpk@gnu.org; Tue, 05 Apr 2011 18:10:03 -0400
Received: from fencepost.gnu.org ([140.186.70.10]:53531)
by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from )
id 1Q7ERm-0001Jr-Lh
for help-glpk@gnu.org; Tue, 05 Apr 2011 18:10:02 -0400
Received: from ppp91-78-239-80.pppoe.mtu-net.ru ([91.78.239.80]:25292
helo=[192.168.1.34])
by fencepost.gnu.org with esmtpsa (TLS1.0:RSA_ARCFOUR_MD5:16)
(Exim 4.71) (envelope-from )
id 1Q7ERl-0007dH-B9; Tue, 05 Apr 2011 18:10:01 -0400
Subject: Re: [Help-glpk] DIMACS, mincost and GLPSOL
From: Andrew Makhorin
To: "Meketon, Marc"
In-Reply-To: <04B026E012A010408111AFE9C67000A122FDF79321@owgusdfwmbx03>
References: <04B026E012A010408111AFE9C67000A122FDF79321@owgusdfwmbx03>
Content-Type: text/plain
Date: Wed, 06 Apr 2011 02:10:16 +0400
Message-Id: <1302041416.8187.11.camel@corvax>
Mime-Version: 1.0
X-Mailer: Evolution 2.6.3
Content-Transfer-Encoding: 7bit
X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 3)
X-Received-From: 140.186.70.10
Cc: "help-glpk@gnu.org"
X-BeenThere: help-glpk@gnu.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: "Users list for GLPK \(GNU Linear Programming Kit\)"
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
X-List-Received-Date: Tue, 05 Apr 2011 22:10:04 -0000
> I am trying to run an assignment problem. I created the DIMACS
> "mincost" file, I used the "glpsol --mincost filename" option.
> Everything runs, but I'm not sure if it's using the out-of-kilter
> algorithm or the Simplex. It kinda seems like the simplex, see below
> for the first few lines and last few lines. If it is using the
> Simplex, does GLPSOL have an option for call the out-of-kilter method?
> I couldn't find it in the documentation.
>
The --mincost option only means that the input data is in dimacs format.
Currently to solve the mincost instance glpsol converts it to LP and
calls the simplex solver, which is not much efficient in this case. To
use the out-of-kilter algorithm you need to write a simple main program,
which calls glp_read_mincost and then glp_mincost_okalg. Please see an
example of such program on page 32 in the document "GLPK: Graph and
Network Routines" included in the distribution (doc/graphs.pdf).
From MAILER-DAEMON Tue Apr 05 18:24:59 2011
Received: from mailman by lists.gnu.org with archive (Exim 4.43)
id 1Q7EgF-0000ar-5Q
for mharc-help-glpk@gnu.org; Tue, 05 Apr 2011 18:24:59 -0400
Received: from [140.186.70.92] (port=53177 helo=eggs.gnu.org)
by lists.gnu.org with esmtp (Exim 4.43) id 1Q7EgD-0000Y5-JN
for help-glpk@gnu.org; Tue, 05 Apr 2011 18:24:58 -0400
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
(envelope-from ) id 1Q7EgC-0004lN-An
for help-glpk@gnu.org; Tue, 05 Apr 2011 18:24:57 -0400
Received: from fencepost.gnu.org ([140.186.70.10]:39544)
by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from )
id 1Q7EgC-0004lJ-8t
for help-glpk@gnu.org; Tue, 05 Apr 2011 18:24:56 -0400
Received: from ppp91-78-239-80.pppoe.mtu-net.ru ([91.78.239.80]:25312
helo=[192.168.1.34])
by fencepost.gnu.org with esmtpsa (TLS1.0:RSA_ARCFOUR_MD5:16)
(Exim 4.71) (envelope-from )
id 1Q7EgB-0008PU-Pe; Tue, 05 Apr 2011 18:24:56 -0400
Subject: Re: [Help-glpk] LP problem with variable coeffcients (parametric
LPsimplex)
From: Andrew Makhorin
To: Paolo Rossi
In-Reply-To:
References:
<893E047B49F4AC409A76C4E407A3F7DE028ABBCD@DE08EV1001.global.ds.honeywell.com>
<893E047B49F4AC409A76C4E407A3F7DE028ABCE3@DE08EV1001.global.ds.honeywell.com>
Content-Type: text/plain
Date: Wed, 06 Apr 2011 02:25:10 +0400
Message-Id: <1302042310.8778.5.camel@corvax>
Mime-Version: 1.0
X-Mailer: Evolution 2.6.3
Content-Transfer-Encoding: 7bit
X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 3)
X-Received-From: 140.186.70.10
Cc: help-glpk@gnu.org
X-BeenThere: help-glpk@gnu.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: "Users list for GLPK \(GNU Linear Programming Kit\)"
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
X-List-Received-Date: Tue, 05 Apr 2011 22:24:58 -0000
> Suppose that my cost function depends on a SOS with 4 variables, i.e.
> 4 regions where I decide to linearise my cost function. When I say
> cost function I mean a function describing total cost of production if
> production falls into that region, not unitary cost of production as I
> meant in my original post.
You may look at the following note:
http://winglpk.sourceforge.net/media/glpk-sos2_02.pdf
which explains how to model non-convex piecewise linear functions and
sos2 constraints with binary variables.
From MAILER-DAEMON Tue Apr 05 20:22:30 2011
Received: from mailman by lists.gnu.org with archive (Exim 4.43)
id 1Q7GVy-0004rh-G6
for mharc-help-glpk@gnu.org; Tue, 05 Apr 2011 20:22:30 -0400
Received: from [140.186.70.92] (port=43061 helo=eggs.gnu.org)
by lists.gnu.org with esmtp (Exim 4.43) id 1Q7GVv-0004qK-OE
for help-glpk@gnu.org; Tue, 05 Apr 2011 20:22:28 -0400
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
(envelope-from ) id 1Q7GVu-0002Qb-Ig
for help-glpk@gnu.org; Tue, 05 Apr 2011 20:22:27 -0400
Received: from mowmgw02.mow.com ([79.141.33.246]:41808)
by eggs.gnu.org with esmtp (Exim 4.71)
(envelope-from )
id 1Q7GVs-0002PR-Sl; Tue, 05 Apr 2011 20:22:25 -0400
X-IronPort-AV: E=Sophos;i="4.63,307,1299456000"; d="scan'208";a="338424256"
Received: from unknown (HELO owgusdfwhub01.owg.ds.corp) ([10.23.60.54])
by mowmgw02.mow.com with ESMTP/TLS/RC4-MD5; 06 Apr 2011 01:19:07 +0100
Received: from OWGUSDFWMBX03.owg.ds.corp ([10.23.60.10]) by
owgusdfwhub01.owg.ds.corp ([10.23.60.54]) with mapi;
Tue, 5 Apr 2011 19:22:20 -0500
From: "Meketon, Marc"
To: "'mao@gnu.org'"
Date: Tue, 5 Apr 2011 19:22:20 -0500
Subject: Re: [Help-glpk] DIMACS, mincost and GLPSOL
Thread-Topic: [Help-glpk] DIMACS, mincost and GLPSOL
Thread-Index: Acvz3kIs0Yqa85VfTueH/Q0zNzVnxgAEm+Zp
Message-ID: <04B026E012A010408111AFE9C67000A122FDEE607A@owgusdfwmbx03>
In-Reply-To: <1302041416.8187.11.camel@corvax>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
acceptlanguage: en-US
Content-Type: text/plain; charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-detected-operating-system: by eggs.gnu.org: Genre and OS details not
recognized.
X-Received-From: 79.141.33.246
Cc: "'help-glpk@gnu.org'"
X-BeenThere: help-glpk@gnu.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: "Users list for GLPK \(GNU Linear Programming Kit\)"
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
X-List-Received-Date: Wed, 06 Apr 2011 00:22:28 -0000
Thanks. I was afraid that you were going to recommend something like that.
----- Original Message -----
From: Andrew Makhorin [mailto:mao@gnu.org]
Sent: Tuesday, April 05, 2011 05:10 PM
To: Meketon, Marc
Cc: help-glpk@gnu.org
Subject: Re: [Help-glpk] DIMACS, mincost and GLPSOL
> I am trying to run an assignment problem. I created the DIMACS
> "mincost" file, I used the "glpsol --mincost filename" option.
> Everything runs, but I'm not sure if it's using the out-of-kilter
> algorithm or the Simplex. It kinda seems like the simplex, see below
> for the first few lines and last few lines. If it is using the
> Simplex, does GLPSOL have an option for call the out-of-kilter method?
> I couldn't find it in the documentation.
>
The --mincost option only means that the input data is in dimacs format.
Currently to solve the mincost instance glpsol converts it to LP and
calls the simplex solver, which is not much efficient in this case. To
use the out-of-kilter algorithm you need to write a simple main program,
which calls glp_read_mincost and then glp_mincost_okalg. Please see an
example of such program on page 32 in the document "GLPK: Graph and
Network Routines" included in the distribution (doc/graphs.pdf).
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, yo=
u should destroy the e-mail message and any attachments or copies, and you =
are prohibited from retaining, distributing, disclosing or using any inform=
ation contained herein. Please inform us of the erroneous delivery by retu=
rn e-mail. Thank you for your cooperation.
From MAILER-DAEMON Wed Apr 06 10:18:19 2011
Received: from mailman by lists.gnu.org with archive (Exim 4.43)
id 1Q7TYp-0007Q3-LM
for mharc-help-glpk@gnu.org; Wed, 06 Apr 2011 10:18:19 -0400
Received: from [140.186.70.92] (port=42380 helo=eggs.gnu.org)
by lists.gnu.org with esmtp (Exim 4.43) id 1Q7TYm-0007Nm-PE
for help-glpk@gnu.org; Wed, 06 Apr 2011 10:18:17 -0400
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
(envelope-from ) id 1Q7TYl-0007KQ-KP
for help-glpk@gnu.org; Wed, 06 Apr 2011 10:18:16 -0400
Received: from mowmgw02.mow.com ([79.141.33.246]:41422)
by eggs.gnu.org with esmtp (Exim 4.71)
(envelope-from )
id 1Q7TYj-0007Jg-Op; Wed, 06 Apr 2011 10:18:14 -0400
X-IronPort-AV: E=Sophos;i="4.63,310,1299456000"; d="scan'208";a="339537566"
Received: from unknown (HELO owgusdfwhub01.owg.ds.corp) ([10.23.60.54])
by mowmgw02.mow.com with ESMTP/TLS/RC4-MD5; 06 Apr 2011 15:14:55 +0100
Received: from OWGUSDFWMBX03.owg.ds.corp ([10.23.60.10]) by
owgusdfwhub01.owg.ds.corp ([10.23.60.54]) with mapi;
Wed, 6 Apr 2011 09:18:10 -0500
From: "Meketon, Marc"
To: "'mao@gnu.org'"
Date: Wed, 6 Apr 2011 09:18:04 -0500
Subject: RE: [Help-glpk] DIMACS, mincost and GLPSOL
Thread-Topic: [Help-glpk] DIMACS, mincost and GLPSOL
Thread-Index: Acvz3kIs0Yqa85VfTueH/Q0zNzVnxgAEm+ZpABitMNA=
Message-ID: <04B026E012A010408111AFE9C67000A122FDF794D1@owgusdfwmbx03>
References: <1302041416.8187.11.camel@corvax>
<04B026E012A010408111AFE9C67000A122FDEE607A@owgusdfwmbx03>
In-Reply-To: <04B026E012A010408111AFE9C67000A122FDEE607A@owgusdfwmbx03>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
acceptlanguage: en-US
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-detected-operating-system: by eggs.gnu.org: Genre and OS details not
recognized.
X-Received-From: 79.141.33.246
Cc: "'help-glpk@gnu.org'"
X-BeenThere: help-glpk@gnu.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: "Users list for GLPK \(GNU Linear Programming Kit\)"
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
X-List-Received-Date: Wed, 06 Apr 2011 14:18:18 -0000
I just suffered through using VS2010 to create the program (haven't done an=
y C/C++ for a long time).
Your example on Page 35 is even better.
Roughly, the out-of-kilter ran about 5 times faster than the simplex for th=
e same problem, and took about 2/3rd's the memory.
-----Original Message-----
From: help-glpk-bounces+marc.meketon=3Doliverwyman.com@gnu.org [mailto:help=
-glpk-bounces+marc.meketon=3Doliverwyman.com@gnu.org] On Behalf Of Meketon,=
Marc
Sent: Tuesday, April 05, 2011 8:22 PM
To: 'mao@gnu.org'
Cc: 'help-glpk@gnu.org'
Subject: Re: [Help-glpk] DIMACS, mincost and GLPSOL
Thanks. I was afraid that you were going to recommend something like that.
----- Original Message -----
From: Andrew Makhorin [mailto:mao@gnu.org]
Sent: Tuesday, April 05, 2011 05:10 PM
To: Meketon, Marc
Cc: help-glpk@gnu.org
Subject: Re: [Help-glpk] DIMACS, mincost and GLPSOL
> I am trying to run an assignment problem. I created the DIMACS
> "mincost" file, I used the "glpsol --mincost filename" option.
> Everything runs, but I'm not sure if it's using the out-of-kilter
> algorithm or the Simplex. It kinda seems like the simplex, see below
> for the first few lines and last few lines. If it is using the
> Simplex, does GLPSOL have an option for call the out-of-kilter method?
> I couldn't find it in the documentation.
>
The --mincost option only means that the input data is in dimacs format.
Currently to solve the mincost instance glpsol converts it to LP and calls =
the simplex solver, which is not much efficient in this case. To use the ou=
t-of-kilter algorithm you need to write a simple main program, which calls =
glp_read_mincost and then glp_mincost_okalg. Please see an example of such =
program on page 32 in the document "GLPK: Graph and Network Routines" inclu=
ded in the distribution (doc/graphs.pdf).
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, yo=
u should destroy the e-mail message and any attachments or copies, and you =
are prohibited from retaining, distributing, disclosing or using any inform=
ation contained herein. Please inform us of the erroneous delivery by retu=
rn e-mail. Thank you for your cooperation.
_______________________________________________
Help-glpk mailing list
Help-glpk@gnu.org
http://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, yo=
u should destroy the e-mail message and any attachments or copies, and you =
are prohibited from retaining, distributing, disclosing or using any inform=
ation contained herein. Please inform us of the erroneous delivery by retu=
rn e-mail. Thank you for your cooperation.
From MAILER-DAEMON Wed Apr 06 11:43:39 2011
Received: from mailman by lists.gnu.org with archive (Exim 4.43)
id 1Q7UtP-0004cv-80
for mharc-help-glpk@gnu.org; Wed, 06 Apr 2011 11:43:39 -0400
Received: from [140.186.70.92] (port=48917 helo=eggs.gnu.org)
by lists.gnu.org with esmtp (Exim 4.43) id 1Q7UtN-0004cp-OA
for help-glpk@gnu.org; Wed, 06 Apr 2011 11:43:38 -0400
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
(envelope-from ) id 1Q7UtM-000260-Lv
for help-glpk@gnu.org; Wed, 06 Apr 2011 11:43:37 -0400
Received: from fencepost.gnu.org ([140.186.70.10]:35549)
by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from )
id 1Q7UtM-00025v-J2
for help-glpk@gnu.org; Wed, 06 Apr 2011 11:43:36 -0400
Received: from ppp91-77-220-126.pppoe.mtu-net.ru ([91.77.220.126]:26091
helo=[192.168.1.34])
by fencepost.gnu.org with esmtpsa (TLS1.0:RSA_ARCFOUR_MD5:16)
(Exim 4.71) (envelope-from )
id 1Q7UtL-0002IJ-6s; Wed, 06 Apr 2011 11:43:35 -0400
Subject: RE: [Help-glpk] DIMACS, mincost and GLPSOL
From: Andrew Makhorin
To: "Meketon, Marc"
In-Reply-To: <04B026E012A010408111AFE9C67000A122FDF794D1@owgusdfwmbx03>
References: <1302041416.8187.11.camel@corvax>
<04B026E012A010408111AFE9C67000A122FDEE607A@owgusdfwmbx03>
<04B026E012A010408111AFE9C67000A122FDF794D1@owgusdfwmbx03>
Content-Type: text/plain
Date: Wed, 06 Apr 2011 19:43:51 +0400
Message-Id: <1302104631.2951.10.camel@corvax>
Mime-Version: 1.0
X-Mailer: Evolution 2.6.3
Content-Transfer-Encoding: 7bit
X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 3)
X-Received-From: 140.186.70.10
Cc: "'help-glpk@gnu.org'"
X-BeenThere: help-glpk@gnu.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: "Users list for GLPK \(GNU Linear Programming Kit\)"
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
X-List-Received-Date: Wed, 06 Apr 2011 15:43:38 -0000
> Your example on Page 35 is even better.
That is what I meant, not that one on p.32. Sorry.
>
> Roughly, the out-of-kilter ran about 5 times faster than the
> simplex for the same problem, and took about 2/3rd's the memory.
I'd like to note that today the out-of-kilter algorithm is not a
best one for solving mincost. For example, RELAX-IV developed by
Prof. Bertsekas is much faster (even faster that the network
simplex). It is free software, so I plan to translate it to C and
include in glpk as a better alternative.
From MAILER-DAEMON Wed Apr 06 16:42:43 2011
Received: from mailman by lists.gnu.org with archive (Exim 4.43)
id 1Q7ZYo-0003nz-Sg
for mharc-help-glpk@gnu.org; Wed, 06 Apr 2011 16:42:42 -0400
Received: from [140.186.70.92] (port=49002 helo=eggs.gnu.org)
by lists.gnu.org with esmtp (Exim 4.43) id 1Q7ZYl-0003Sr-3u
for help-glpk@gnu.org; Wed, 06 Apr 2011 16:42:40 -0400
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
(envelope-from ) id 1Q7ZYH-0001z4-23
for help-glpk@gnu.org; Wed, 06 Apr 2011 16:42:09 -0400
Received: from mowmgw01.mow.com ([69.74.255.162]:15791)
by eggs.gnu.org with esmtp (Exim 4.71)
(envelope-from )
id 1Q7ZYF-0001yV-65; Wed, 06 Apr 2011 16:42:07 -0400
X-IronPort-AV: E=Sophos;i="4.63,312,1299474000"; d="scan'208";a="306687388"
Received: from unknown (HELO owgusdfwhub02.owg.ds.corp) ([10.23.60.59])
by mowmgw01.mow.com with ESMTP/TLS/RC4-MD5; 06 Apr 2011 16:42:41 -0400
Received: from OWGUSDFWMBX03.owg.ds.corp ([10.23.60.10]) by
owgusdfwhub02.owg.ds.corp ([10.23.60.59]) with mapi;
Wed, 6 Apr 2011 15:41:59 -0500
From: "Meketon, Marc"
To: Andrew Makhorin
Date: Wed, 6 Apr 2011 15:41:55 -0500
Subject: RE: [Help-glpk] DIMACS, mincost and GLPSOL
Thread-Topic: [Help-glpk] DIMACS, mincost and GLPSOL
Thread-Index: Acv0cWiMmQ0KJ9CXStmIRrC5V2azRgAKNoCw
Message-ID: <04B026E012A010408111AFE9C67000A122FDF79642@owgusdfwmbx03>
References: <1302041416.8187.11.camel@corvax>
<04B026E012A010408111AFE9C67000A122FDEE607A@owgusdfwmbx03>
<04B026E012A010408111AFE9C67000A122FDF794D1@owgusdfwmbx03>
<1302104631.2951.10.camel@corvax>
In-Reply-To: <1302104631.2951.10.camel@corvax>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
acceptlanguage: en-US
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-detected-operating-system: by eggs.gnu.org: Genre and OS details not
recognized.
X-Received-From: 69.74.255.162
Cc: "'help-glpk@gnu.org'"
X-BeenThere: help-glpk@gnu.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: "Users list for GLPK \(GNU Linear Programming Kit\)"
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
X-List-Received-Date: Wed, 06 Apr 2011 20:42:40 -0000
I had a modified form of Andrew Goldberg's CS2 on my laptop (I bought a lic=
ense many years ago) which supposedly is a better version of RELAX-IV.
My modification had taken out the ability to read DIMACs, but I had some ti=
me to kill in the last hour and reinstalled that ability.
On my problem that took about 30 minutes with the out-of-kilter algorithm i=
n GLPK (and about 170 minutes with the GLPK simplex), CS2 took 7 seconds. =
Whew.
-----Original Message-----
From: Andrew Makhorin [mailto:mao@gnu.org]
Sent: Wednesday, April 06, 2011 11:44 AM
To: Meketon, Marc
Cc: 'help-glpk@gnu.org'
Subject: RE: [Help-glpk] DIMACS, mincost and GLPSOL
> Your example on Page 35 is even better.
That is what I meant, not that one on p.32. Sorry.
>
> Roughly, the out-of-kilter ran about 5 times faster than the simplex
> for the same problem, and took about 2/3rd's the memory.
I'd like to note that today the out-of-kilter algorithm is not a best one f=
or solving mincost. For example, RELAX-IV developed by Prof. Bertsekas is m=
uch faster (even faster that the network simplex). It is free software, so =
I plan to translate it to C and include in glpk as a better alternative.
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, yo=
u should destroy the e-mail message and any attachments or copies, and you =
are prohibited from retaining, distributing, disclosing or using any inform=
ation contained herein. Please inform us of the erroneous delivery by retu=
rn e-mail. Thank you for your cooperation.
From MAILER-DAEMON Wed Apr 06 17:32:00 2011
Received: from mailman by lists.gnu.org with archive (Exim 4.43)
id 1Q7aKW-00084y-Ix
for mharc-help-glpk@gnu.org; Wed, 06 Apr 2011 17:32:00 -0400
Received: from [140.186.70.92] (port=53314 helo=eggs.gnu.org)
by lists.gnu.org with esmtp (Exim 4.43) id 1Q7aKU-000819-B2
for help-glpk@gnu.org; Wed, 06 Apr 2011 17:31:59 -0400
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
(envelope-from ) id 1Q7aKT-00035w-Im
for help-glpk@gnu.org; Wed, 06 Apr 2011 17:31:58 -0400
Received: from fencepost.gnu.org ([140.186.70.10]:44723)
by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from )
id 1Q7aKT-00035s-HU
for help-glpk@gnu.org; Wed, 06 Apr 2011 17:31:57 -0400
Received: from ppp91-77-173-130.pppoe.mtu-net.ru ([91.77.173.130]:14233
helo=[192.168.1.34])
by fencepost.gnu.org with esmtpsa (TLS1.0:RSA_ARCFOUR_MD5:16)
(Exim 4.71) (envelope-from )
id 1Q7aKS-0002v3-84; Wed, 06 Apr 2011 17:31:56 -0400
Subject: RE: [Help-glpk] DIMACS, mincost and GLPSOL
From: Andrew Makhorin
To: "Meketon, Marc"
In-Reply-To: <04B026E012A010408111AFE9C67000A122FDF79642@owgusdfwmbx03>
References: <1302041416.8187.11.camel@corvax>
<04B026E012A010408111AFE9C67000A122FDEE607A@owgusdfwmbx03>
<04B026E012A010408111AFE9C67000A122FDF794D1@owgusdfwmbx03>
<1302104631.2951.10.camel@corvax>
<04B026E012A010408111AFE9C67000A122FDF79642@owgusdfwmbx03>
Content-Type: text/plain
Date: Thu, 07 Apr 2011 01:32:14 +0400
Message-Id: <1302125534.3063.5.camel@corvax>
Mime-Version: 1.0
X-Mailer: Evolution 2.6.3
Content-Transfer-Encoding: 7bit
X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 3)
X-Received-From: 140.186.70.10
Cc: "'help-glpk@gnu.org'"
X-BeenThere: help-glpk@gnu.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: "Users list for GLPK \(GNU Linear Programming Kit\)"