Re: [Help-glpk] Objective function defined with max, min.
On Thu, 5 Jan 2017, Michael Hennebry wrote: The objective function includes crop(s) = median(0, s, 1) where the range of s includes both negative values and values > 1 . The set defined is not convex and so cannot be defined purely with linear constraints. One can get around the need for a binary by using optimality. Add nonnegative auxillary variables p0, n0, p1 and n1. s = p0-n0 s = p1-n1+1 Adjust the objective to ensure that p0 or n0 is zero at optimality and that p1 or n1 is zero at optimality. Oops. That does not work. There are situations in which the optimality condition is useful, but your function is neither convex nor concave. You will need at least one binary. The convex hull of (s, crop(s) has vertices (smin, 0) (0, 0) (smax, 1) (1, 1) in that order. 0<=crop(s)<=1 crop(s)<=p0 crop(s)>=1-n1 -- Michael henne...@web.cs.ndsu.nodak.edu "Sorry but your password must contain an uppercase letter, a number, a haiku, a gang sign, a heiroglyph, and the blood of a virgin." -- someeecards ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Objective function defined with max, min.
> It should work for minimization, but I want to maximize expression > with f(x) as a summand. So adding Z should make the solution > unbounded. Yes, it doesn't work in case of maximization. You may try using the "standard big M" approach, for example, as follows. Let z1 = 1, z2 = 0, z3 = 0: -M1 <= x1 <= 0, 0 <= x2 <= 0, 0 <= x3 <= 0 z1 = 0, z2 = 1, z3 = 0: 0 <= x1 <= 0, 0 <= x2 <= 1, 0 <= x3 <= 0 z1 = 0, z2 = 0, z3 = 1: 0 <= x1 <= 0, 0 <= x2 <= 0, 1 <= x3 <= +M3 Then f(x) = min(0, max(1, x)) can be described by the following linear constraints: f = x2 + z3 x = x1 + x2 + x3 -M1 * z1 <= x1 <= 0 0 <= x2 <= z2 z3 <= x3 <= +M3 * z3 z1 + z2 + z3 = 1 where x1, x2, x3 are auxiliary continuous vars, z1, z2, z3 are auxiliary binary vars, M1, M3 are "big M" constants. Note that some auxiliary variables can be eliminated due to equality constraints. ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
[Help-glpk] Patches for simplex routines
Andrew,
I'm attaching two patches for the simplex routines.
The first one is just your idea [1] for restoring the objective limit
check in dual simplex when perturbation is enabled, which considerably
improves branch and bound performance. This is just to make sure it is
not forgotten.
The second patch changes two asserts into errors (one in primal and
one in dual). I managed to trigger the second one, but I'm changing
the first one just in case.
Best Regards,
Chris Matrakidis
PS. In addition to the patch [2] you mentioned a few days ago, in May
I sent another patch as well [3] for an mps reading bug.
[1] http://lists.gnu.org/archive/html/help-glpk/2016-04/msg6.html
[2] http://lists.gnu.org/archive/html/bug-glpk/2016-05/msg6.html
[3] http://lists.gnu.org/archive/html/bug-glpk/2016-05/msg1.html
diff --git a/src/simplex/spydual.c b/src/simplex/spydual.c
index e41baf2..d33ebb1 100644
--- a/src/simplex/spydual.c
+++ b/src/simplex/spydual.c
@@ -1374,13 +1374,15 @@ loop: /* main loop starts here */
check_accuracy(csa);
#endif
/* check if the objective limit has been reached */
-#if PERTURB
- /* FIXME */
- if (!perturb)
-#endif
if (csa->phase == 2 && csa->obj_lim != DBL_MAX
&& spx_eval_obj(lp, beta) >= csa->obj_lim)
- { if (csa->beta_st != 1)
+ { if (perturb)
+ { /* remove perturbation */
+perturb = 0;
+memcpy(csa->lp->c, csa->orig_c, (1+n) * sizeof(double));
+csa->phase = csa->d_st = 0;
+ }
+ if (csa->beta_st != 1)
csa->beta_st = 0;
if (csa->d_st != 1)
csa->d_st = 0;
diff --git a/src/simplex/spxprim.c b/src/simplex/spxprim.c
index 4a5e7aa..1f4aac8 100644
--- a/src/simplex/spxprim.c
+++ b/src/simplex/spxprim.c
@@ -963,7 +963,13 @@ loop: /* main loop starts here */
else
spx_nt_prod(lp, nt, trow, 1, -1.0, rho);
/* FIXME: tcol[p] and trow[q] should be close to each other */
- xassert(trow[csa->q] != 0.0);
+ if (trow[csa->q] == 0.0)
+ { if (msg_lev >= GLP_MSG_ERR)
+xprintf("Error: trow[q] == 0.0\n");
+ csa->p_stat = csa->d_stat = GLP_UNDEF;
+ ret = GLP_EFAIL;
+ goto fini;
+ }
/* update reduced costs of non-basic variables for adjacent
* basis */
if (spx_update_d(lp, d, csa->p, csa->q, trow, tcol) <= 1e-9)
diff --git a/src/simplex/spydual.c b/src/simplex/spydual.c
index d33ebb1..c8350d2 100644
--- a/src/simplex/spydual.c
+++ b/src/simplex/spydual.c
@@ -1632,7 +1632,13 @@ loop: /* main loop starts here */
t_pivcol += timer() - t_start;
#endif
/* FIXME: tcol[p] and trow[q] should be close to each other */
- xassert(csa->tcol.vec[csa->p] != 0.0);
+ if (csa->tcol.vec[csa->p] == 0.0)
+ { if (msg_lev >= GLP_MSG_ERR)
+xprintf("Error: tcol[p] == 0.0\n");
+ csa->p_stat = csa->d_stat = GLP_UNDEF;
+ ret = GLP_EFAIL;
+ goto fini;
+ }
/* update values of basic variables for adjacent basis */
k = head[csa->p]; /* x[k] = xB[p] */
p_flag = (l[k] != u[k] && beta[csa->p] > u[k]);
___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk
[Help-glpk] [Fwd: Re: Objective function defined with max, min.]
Forwarded Message From: Alexey Karakulov To: Michael Hennebry Cc: Andrew Makhorin , help-glpk@gnu.org Subject: Re: [Help-glpk] Objective function defined with max, min. Date: Fri, 6 Jan 2017 00:09:00 +0200 Michael, thanks. This seems to work for me, but it's only for maximizing "crop(s)", not minimizing, right? I have "crop(s[i])" with both positive and negative signs for different "i", so I should do some fiddling to get it working. On Thu, Jan 5, 2017 at 8:39 PM, Michael Hennebry wrote: The objective function includes crop(s) = median(0, s, 1) where the range of s includes both negative values and values > 1 . The set defined is not convex and so cannot be defined purely with linear constraints. One can get around the need for a binary by using optimality. Add nonnegative auxillary variables p0, n0, p1 and n1. s = p0-n0 s = p1-n1+1 Adjust the objective to ensure that p0 or n0 is zero at optimality and that p1 or n1 is zero at optimality. 0<=crop(s)<=1 crop(s)<=p0 crop(s)>=1-n1 -- Michael henne...@web.cs.ndsu.nodak.edu "Sorry but your password must contain an uppercase letter, a number, a haiku, a gang sign, a heiroglyph, and the blood of a virgin." -- someeecards ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Patch to configure a reentrant version of GLPK
Heinrich, > Why should this option be disabled by default? I have only really tested the patch on Linux so I thought it safer to have it disabled by default for the time being. This way, whoever really needs it can try it and won't be worse off if it doesn't work. > For all applications that up to now were only able to use GLPK with one > thread the patch makes no difference. Well, I noticed a very minor slowdown when enabled but nothing to worry about (at least on my system). > If we have such a switch a program calling the library will need a means > of determining if the library is thread-safe or not. This may still be required to help with code portability to systems with old glpk libraries (although a version check may be enough). > So it would be preferable not to have any switch at all but simply make > the library thread safe in all cases. I agree it makes sense to have it enabled by default eventually, but I think the switch is still necessary to ease configuring a single threaded version. Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
[Help-glpk] Adjusting GLPK for stdcall
On 01/05/2017 09:50 PM, Passorelli, Curtis wrote:
> I have the 4.60 source code. Is there any way to compile it to work
with VBA such as adding Gz to the Make File or changing the source code
to __stdcall?
Hello Curtis,
according to
https://msdn.microsoft.com/en-us/en_us/library/zxk0tw93.aspx
__stdcall is only relevant for 32bit and ignored on the amd64/x64
architecture.
/Gz sets the __stdcall convention for all functions
https://msdn.microsoft.com/en-us/library/46t77ak2.aspx
But the code still has to be changed manually where function pointers
are passed that have to be __cdecl. This was the case when calling qsort
under Visual Studio 2008.
Below you find a summary of the changes needed for 4.37. It is a small
number of places.
I think the best way to do it would be to provide a symbol, e.g. CDECL,
everywhere where compiling with /Gz requires __cdecl. This symbol than
can be defined as __cdecl in w32/config.h and as blank in all other
config.h files.
The patch should be sent to Andrew for integration into his upstream code.
@Andrew
LibreOffice supports calling native DLLs on Windows. The MPL license is
compatible with GPL, cf. https://www.gnu.org/licenses/license-list.html
So there is a legitimate reason for compiling with __stdcall convention.
Best regards
Heinrich Schuchardt
diff -ruN glpk-4.37/src/glpini02.c glpk-4.37-stdcall/src/glpini02.c
--- glpk-4.37/src/glpini02.c2009-03-29 11:00:00.0 +0200
+++ glpk-4.37-stdcall/src/glpini02.c2010-01-04 19:19:14.815755000 +0100
@@ -31,7 +31,7 @@
/* penalty value */
};
-static int fcmp(const void *ptr1, const void *ptr2)
+static int __cdecl fcmp(const void *ptr1, const void *ptr2)
{ /* this routine is passed to the qsort() function */
struct var *col1 = (void *)ptr1, *col2 = (void *)ptr2;
if (col1->q < col2->q) return -1;
diff -ruN glpk-4.37/src/glpios03.c glpk-4.37-stdcall/src/glpios03.c
--- glpk-4.37/src/glpios03.c2009-03-29 11:00:00.0 +0200
+++ glpk-4.37-stdcall/src/glpios03.c2010-01-04 19:19:14.815755000 +0100
@@ -432,7 +432,7 @@
#if 0
struct col { int j; double f; };
-static int fcmp(const void *x1, const void *x2)
+static int __cdecl fcmp(const void *x1, const void *x2)
{ const struct col *c1 = x1, *c2 = x2;
if (c1->f > c2->f) return -1;
if (c1->f < c2->f) return +1;
@@ -1811,7 +1811,7 @@
struct cut { IOSCUT *cut; double eff; };
-static int fcmp(const void *x1, const void *x2)
+static int __cdecl fcmp(const void *x1, const void *x2)
{ const struct cut *c1 = x1, *c2 = x2;
if (c1->eff > c2->eff) return -1;
if (c1->eff < c2->eff) return +1;
diff -ruN glpk-4.37/src/glpios05.c glpk-4.37-stdcall/src/glpios05.c
--- glpk-4.37/src/glpios05.c2009-03-29 11:00:00.0 +0200
+++ glpk-4.37-stdcall/src/glpios05.c2010-01-04 19:19:14.815755000 +0100
@@ -225,7 +225,7 @@
struct var { int j; double f; };
-static int fcmp(const void *p1, const void *p2)
+static int __cdecl fcmp(const void *p1, const void *p2)
{ const struct var *v1 = p1, *v2 = p2;
if (v1->f > v2->f) return -1;
if (v1->f < v2->f) return +1;
diff -ruN glpk-4.37/src/glpios06.c glpk-4.37-stdcall/src/glpios06.c
--- glpk-4.37/src/glpios06.c2009-03-29 11:00:00.0 +0200
+++ glpk-4.37-stdcall/src/glpios06.c2010-01-04 19:19:14.815755000 +0100
@@ -774,7 +774,7 @@
struct vset { int j; double v; };
-static int cmir_cmp(const void *p1, const void *p2)
+static int __cdecl cmir_cmp(const void *p1, const void *p2)
{ const struct vset *v1 = p1, *v2 = p2;
if (v1->v < v2->v) return -1;
if (v1->v > v2->v) return +1;
diff -ruN glpk-4.37/src/glpios10.c glpk-4.37-stdcall/src/glpios10.c
--- glpk-4.37/src/glpios10.c2009-03-29 11:00:00.0 +0200
+++ glpk-4.37-stdcall/src/glpios10.c2010-01-04 19:19:14.815755000 +0100
@@ -54,7 +54,7 @@
/* sorting key */
};
-static int fcmp(const void *x, const void *y)
+static int __cdecl fcmp(const void *x, const void *y)
{ /* comparison routine */
const struct VAR *vx = x, *vy = y;
if (vx->d > vy->d)
diff -ruN glpk-4.37/w32/Makefile_VC9_DLL
glpk-4.37-stdcall/w32/Makefile_VC9_DLL
--- glpk-4.37/w32/Makefile_VC9_DLL 2009-03-29 11:00:00.0 +0200
+++ glpk-4.37-stdcall/w32/Makefile_VC9_DLL 2010-01-04 19:19:14.815755000
+0100
@@ -1,6 +1,6 @@
# Build GLPK DLL with Microsoft Visual Studio Express 2008
-CFLAGS = /I. /DHAVE_CONFIG_H /nologo /W3 /O2
+CFLAGS = /I. /DHAVE_CONFIG_H /nologo /W3 /O2 /Gz
OBJSET = \
..\src\glpapi01.obj \
___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Patch to configure a reentrant version of GLPK
On 12/29/2016 03:25 PM, Chris Matrakidis wrote: > Andrew, > > The attached patch adds the --enable-reentrant option to configure > (disabled by default) Thank you Chris for you patch. Thread safeness for GLPK has been a topic discussed again and again. Why should this option be disabled by default? For all applications that up to now were only able to use GLPK with one thread the patch makes no difference. If we have such a switch a program calling the library will need a means of determining if the library is thread-safe or not. So it would be preferable not to have any switch at all but simply make the library thread safe in all cases. > as suggested by David Monniaux a few days ago > [1]. When selected, the appropriate thread local storage class > specifier is identified, added to config.h and used in tls.c. The > patch is based on the work of Dmitry Nadezhin [2] and the ax_tls macro > form the autoconf archive [3] simplified to match the configure.ac > style, The code remains C89 if the option is not selected. It also remains C89 if the compiler does not support any of the prefixes tested. Best regards Heinrich Schuchardt > > I have tested this extensively but only on Linux with gcc, so > additional testing and feedback is welcome. > > Best Regards, > > Chris Matrakidis > > [1] http://lists.gnu.org/archive/html/help-glpk/2016-12/msg00023.html > [2] https://github.com/nadezhin/thermocompensation > [3] http://www.gnu.org/software/autoconf-archive/ax_tls.html ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
[Help-glpk] [Fwd: Re: Objective function defined with max, min.]
Forwarded Message
From: Alexey Karakulov
To: Andrew Makhorin
Cc: help-glpk@gnu.org
Subject: Re: Objective function defined with max, min.
Date: Thu, 5 Jan 2017 20:46:43 +0200
f(x) = 0, if x < 0
= x, if x >= 0
The latter equality can be modeled thru the following
linear constraints:
x = x1 - x2
f = x1
x1, x2 >= 0
Simplified:
> f = x + z
> f, z >= 0
It should work for minimization, but I want to maximize expression with
f(x) as a summand. So adding Z should make the solution unbounded.
Note that in my problem X is dependent variable. If it was independent,
I could just write "x" instead of "f(x)".
Basically, I want to maximize convex piece-wise linear function f(x).
Probably I'll have to use binary variables as described in the second
case
here:
http://orinanobworld.blogspot.com.cy/2010/10/piecewise-linear-functions-in-math.html
On Thu, Jan 5, 2017 at 12:52 AM, Andrew Makhorin wrote:
On Thu, 2017-01-05 at 01:50 +0300, Andrew Makhorin wrote:
> On Wed, 2017-01-04 at 23:43 +0200, Alexey Karakulov wrote:
> > Hi, I have this kind of function in the objective:
> >
> > > crop(s) = max(0, min(1, s))
> >
> >
> > I wonder if it's possible (and how) to reformulate the task
to be LP
> > problem. I have read this posting [1], but I'm not sure how
to apply
> > it.
>
>
> Note that
>
> crop(x) = f(x) - f(x-1)
>
> where
>
> f(x) = 0, if x < 0
> = x, if x >= 0
>
> The latter equality can be modeled thru the following linear
> constraints:
>
> x = x1 + x2
Must read
x = x1 - x2
> f = x1
> x1, x2 >= 0
>
> where x1, x2 are auxiliary variables.
>
> f(x-1) can be modeled in the same way by taking y = x-1.
>
> (Check all this carefully for errors.)
>
> >
> >
> > > param maxN default 1000;
> > > param maxJ default 10;
> > > set N := 1 .. maxN;
> > > set J := 1 .. maxJ;
> > > param a{N};
> > > param w{N};
> > > var X0;
> > > var X{J};
> > > var S{maxJ .. maxN};
> >
> >
> > > maximize Obj: sum {n in N} w[n] * crop(S[n])
> >
> > > subject to DefineS {n in maxJ .. maxN}: S[n] = X0 + sum {j
in J}
> > a[n-j+1] * X[j]
> >
> >
> > [1]:
http://lists.gnu.org/archive/html/help-glpk/2007-06/msg5.html
> >
>
___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] Objective function defined with max, min.
The objective function includes crop(s) = median(0, s, 1) where the range of s includes both negative values and values > 1 . The set defined is not convex and so cannot be defined purely with linear constraints. One can get around the need for a binary by using optimality. Add nonnegative auxillary variables p0, n0, p1 and n1. s = p0-n0 s = p1-n1+1 Adjust the objective to ensure that p0 or n0 is zero at optimality and that p1 or n1 is zero at optimality. 0<=crop(s)<=1 crop(s)<=p0 crop(s)>=1-n1 -- Michael henne...@web.cs.ndsu.nodak.edu "Sorry but your password must contain an uppercase letter, a number, a haiku, a gang sign, a heiroglyph, and the blood of a virgin." -- someeecards ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] [Fwd: VBA dll call]
Hello Curtis, please, find appended two examples. Please, load the module files to your VBA project. glpk.bas contains the library definitions. You will have to adjust the path to the glpk libary. lp.bas contains a linear problem. mip.bas contains a mixed integer problem. The definitions assume that you are using a 32bit system. Cf. https://support.office.com/en-us/article/What-version-of-Office-am-I-using-932788b8-a3ce-44bf-bb09-e334518b8b19 Best regards Heinrich Schuchardt On 01/04/2017 10:40 PM, Andrew Makhorin wrote: > Forwarded Message > To: help-glpk@gnu.org > Subject: VBA dll call > Date: Wed, 4 Jan 2017 19:34:29 + > > Hello, > > I have been working with the GLPK API. I can get most of the functions > working except when it comes to matrices. > > I am trying to fill up the constraint matrix, and it errors out and > shuts down Excel. > > Are there any obvious mistakes?> > Thanks for all of your hard work, > > Curtis Passorelli Attribute VB_Name = "glpk" Option Explicit ' enable/disable flag: Public Const GLP_ON = 1 ' enable something Public Const GLP_OFF = 0 ' disable something ' reason codes: Public Const GLP_IROWGEN = &H1 ' request for row generation Public Const GLP_IBINGO = &H2' better long solution found Public Const GLP_IHEUR = &H3 ' request for heuristic solution Public Const GLP_ICUTGEN = &H4 ' request for cut generation Public Const GLP_IBRANCH = &H5 ' request for branching Public Const GLP_ISELECT = &H6 ' request for subproblem selection Public Const GLP_IPREPRO = &H7 ' request for preprocessing ' optimization direction flag: Public Const GLP_MIN = 1 ' minimization Public Const GLP_MAX = 2 ' maximization ' kind of structural variable: Public Const GLP_CV = 1 ' continuous variable Public Const GLP_IV = 2 ' long variable Public Const GLP_BV = 3 ' binary variable ' type of auxiliary/structural variable: Public Const GLP_FR = 1 ' free variable Public Const GLP_LO = 2 ' variable with lower bound Public Const GLP_UP = 3 ' variable with upper bound Public Const GLP_DB = 4 ' double-bounded variable Public Const GLP_FX = 5 ' fixed variable ' status of auxiliary/structural variable: Public Const GLP_BS = 1 ' basic variable Public Const GLP_NL = 2 ' non-basic variable on lower bound Public Const GLP_NU = 3 ' non-basic variable on upper bound Public Const GLP_NF = 4 ' non-basic free variable Public Const GLP_NS = 5 ' non-basic fixed variable ' scaling options: Public Const GLP_SF_GM = &H1 ' perform geometric mean scaling Public Const GLP_SF_EQ = &H10' perform equilibration scaling Public Const GLP_SF_2N = &H20' round scale factors to power of two Public Const GLP_SF_SKIP = &H40 ' skip if problem is well scaled Public Const GLP_SF_AUTO = &H80 ' choose scaling options automatically ' solution indicator: Public Const GLP_SOL = 1 ' basic solution Public Const GLP_IPT = 2 ' interior-point solution Public Const GLP_MIP = 3 ' mixed long solution ' solution status: Public Const GLP_UNDEF = 1 ' solution is undefined Public Const GLP_FEAS = 2' solution is feasible Public Const GLP_INFEAS = 3 ' solution is infeasible Public Const GLP_NOFEAS = 4 ' no feasible solution exists Public Const GLP_OPT = 5 ' solution is optimal Public Const GLP_UNBND = 6 ' solution is unbounded Public Const GLP_MSG_OFF = 0 ' no output Public Const GLP_MSG_ERR = 1 ' warning and error messages only Public Const GLP_MSG_ON = 2 ' normal output Public Const GLP_MSG_ALL = 3 ' full output Public Const GLP_MSG_DBG = 4 ' debug output Public Const GLP_PRIMAL = 1 ' use primal simplex Public Const GLP_DUALP = 2 ' use dual if it fails, use primal Public Const GLP_DUAL = 3' use dual simplex Public Const GLP_PT_STD = &H11 ' standard (Dantzig rule) Public Const GLP_PT_PSE = &H22 ' projected steepest edge Public Const GLP_RT_STD = &H11 ' standard (textbook) Public Const GLP_RT_HAR = &H22 ' two-pass Harris' ratio test Public Const GLP_BR_FFV = 1 ' first fractional variable Public Const GLP_BR_LFV = 2 ' last fractional variable Public Const GLP_BR_MFV = 3 ' most fractional variable Public Const GLP_BR_DTH = 4 ' heuristic by Driebeck and Tomlin Public Const GLP_BR_PCH = 5 ' hybrid pseudocost heuristic Public Const GLP_BT_DFS = 1 ' depth first search Public Const GLP_BT_BFS = 2 ' breadth first search Public Const GLP_BT_BLB = 3 ' best local bound Public Const GLP_BT_BPH = 4 ' best projection heuristic Public Const GLP_PP_NONE = 0 ' disa
