[PPL-devel] [GIT] ppl/ppl(master): Improved the documentation with examples for uses of the big parameter.
François Galea
francois.galea at uvsq.fr
Fri Mar 19 22:15:25 CET 2010
Module: ppl/ppl
Branch: master
Commit: 124faa76cafb6e7cd49df166614178a30a5cedf2
URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=124faa76cafb6e7cd49df166614178a30a5cedf2
Author: François Galea <francois.galea at uvsq.fr>
Date: Fri Mar 19 22:07:21 2010 +0100
Improved the documentation with examples for uses of the big parameter.
---
src/PIP_Problem.defs.hh | 143 ++++++++++++++++++++++++++++++++++++++++++-----
1 files changed, 128 insertions(+), 15 deletions(-)
diff --git a/src/PIP_Problem.defs.hh b/src/PIP_Problem.defs.hh
index 32920d9..51e4165 100644
--- a/src/PIP_Problem.defs.hh
+++ b/src/PIP_Problem.defs.hh
@@ -326,37 +326,150 @@ operator<<(std::ostream& s, const PIP_Problem& p);
\f$M-x'_i\f$, where the \f$x'_i\f$ variables are positive variables to
be minimized.
- Solve the lexicographic minimum for the \f$x'\f$ variable vector.
- - In the solution expressions, the values of the original variables are
- obtained from the resulting values of the \f$x'_i\f$ variables by
- applying the equality \f$x_i = M-x'_i\f$.
+ - In the solution expressions, the values of the \f$x'\f$ variables will
+ be expressed in the form: \f$x'_i = M-x_i\f$. To get back the value of
+ the expression of each \f$x_i\f$ variable, just apply the
+ formula: \f$x_i = M-x'_i\f$.
+ \par
+ Note that if the resulting expression of one of the \f$x'_i\f$ variables
+ is not in the \f$x'_i = M-x_i\f$ form, this means that the
+ sign-unrestricted problem is unbounded.
\par
You can choose to maximize only a subset of the variables while minimizing
the other variables. In that case, just apply the variable substitution
method on the variables you want to be maximized. The variable
optimization priority will still be in lexicographic order.
- \par Allowing variables and parameters to be arbitrarily signed
- You can deal with arbitrarily signed variables and/or parameters by
- reformulating the constraints using variable and/or parameter
- substitution. Proceed the following steps:
+ \par
+ \b Example: consider you want to find the lexicographic maximum of the
+ \f$(x,y)\f$ vector, under the constraints:
+ \f[\left\{\begin{array}{l}
+ y \geq 2x - 4\\
+ y \leq -x + p
+ \end{array}\right.\f]
+ \par
+ where \f$p\f$ is a parameter.
+ \par
+ After variable substitution, the constraints become:
+ \f[\left\{\begin{array}{l}
+ M - y \geq 2M - 2x - 4\\
+ M - y \leq -M + x + p
+ \end{array}\right.\f]
+ \par
+ The code for creating the corresponding problem object is the following:
+ \code
+ Variable x(0);
+ Variable y(1);
+ Variable p(2);
+ Variable M(3);
+ Variables_Set params(p, M);
+ Constraint_System cs;
+ cs.insert(M - y >= 2*M - 2*x - 4);
+ cs.insert(M - y <= -M + x + p);
+ PIP_Problem pip(cs.space_dimension(), cs.begin(), cs.end(), params);
+ pip.set_big_parameter_dimension(3); // M is the big parameter
+ \endcode
+ Solving the problem provides the following solution:
+ \verbatim
+ Parameter E = (C + 1) div 3
+ {D - E - 1 ; -C + D + E + 1}
+ \endverbatim
+ Under the notations above, the solution is:
+ \f[ \left\{\begin{array}{l}
+ x'=M-\left\lfloor\frac{p+1}{3}\right\rfloor-1\\
+ y'=M-p+\left\lfloor\frac{p+1}{3}\right\rfloor+1
+ \end{array}\right.
+ \f]
+ \par
+ Performing substitution again provides us with the values of the original
+ variables:
+ \f[ \left\{\begin{array}{l}
+ x=\left\lfloor\frac{p+1}{3}\right\rfloor+1\\
+ y=p-\left\lfloor\frac{p+1}{3}\right\rfloor-1
+ \end{array}\right.
+ \f]
+
+ \par Allowing variables to be arbitrarily signed
+ You can deal with arbitrarily signed variables by reformulating the
+ constraints using variable substitution. Proceed the following steps:
- Create a big parameter (see PIP_Problem::set_big_parameter_dimension),
which we will call \f$M\f$.
- Reformulate each of the maximization problem constraints by
substituting each \f$x_i\f$ variable with an expression of the form
- \f$x'_i-M\f$, where the \f$x'_i\f$ variables are positive, and/or by
- substituting each \f$p_i\f$ parameter with an expression of the form
- \f$p'_i-M\f$, where the \f$p'_i\f$ parameters are positive.
+ \f$x'_i-M\f$, where the \f$x'_i\f$ variables are positive.
- Solve the lexicographic minimum for the \f$x'\f$ variable vector.
- - In the solution expressions, the values of the original variables
- and/or parameters are obtained from the resulting values of the
- \f$x'_i\f$ variables and/or the \f$p'_i\f$ parameters by applying the
- equalities \f$x_i = M-x'_i\f$ and/or \f$p_i = M-p'_i\f$.
-
+ - The solution expression can be read in the form:
+ - In the solution expressions, the values of the \f$x'\f$ variables will
+ be expressed in the form: \f$x'_i = x_i+M\f$. To get back the value of
+ the expression of each signed \f$x_i\f$ variable, just apply the
+ formula: \f$x_i = x'_i-M\f$.
+ \par
+ Note that if the resulting expression of one of the \f$x'_i\f$ variables
+ is not in the \f$x'_i = x_i+M\f$ form, this means that the
+ sign-unrestricted problem is unbounded.
\par
You can choose to define only a subset of the variables to be
sign-unrestricted. In that case, just apply the variable substitution
method on the variables you want to be sign-unrestricted.
+ \par
+ \b Example: consider you want to find the lexicographic minimum of the
+ \f$(x,y)\f$ vector, where the \f$x\f$ and \f$y\f$ variables are
+ sign-unrestricted, under the constraints:
+ \f[\left\{\begin{array}{l}
+ y \geq -2x - 4\\
+ 2y \leq x + 2p
+ \end{array}\right.\f]
+ \par
+ where \f$p\f$ is a parameter.
+ \par
+ After variable substitution, the constraints become:
+ \f[\left\{\begin{array}{l}
+ y' - M \geq -2x' + 2M - 4\\
+ 2y' - 2M \leq x' - M + 2p
+ \end{array}\right.\f]
+ \par
+ The code for creating the corresponding problem object is the following:
+ \code
+ Variable x(0);
+ Variable y(1);
+ Variable p(2);
+ Variable M(3);
+ Variables_Set params(p, M);
+ Constraint_System cs;
+ cs.insert(y - M >= -2*x + 2*M - 4);
+ cs.insert(2*y - 2*M <= x - M + 2*p);
+ PIP_Problem pip(cs.space_dimension(), cs.begin(), cs.end(), params);
+ pip.set_big_parameter_dimension(3); // M is the big parameter
+ \endcode
+ \par
+ Solving the problem provides the following solution:
+ \verbatim
+ Parameter E = (2*C + 3) div 5
+ {D - E - 1 ; D + 2*E - 2}
+ \endverbatim
+ Under the notations above, the solution is:
+ \f[ \left\{\begin{array}{l}
+ x'=M-\left\lfloor\frac{2p+3}{5}\right\rfloor-1\\
+ y'=M+2\left\lfloor\frac{2p+3}{5}\right\rfloor-2
+ \end{array}\right.
+ \f]
+ \par
+ Performing substitution again provides us with the values of the original
+ variables:
+ \f[ \left\{\begin{array}{l}
+ x=\left\lfloor\frac{2p+3}{5}\right\rfloor-1\\
+ y=2\left\lfloor\frac{2p+3}{5}\right\rfloor-2
+ \end{array}\right.
+ \f]
+
+ \par Allowing parameters to be arbitrarily signed
+ You can consider a parameter \f$p\f$ arbitrarily signed by replacing
+ \f$p\f$ with \f$p^+-p^-\f$, where both \f$p^+\f$ and \f$p^-\f$ are
+ positive parameters. To represent a set of arbitrarily signed parameters,
+ replace each parameter \f$p_i\f$ with \f$p^+_i-p^-\f$, where \f$-p^-\f$ is
+ the minimum negative value of all parameters.
+
\par Minimizing a linear cost function
Lexicographic solving can be used to find the parametric minimum of a
linear cost function.
More information about the PPL-devel
mailing list