Re: [Fwd: GUSEK exercise review support request]
On Sun, 5 Jun 2022, Andrew Makhorin wrote:
> Forwarded Message
>
> Date: Fri, 3 Jun 2022 16:46:42 -0500
> Subject: GUSEK exercise review support request
> To: m...@gnu.org
> From: Román Leonardo Rodriguez Florián
> Kind regards Andrew,
>
> I hope you are very well, I would like to ask for your support, if you
> can help me by reviewing the GUSEK exercise that I am sending you attached,
> I think I am indexing wrong.
>
> Reading model section from A_mixture_problem(ALGEBRAICO).mod...
> A_mixture_problem(ALGEBRAIC).mod:23: syntax error in literal set
> Context: i ] ; subject to REQ_MIN_SEM { i in seeds } : sum { i in
> MathProg model processing error
the version in the attachment seems to run. Apart from the sum braces,
indexing needed to be swapped, since in the data the "NORMAL",
"ESPECIAL" and "EXTRA" lines correspond to the 1st array index i. And a
few data entries were missing (I set them to 0, which may not be the
wanted).
Best Regards, Hartmut
Un_problema_de_mezclas(ALGEBRAICO).mod
Description: application/xml-dtd
Re: [Fwd: GUSEK exercise review support request]
On Sun, 5 Jun 2022, Andrew Makhorin wrote:
> Forwarded Message
> Date: Fri, 3 Jun 2022 16:46:42 -0500
> Subject: GUSEK exercise review support request
> To: m...@gnu.org
> From: Román Leonardo Rodriguez Florián
> Kind regards Andrew,
>
> I hope you are very well, I would like to ask for your support, if you
> can help me by reviewing the GUSEK exercise that I am sending you attached,
> I think I am indexing wrong.
>
> Reading model section from A_mixture_problem(ALGEBRAICO).mod...
> A_mixture_problem(ALGEBRAIC).mod:23: syntax error in literal set
> Context: i ] ; subject to REQ_MIN_SEM { i in seeds } : sum { i in
> MathProg model processing error
This error goes away when you move *_rec_cant[i,j] to the left side and
put the entire sum{j in mezclas} term it into brackets:
subject to REQ_MIN_SEM {i in semillas}: sum{j in mezclas} (1*libras[i,j] -
min_req_cant[i,j]) >= 0 ;
# Restricción del Porcentajes máximos Semillas en Mezcla NORMAL
subject to REQ_MAX_SEM {i in semillas}: sum{j in mezclas} (1*libras[i,j] -
max_req_cant[i,j]) <= 0 ;
There remains another error, something with data...
Best Regards, Hartmut
Re: One-off error in the MIP solver?
1 0 1
> 13 x[13] * 1 0 1
> 14 x[14] * 1 0 1
> 15 x[15] * 1 0 1
> 16 x[16] * 1 0 1
> 17 x[17] * 1 0 1
> 18 x[18] * 0 0 1
> 19 x[19] * 0 0 1
> 20 x[20] * 0 0 1
> 21 e 0 0
>
> Integer feasibility conditions:
>
> KKT.PE: max.abs.err = 0.00e+00 on row 0
> max.rel.err = 0.00e+00 on row 0
> High quality
>
> KKT.PB: max.abs.err = 1.00e+00 on row 3
> max.rel.err = 7.63e-06 on row 3
> Low quality
Many thanks for your explanation! It will take me some time to get the
details. For now i have just added a --tolint parameter to the command
line of glpsol (file glpsol.c) here, and with --tolint 1e-6 or lower the
result comes out right. Hopefully this and a few other --tol parameters
will find their way into glpsol. GMPL by glpsol is such a funny and
approachable language for learning and trying out LP/MIP stuff.
Best Regards, Hartmut
> _
>
> On 24.01.2022 11:46, Hartmut Henkel wrote:
>
> Hi,
>
> here seems to be some one-off error in gmpl/glpk (5.0, debian Linux):
>
> param v := 131072;
> param n := 20; # number of bits
> set J := 1..n; # set of all bits
> var x{j in J}, binary;
> var e, >= 0;
> minimize slack: e;
>
> s.t. cs1: sum{j in J} (2**(j - 1) * x[j]) - v <= e;
> s.t. cs2: sum{j in J} (2**(j - 1) * x[j]) - v >= -e;
>
> solve;
>
> printf "v: %d\nv: ", v;
> for {j in J} printf "%d", x[n - j + 1];
> printf "\n";
> printf "v: %d\n", sum{j in J} (2**(j - 1) * x[j]);
> printf "e: %d\n", e;
>
> end;
>
> Here it prints:
>
> v: 131072
> v: 001
> v: 131071
> e: 0
>
> With v = 131071 or v = 131073 or v = 65536 it works fine. Also fine with
> larger numbers like v = 88. Same problem when solving the exported
> .lp file, which looks ok., confirmed by another solver. Seems not to be
> a general int limitation or printing issue. Do you have any idea what's
> happening here?
>
> Best Regards, Hartmut
One-off error in the MIP solver?
Hi,
here seems to be some one-off error in gmpl/glpk (5.0, debian Linux):
param v := 131072;
param n := 20; # number of bits
set J := 1..n; # set of all bits
var x{j in J}, binary;
var e, >= 0;
minimize slack: e;
s.t. cs1: sum{j in J} (2**(j - 1) * x[j]) - v <= e;
s.t. cs2: sum{j in J} (2**(j - 1) * x[j]) - v >= -e;
solve;
printf "v: %d\nv: ", v;
for {j in J} printf "%d", x[n - j + 1];
printf "\n";
printf "v: %d\n", sum{j in J} (2**(j - 1) * x[j]);
printf "e: %d\n", e;
end;
Here it prints:
v: 131072
v: 001
v: 131071
e: 0
With v = 131071 or v = 131073 or v = 65536 it works fine. Also fine with
larger numbers like v = 88. Same problem when solving the exported
.lp file, which looks ok., confirmed by another solver. Seems not to be
a general int limitation or printing issue. Do you have any idea what's
happening here?
Best Regards, Hartmut
GLPK: Adding asin() and acos() to GNU MathProg
Hi Andrew,
when using gmpl/glpsol for curve fitting, the Chebyshev polynomial t(n,
x) = cos(n * acos(x)) can not easily be built due to the missing acos()
function. The patch below adds asin() and acos() to gmpl. Here is an
example for use, minimax fitting of exp(x):
# $ glpsol --dual --model --tolbnd 1e-12 --toldj 1e-12 --tolpiv 1e-14 cheby.mod
param x_max := 1;
param tol := 0.001;
param n := 11;
param m := 1000 * n;
set cols := (1..n);
set rows := (1..m);
param v{i in rows} := exp((i - 1) / (m - 1) * x_max);
param t{i in rows, j in cols} := cos(j * acos((i - 1) / (m - 1) * x_max));
var x{j in cols};
var d;
maximize slack: d;
s.t. slack1: d >= 0;
s.t. pass1{i in rows}: d + v[i] - sum{j in cols} (x[j] * t[i,j]) <= tol;
s.t. pass2{i in rows}: d - v[i] + sum{j in cols} (x[j] * t[i,j]) <= tol;
solve;
printf "#d\n", d > "result";
printf{j in cols}: "%d %.10g\n", j, x[j].val >> "result";
end;
Below is the simple patch, checked with the above code. I would be glad
if you could include this into glpk. The documentation i could update
only in the english version.
Best Regards, Hartmut
Hartmut Henkel, Zellhausen, Germany
--- glpk-5.0/src/mpl/mpl.h 2020-12-16 10:00:00.0 +0100
+++ glpk-5.0-mod/src/mpl/mpl.h 2021-07-24 13:54:51.324270191 +0200
@@ -830,10 +830,18 @@
double fp_sin(MPL *mpl, double x);
/* floating-point trigonometric sine */
+#define fp_asin _glp_mpl_fp_asin
+double fp_asin(MPL *mpl, double x);
+/* floating-point trigonometric arcsine */
+
#define fp_cos _glp_mpl_fp_cos
double fp_cos(MPL *mpl, double x);
/* floating-point trigonometric cosine */
+#define fp_acos _glp_mpl_fp_acos
+double fp_acos(MPL *mpl, double x);
+/* floating-point trigonometric arccosine */
+
#define fp_tan _glp_mpl_fp_tan
double fp_tan(MPL *mpl, double x);
/* floating-point trigonometric tangent */
@@ -2117,64 +2125,66 @@
#define O_LOG10 329 /* common (decimal) logarithm */
#define O_SQRT 330 /* square root */
#define O_SIN 331 /* trigonometric sine */
-#define O_COS 332 /* trigonometric cosine */
-#define O_TAN 333 /* trigonometric tangent */
-#define O_ATAN 334 /* trigonometric arctangent */
-#define O_ROUND 335 /* round to nearest integer */
-#define O_TRUNC 336 /* truncate to nearest integer */
-#define O_CARD 337 /* cardinality of set */
-#define O_LENGTH338 /* length of symbolic value */
+#define O_ASIN 332 /* trigonometric arcsine */
+#define O_COS 333 /* trigonometric cosine */
+#define O_ACOS 334 /* trigonometric arccosine */
+#define O_TAN 335 /* trigonometric tangent */
+#define O_ATAN 336 /* trigonometric arctangent */
+#define O_ROUND 337 /* round to nearest integer */
+#define O_TRUNC 338 /* truncate to nearest integer */
+#define O_CARD 339 /* cardinality of set */
+#define O_LENGTH340 /* length of symbolic value */
/* binary operations ---*/
-#define O_ADD 339 /* addition */
-#define O_SUB 340 /* subtraction */
-#define O_LESS 341 /* non-negative subtraction */
-#define O_MUL 342 /* multiplication */
-#define O_DIV 343 /* division */
-#define O_IDIV 344 /* quotient of exact division */
-#define O_MOD 345 /* remainder of exact division */
-#define O_POWER 346 /* exponentiation (raise to power) */
-#define O_ATAN2 347 /* trigonometric arctangent */
-#define O_ROUND2348 /* round to n fractional digits */
-#define O_TRUNC2349 /* truncate to n fractional digits */
-#define O_UNIFORM 350 /* pseudo-random in [a, b) */
-#define O_NORMAL351 /* gaussian random, given mu and sigma */
-#define O_CONCAT352 /* concatenation */
-#define O_LT353 /* comparison on 'less than' */
-#define O_LE354 /* comparison on 'not greater than' */
-#define O_EQ355 /* comparison on 'equal to' */
-#define O_GE356 /* comparison on 'not less than' */
-#define O_GT357 /* comparison on 'greater than' */
-#define O_NE358 /* comparison on 'not equal to' */
-#define O_AND 359 /* conjunction (logical "and") */
-#define O_OR360 /* disjunction (logical "or") */
-#define O_UNION 361 /* union */
-#define O_DIFF 362 /* difference */
-#define O_SYMDIFF 363 /* symmetric difference */
-#define O_INTER 364 /* intersection */
-#define O_CROSS 365 /* cross (Cartesian) product */
-#define O_IN366 /* test on 'x in Y' */
-#define O_NOTIN 367 /* test on 'x not in Y
glpsol: Adding tol_bnd, tol_dj, tol_piv options
Hi Andrew,
when using glpsol for optimization of a row- and column-dense problem
written in GNU MathProg, the default tolerances preset in glpsol are not
sufficient for finding the optimum. But, when using the C API with
setting lower/tighter tolerances (e. g. factor 1e-4) in the smcp
structure, the maximum is found.
These three tolerance options are currently missing in glpsol, and it
would be nice to have them included. They also let solve the problem
above. I would be glad if you could apply the two trivial patches below
to the sources.
Best Regards, Hartmut
Hartmut Henkel, Zellhausen, Germany
--- orig/examples/glpsol.c 2021-07-04 10:57:19.718164980 +0200
+++ glpsol.c2021-07-03 12:32:22.216853938 +0200
@@ -331,6 +331,11 @@
"fault)\n");
xprintf(" --norelax use standard \"textbook\" ratio tes"
"t\n");
+#if 1 /* 2021-07-03 */
+ xprintf(" --tolbnd tol set tol_bnd tolerance to tol\n");
+ xprintf(" --toldj tol set tol_dj tolerance to tol\n");
+ xprintf(" --tolpiv tol set tol_piv tolerance to tol\n");
+#endif
#if 0 /* 23/VI-2017 */
#if 1 /* 28/III-2016 */
xprintf(" --flipuse flip-flop ratio test (assumes -"
@@ -787,6 +792,50 @@
csa->smcp.r_test = GLP_RT_HAR;
else if (p("--norelax"))
csa->smcp.r_test = GLP_RT_STD;
+#if 1 /* 2021-07-03 */
+ else if (p("--tolbnd"))
+ { double tol_bnd;
+k++;
+if (k == argc || argv[k][0] == '\0' || argv[k][0] == '-')
+{ xprintf("No tol_bnd tolerance specified\n");
+ return 1;
+}
+if (str2num(argv[k], &tol_bnd) || tol_bnd < 0.0)
+{ xprintf("Invalid tol_bnd tolerance '%s'\n",
+ argv[k]);
+ return 1;
+}
+csa->smcp.tol_bnd = tol_bnd;
+ }
+ else if (p("--toldj"))
+ { double tol_dj;
+k++;
+if (k == argc || argv[k][0] == '\0' || argv[k][0] == '-')
+{ xprintf("No tol_dj tolerance specified\n");
+ return 1;
+}
+if (str2num(argv[k], &tol_dj) || tol_dj < 0.0)
+{ xprintf("Invalid tol_dj tolerance '%s'\n",
+ argv[k]);
+ return 1;
+}
+csa->smcp.tol_dj = tol_dj;
+ }
+ else if (p("--tolpiv"))
+ { double tol_piv;
+k++;
+if (k == argc || argv[k][0] == '\0' || argv[k][0] == '-')
+{ xprintf("No tol_piv tolerance specified\n");
+ return 1;
+}
+if (str2num(argv[k], &tol_piv) || tol_piv < 0.0)
+{ xprintf("Invalid tol_piv tolerance '%s'\n",
+ argv[k]);
+ return 1;
+}
+csa->smcp.tol_piv = tol_piv;
+ }
+#endif
#if 1 /* 28/III-2016 */
else if (p("--flip"))
#if 0 /* 23/VI-2017 */
--- orig/doc/glpk10.tex 2021-07-04 11:08:45.443664879 +0200
+++ glpk10.tex 2021-07-04 11:10:26.475813095 +0200
@@ -91,6 +91,9 @@
--nosteep use standard "textbook" pricing
--relax use Harris' two-pass ratio test (default)
--norelax use standard "textbook" ratio test
+ --tolbnd tol set tol_bnd tolerance to tol
+ --toldj tol set tol_dj tolerance to tol
+ --tolpiv tol set tol_piv tolerance to tol
--presol use presolver (default; assumes --scale and --adv)
--nopresoldo not use presolver
--exact use simplex method based on exact arithmetic
