Egerstedt standard problem - Revision history

ChristophHansknecht: Fixed type, error in relaxed objective function value

2019-09-19T15:09:18Z

Fixed type, error in relaxed objective function value

← Older revision		Revision as of 15:09, 19 September 2019
Line 7:		Line 7:
	}}<!-- Do not insert line break here or Dimensions Box moves up in the layout...		}}<!-- Do not insert line break here or Dimensions Box moves up in the layout...

	-->The '''Egerstedt standard ~~problemm~~''' is the problem is of an academic nature and was proposed by Egerestedt to highlight the features of an Hybrid System algorithm in 2006 <bib id="Egerstedt2006" />. It has been used since then in many MIOCP research studies (e.g. <bib id="Jung2013" />) for benchmarking of MIOCP algorithms.		-->The '''Egerstedt standard problem''' is the problem is of an academic nature and was proposed by Egerestedt to highlight the features of an Hybrid System algorithm in 2006 <bib id="Egerstedt2006" />. It has been used since then in many MIOCP research studies (e.g. <bib id="Jung2013" />) for benchmarking of MIOCP algorithms.


Line 35:		Line 35:
	If the problem is relaxed, i.e., we demand that <math>w(t)</math> be in the continuous interval <math>[0, 1]</math> instead of the binary choice <math>\{0,1\}</math>, the optimal solution can be determined by using a direct method such as collocation or Bock's direct multiple shooting method.		If the problem is relaxed, i.e., we demand that <math>w(t)</math> be in the continuous interval <math>[0, 1]</math> instead of the binary choice <math>\{0,1\}</math>, the optimal solution can be determined by using a direct method such as collocation or Bock's direct multiple shooting method.

	The optimal objective value of the relaxed problem with <math> n_t=6000, \, n_u=40 </math> is <math>x_3(t_f)=1.0.995906234</math>. The objective value of the binary controls obtained by Combinatorial Integral Approimation (CIA) is <math>x_3(t_f) =3.20831942</math>. The binary control solution was evaluated in the MIOCP by using a Merit function with additional Lagrange term <math> 100 \max\limits_{t\in[0,1]}\{0,0.4-x_2(t)\} </math>.		The optimal objective value of the relaxed problem with <math> n_t=6000, \, n_u=40 </math> is <math>x_3(t_f)=0.995906234</math>. The objective value of the binary controls obtained by Combinatorial Integral Approimation (CIA) is <math>x_3(t_f) =3.20831942</math>. The binary control solution was evaluated in the MIOCP by using a Merit function with additional Lagrange term <math> 100 \max\limits_{t\in[0,1]}\{0,0.4-x_2(t)\} </math>.

	<gallery caption="Reference solution plots" widths="180px" heights="140px" perrow="2">		<gallery caption="Reference solution plots" widths="180px" heights="140px" perrow="2">

ClemensZeile at 13:30, 10 January 2018

2018-01-10T13:30:32Z

← Older revision		Revision as of 13:30, 10 January 2018
Line 46:		Line 46:
	== Source Code ==		== Source Code ==

	Model ~~descriptions are~~ available in		Model description is available in
	* [[:Category:AMPL \| AMPL code]] at [[~~Lotka Volterra fishing~~ problem (AMPL)]]		* [[:Category:AMPL \| AMPL code]] at [[Egerstedt standard problem (AMPL)]]

ClemensZeile at 13:29, 10 January 2018

2018-01-10T13:29:35Z

← Older revision		Revision as of 13:29, 10 January 2018
Line 38:		Line 38:

	<gallery caption="Reference solution plots" widths="180px" heights="140px" perrow="2">		<gallery caption="Reference solution plots" widths="180px" heights="140px" perrow="2">
	Image:~~MmlotkaRelaxed_12000_30_1~~.png\| Optimal relaxed controls and states determined by an direct approach with ampl_mintoc (Radau collocation) and <math>n_t=~~12000~~, \, n_u=~~400~~</math>.		Image:EgerstedtRelaxed 6000 150 1.png\| Optimal relaxed controls and states determined by an direct approach with ampl_mintoc (Radau collocation) and <math>n_t=6000, \, n_u=40</math>.
	Image:~~MmlotkaCIA 12000 30~~ 1.png\| Optimal binary controls and states determined by an direct approach (Radau collocation) with ampl_mintoc and <math>n_t=~~12000~~, \, n_u=~~400~~</math>. The relaxed controls were approximated by Combinatorial Integral Approximation.		Image:EgerstedtCIA 6000 150 1.png\| Optimal binary controls and states determined by an direct approach (Radau collocation) with ampl_mintoc and <math>n_t=6000, \, n_u=40</math>. The relaxed controls were approximated by Combinatorial Integral Approximation.
	</gallery>		</gallery>

Line 47:		Line 47:

	Model descriptions are available in		Model descriptions are available in

	* [[:Category:ACADO \| ACADO code]] at [[Lotka Volterra fishing problem (ACADO)]]
	* [[:Category:AMPL \| AMPL code]] at [[Lotka Volterra fishing problem (AMPL)]]		* [[:Category:AMPL \| AMPL code]] at [[Lotka Volterra fishing problem (AMPL)]]
	* [[:Category:APMonitor \| APMonitor code]] at [[Lotka Volterra fishing problem (APMonitor)]]
	* [[:Category:Bocop \| Bocop code]] at [[Lotka Volterra fishing problem (Bocop)]]
	* [[:Category:Casadi \| Casadi code]] at [[Lotka Volterra fishing problem (Casadi)]]
	* [[:Category:JModelica \| JModelica code]] at [[Lotka Volterra fishing problem (JModelica)]]
	* [[:Category:Julia/JuMP \| JuMP code]] at [[Lotka Volterra fishing problem (JuMP)]]
	* [[:Category:Muscod \| Muscod code]] at [[Lotka Volterra fishing problem (Muscod)]]
	* [[:Category:switch \| switch code]] at [[Lotka Volterra fishing problem (switch)]]
	* [[:Category:TomDyn/PROPT \| PROPT code]] at [[Lotka Volterra fishing problem (TomDyn/PROPT)]]

	~~== Variants ==~~

	~~There are several alternative formulations and variants of the above problem, in particular~~

	* a prescribed time grid for the control function <bib id="Sager2006" />, see also [[Lotka Volterra fishing problem (AMPL)]],
	* a time-optimal formulation to get into a steady-state <bib id="Sager2005" />,
	* the usage of a different target steady-state, as the one corresponding to <math> w(t) = 1</math> which is <math>(1 + c_1, 1 - c_0)</math>, see [[Lotka Volterra multi-arcs problem]]
	* different fishing control functions for the two species, see [[Lotka Volterra Multimode fishing problem]]
	* different parameters and start values.

	~~== Miscellaneous and Further Reading ==~~
	The Lotka Volterra fishing problem was introduced by Sebastian Sager in a proceedings paper <bib id="Sager2006" /> and revisited in his PhD thesis <bib id="Sager2005" />. These are also the references to look for more details.

	== References ==		== References ==
Line 79:		Line 58:
	[[Category:ODE model]]		[[Category:ODE model]]
	[[Category:Tracking objective]]		[[Category:Tracking objective]]
	~~[[Category:Chattering]]~~
	[[Category:Sensitivity-seeking arcs]]		[[Category:Sensitivity-seeking arcs]]
	~~[[Category:Population dynamics]]~~

ClemensZeile at 13:11, 10 January 2018

2018-01-10T13:11:41Z

← Older revision		Revision as of 13:11, 10 January 2018
Line 28:		Line 28:
	\end{array}		\end{array}
	</math>		</math>
			</p>
	for <math>t \in [t_0, t_f]=[0,1] </math>.		for <math>t \in [t_0, t_f]=[0,1] </math>.
	~~</p>~~

	== Reference Solutions ==		== Reference Solutions ==

	If the problem is relaxed, i.e., we demand that <math>w(t)</math> be in the continuous interval <math>[0, 1]</math> instead of the binary choice <math>\{0,1\}</math>, the optimal solution can be determined by means of [http://en.wikipedia.org/wiki/Pontryagin%27s_minimum_principle Pontryagins maximum principle]. The optimal solution contains a singular arc, as can be seen in the plot of the optimal control. The two differential states and corresponding adjoint variables in the indirect approach are also displayed. A different approach to solving the relaxed problem is by using a direct method such as collocation or Bock's direct multiple shooting method~~. Optimal solutions for different control discretizations are also plotted in the leftmost figure~~.		If the problem is relaxed, i.e., we demand that <math>w(t)</math> be in the continuous interval <math>[0, 1]</math> instead of the binary choice <math>\{0,1\}</math>, the optimal solution can be determined by using a direct method such as collocation or Bock's direct multiple shooting method.

	The optimal objective value of ~~this~~ relaxed problem is <math>~~x_2~~(t_f) = 1.~~34408~~</math>. ~~As follows from MIOC theory <bib id="Sager2011d" /> this is the best lower bound on the optimal~~ value of the original problem with the integer restriction on the control function. In other words, this objective value can be approximated arbitrarily close, if the control only switches often enough between 0 and 1. As no optimal solution exists, two suboptimal ones are shown, one with only two switches and an objective function value of <math>~~x_2~~(t_f) = 1.~~38276~~</math>~~, and one~~ with ~~56 switches and~~ <math>x_2(~~t_f~~) ~~= 1.34416~~</math>.		The optimal objective value of the relaxed problem with <math> n_t=6000, \, n_u=40 </math> is <math>x_3(t_f)=1.0.995906234</math>. The objective value of the binary controls obtained by Combinatorial Integral Approimation (CIA) is <math>x_3(t_f) =3.20831942</math>. The binary control solution was evaluated in the MIOCP by using a Merit function with additional Lagrange term <math> 100 \max\limits_{t\in[0,1]}\{0,0.4-x_2(t)\} </math>.

	<gallery caption="Reference solution plots" widths="180px" heights="140px" perrow="2">		<gallery caption="Reference solution plots" widths="180px" heights="140px" perrow="2">
	Image:~~lotkaRelaxedControls~~.png\| Optimal relaxed ~~control~~ determined by an ~~indirect approach and by a~~ direct approach ~~on different control discretization grids.~~		Image:MmlotkaRelaxed_12000_30_1.png\| Optimal relaxed controls and states determined by an direct approach with ampl_mintoc (Radau collocation) and <math>n_t=12000, \, n_u=400</math>.
	~~Image:lotkaindirektStates.png\| Differential states~~ and ~~corresponding adjoint variables in the indirect approach~~.		Image:MmlotkaCIA 12000 30 1.png\| Optimal binary controls and states determined by an direct approach (Radau collocation) with ampl_mintoc and <math>n_t=12000, \, n_u=400</math>. The relaxed controls were approximated by Combinatorial Integral Approximation.
	Image:~~lotka2Switches~~.png\| ~~Control~~ and ~~differential~~ states with ~~only two switches~~.
	~~Image:lotka56Switches.png\| Control and differential states with 56 switches~~.
	</gallery>		</gallery>

ClemensZeile at 12:20, 10 January 2018

2018-01-10T12:20:46Z

← Older revision		Revision as of 12:20, 10 January 2018
Line 23:		Line 23:
	& \dot{x}_3 & = & x_1^2+x_2^2, \\[1.5ex]		& \dot{x}_3 & = & x_1^2+x_2^2, \\[1.5ex]
	& x(0) &=& (0.5, 0.5, 0)^T, \\		& x(0) &=& (0.5, 0.5, 0)^T, \\
	& x_2(t) & \geq & 0.4,		& x_2(t) & \geq & 0.4, \\
	& 1 &=& \sum\limits_{i=1}^3\omega_i(t), \\		& 1 &=& \sum\limits_{i=1}^3\omega_i(t), \\
	& \omega(t) &\in& \{0, 1\},		& \omega(t) &\in& \{0, 1\},

ClemensZeile: /* Mathematical formulation */

2018-01-10T12:20:14Z

Mathematical formulation

← Older revision		Revision as of 12:20, 10 January 2018
Line 25:		Line 25:
	& x_2(t) & \geq & 0.4,		& x_2(t) & \geq & 0.4,
	& 1 &=& \sum\limits_{i=1}^3\omega_i(t), \\		& 1 &=& \sum\limits_{i=1}^3\omega_i(t), \\
	& \omega(t) &\in& \{0, 1\}, \\		& \omega(t) &\in& \{0, 1\},
	\end{array}		\end{array}
	</math>		</math>
	for <math>t \in [t_0, t_f]=[0,1] </math>.		for <math>t \in [t_0, t_f]=[0,1] </math>.
	</p>		</p>


	== Reference Solutions ==		== Reference Solutions ==

ClemensZeile at 12:19, 10 January 2018

2018-01-10T12:19:55Z

← Older revision		Revision as of 12:19, 10 January 2018
Line 23:		Line 23:
	& \dot{x}_3 & = & x_1^2+x_2^2, \\[1.5ex]		& \dot{x}_3 & = & x_1^2+x_2^2, \\[1.5ex]
	& x(0) &=& (0.5, 0.5, 0)^T, \\		& x(0) &=& (0.5, 0.5, 0)^T, \\
			& x_2(t) & \geq & 0.4,
			& 1 &=& \sum\limits_{i=1}^3\omega_i(t), \\
	& \omega(t) &\in& \{0, 1\}, \\		& \omega(t) &\in& \{0, 1\}, \\
	~~& 1 &=& \sum\limits_{i=1}^3\omega_i(t). \\~~
	\end{array}		\end{array}
	</math>		</math>
			for <math>t \in [t_0, t_f]=[0,1] </math>.
	</p>		</p>

	~~== Parameters ==~~

	~~These fixed values are used within the model.~~

	~~<math>~~
	~~\begin{array}{rcl}~~
	~~[t_0, t_f] &=& [0, 12],\\~~
	~~(c_0, c_1) &=& (0.4, 0.2).~~
	~~\end{array}~~
	~~</math>~~

	== Reference Solutions ==		== Reference Solutions ==

ClemensZeile at 12:14, 10 January 2018

2018-01-10T12:14:13Z

← Older revision		Revision as of 12:14, 10 January 2018
Line 23:		Line 23:
	& \dot{x}_3 & = & x_1^2+x_2^2, \\[1.5ex]		& \dot{x}_3 & = & x_1^2+x_2^2, \\[1.5ex]
	& x(0) &=& (0.5, 0.5, 0)^T, \\		& x(0) &=& (0.5, 0.5, 0)^T, \\
	& \omega(t) &\in& \{0, 1\},		& \omega(t) &\in& \{0, 1\}, \\
	& 1 &=& \sum\limits_{i=1}^3\omega_i(t). \\		& 1 &=& \sum\limits_{i=1}^3\omega_i(t). \\
	\end{array}		\end{array}

ClemensZeile at 12:13, 10 January 2018

2018-01-10T12:13:32Z

← Older revision		Revision as of 12:13, 10 January 2018
Line 7:		Line 7:
	}}<!-- Do not insert line break here or Dimensions Box moves up in the layout...		}}<!-- Do not insert line break here or Dimensions Box moves up in the layout...

	-->The '''Egerstedt standard problemm''' is the problem is of an academic nature and was proposed by Egerestedt to highlight the features of an Hybrid System algorithm in 2006 <bib id="Egerstedt2006" />. It has been used since then in many MIOCP research studies (e.g. <bib id="Jung2013" /> for benchmarking of MIOCP algorithms.		-->The '''Egerstedt standard problemm''' is the problem is of an academic nature and was proposed by Egerestedt to highlight the features of an Hybrid System algorithm in 2006 <bib id="Egerstedt2006" />. It has been used since then in many MIOCP research studies (e.g. <bib id="Jung2013" />) for benchmarking of MIOCP algorithms.


	== Mathematical formulation ==		== Mathematical formulation ==

	The mixed-integer optimal control problem is given by		The mixed-integer optimal control problem after partial outer convexification is given by

	<p>		<p>
	<math>		<math>
	\begin{array}{llclr}		\begin{array}{llclr}
	\displaystyle \min_{x, w} & ~~x_2~~(t_f) \\[1.5ex]		\displaystyle \min_{x, \omega} & x_3(t_f) \\[1.5ex]
	\mbox{s.t.}		\mbox{s.t.}
	& \dot{x}_0 & = & ~~x_0~~ - ~~x_0~~ x_1 - \~~; c_0 x_0 \; w~~, \\		& \dot{x}_1 & = & -x_1\omega_1 + (x_1+x_2)\omega_2+(x_1-x_2)\omega_3, \\
	& \dot{x}_1 & = & - x_1 + ~~x_0~~ x_1 - \~~; c_1~~ x_1 \~~; w~~, \\		& \dot{x}_2 & = & (x_1+2x_2)\omega_1+(x_1-2x_2)\omega_2+(x_1+x_2)\omega_3, \\
	& \dot{x}_2 & = & ~~(x_0 - 1)~~^2 + ~~(x_1 - 1)~~^2, \\[1.5ex]		& \dot{x}_3 & = & x_1^2+x_2^2, \\[1.5ex]
	& x(0) &=& (0.5, 0.7, 0)^T, \\		& x(0) &=& (0.5, 0.5, 0)^T, \\
	& w(t) &\in& \{0, 1\}.		& \omega(t) &\in& \{0, 1\},
			& 1 &=& \sum\limits_{i=1}^3\omega_i(t). \\
	\end{array}		\end{array}
	</math>		</math>
	</p>		</p>

	Here the differential states <math>(x_0, x_1)</math> describe the biomasses of prey and predator, respectively. The third differential state is used here to transform the objective, an integrated deviation, into the Mayer formulation <math>\min \; x_2(t_f)</math>. The decision, whether the fishing fleet is actually fishing at time <math>t</math> is denoted by <math>w(t)</math>.

	== Parameters ==		== Parameters ==

ClemensZeile: Created page with "{{Dimensions |nd = 1 |nx = 3 |nw = 3 |nc = 1 |nre = 3 }}Th..."

2018-01-10T12:04:30Z

Created page with "{{Dimensions |nd = 1 |nx = 3 |nw = 3 |nc = 1 |nre = 3 }}Th..."

New page

{{Dimensions
|nd = 1
|nx = 3
|nw = 3
|nc = 1
|nre = 3
}}The '''Egerstedt standard problemm''' is the problem is of an academic nature and was proposed by Egerestedt to highlight the features of an Hybrid System algorithm in 2006 <bib id="Egerstedt2006" />. It has been used since then in many MIOCP research studies (e.g. <bib id="Jung2013" /> for benchmarking of MIOCP algorithms.

== Mathematical formulation ==

The mixed-integer optimal control problem is given by

<p>
<math>
\begin{array}{llclr}
\displaystyle \min_{x, w} & x_2(t_f) \\[1.5ex]
\mbox{s.t.}
& \dot{x}_0 & = & x_0 - x_0 x_1 - \; c_0 x_0 \; w, \\
& \dot{x}_1 & = & - x_1 + x_0 x_1 - \; c_1 x_1 \; w, \\
& \dot{x}_2 & = & (x_0 - 1)^2 + (x_1 - 1)^2, \\[1.5ex]
& x(0) &=& (0.5, 0.7, 0)^T, \\
& w(t) &\in& \{0, 1\}.
\end{array}
</math>
</p>

Here the differential states <math>(x_0, x_1)</math> describe the biomasses of prey and predator, respectively. The third differential state is used here to transform the objective, an integrated deviation, into the Mayer formulation <math>\min \; x_2(t_f)</math>. The decision, whether the fishing fleet is actually fishing at time <math>t</math> is denoted by <math>w(t)</math>.

== Parameters ==

These fixed values are used within the model.

<math>
\begin{array}{rcl}
[t_0, t_f] &=& [0, 12],\\
(c_0, c_1) &=& (0.4, 0.2).
\end{array}
</math>

== Reference Solutions ==

If the problem is relaxed, i.e., we demand that <math>w(t)</math> be in the continuous interval <math>[0, 1]</math> instead of the binary choice <math>\{0,1\}</math>, the optimal solution can be determined by means of [http://en.wikipedia.org/wiki/Pontryagin%27s_minimum_principle Pontryagins maximum principle]. The optimal solution contains a singular arc, as can be seen in the plot of the optimal control. The two differential states and corresponding adjoint variables in the indirect approach are also displayed. A different approach to solving the relaxed problem is by using a direct method such as collocation or Bock's direct multiple shooting method. Optimal solutions for different control discretizations are also plotted in the leftmost figure.

The optimal objective value of this relaxed problem is <math>x_2(t_f) = 1.34408</math>. As follows from MIOC theory <bib id="Sager2011d" /> this is the best lower bound on the optimal value of the original problem with the integer restriction on the control function. In other words, this objective value can be approximated arbitrarily close, if the control only switches often enough between 0 and 1. As no optimal solution exists, two suboptimal ones are shown, one with only two switches and an objective function value of <math>x_2(t_f) = 1.38276</math>, and one with 56 switches and <math>x_2(t_f) = 1.34416</math>.

<gallery caption="Reference solution plots" widths="180px" heights="140px" perrow="2">
Image:lotkaRelaxedControls.png| Optimal relaxed control determined by an indirect approach and by a direct approach on different control discretization grids.
Image:lotkaindirektStates.png| Differential states and corresponding adjoint variables in the indirect approach.
Image:lotka2Switches.png| Control and differential states with only two switches.
Image:lotka56Switches.png| Control and differential states with 56 switches.
</gallery>

== Source Code ==

Model descriptions are available in

* [[:Category:ACADO | ACADO code]] at [[Lotka Volterra fishing problem (ACADO)]]
* [[:Category:AMPL | AMPL code]] at [[Lotka Volterra fishing problem (AMPL)]]
* [[:Category:APMonitor | APMonitor code]] at [[Lotka Volterra fishing problem (APMonitor)]]
* [[:Category:Bocop | Bocop code]] at [[Lotka Volterra fishing problem (Bocop)]]
* [[:Category:Casadi | Casadi code]] at [[Lotka Volterra fishing problem (Casadi)]]
* [[:Category:JModelica | JModelica code]] at [[Lotka Volterra fishing problem (JModelica)]]
* [[:Category:Julia/JuMP | JuMP code]] at [[Lotka Volterra fishing problem (JuMP)]]
* [[:Category:Muscod | Muscod code]] at [[Lotka Volterra fishing problem (Muscod)]]
* [[:Category:switch | switch code]] at [[Lotka Volterra fishing problem (switch)]]
* [[:Category:TomDyn/PROPT | PROPT code]] at [[Lotka Volterra fishing problem (TomDyn/PROPT)]]

== Variants ==

There are several alternative formulations and variants of the above problem, in particular

* a prescribed time grid for the control function <bib id="Sager2006" />, see also [[Lotka Volterra fishing problem (AMPL)]],
* a time-optimal formulation to get into a steady-state <bib id="Sager2005" />,
* the usage of a different target steady-state, as the one corresponding to <math> w(t) = 1</math> which is <math>(1 + c_1, 1 - c_0)</math>, see [[Lotka Volterra multi-arcs problem]]
* different fishing control functions for the two species, see [[Lotka Volterra Multimode fishing problem]]
* different parameters and start values.

== Miscellaneous and Further Reading ==
The Lotka Volterra fishing problem was introduced by Sebastian Sager in a proceedings paper <bib id="Sager2006" /> and revisited in his PhD thesis <bib id="Sager2005" />. These are also the references to look for more details.

== References ==
<biblist />


[[Category:MIOCP]]
[[Category:ODE model]]
[[Category:Tracking objective]]
[[Category:Chattering]]
[[Category:Sensitivity-seeking arcs]]
[[Category:Population dynamics]]



We present numerical results for a benchmark MIOCP from a previous study [157] with the
addition of switching constraints. In its original form, the problem was:

After partial outer convexification with respect to the integer control v, the binary
convexified counterpart problem reads