Re: [Fwd: GLPK doubt]

[Michael Hennebry]

On Thu, 8 Feb 2024, Manuel Muñoz Márquez wrote:


You have a decision problem if and only if you have decision variables.


I think OP is using "decision variables" in a non-standard way:
binary auxilliary variables representing choices,
e.g., project p is done in month m.
OP wants to reduce it to one variable per project.
It won't work.
If q[p]=1 represents project p is done in month 1
and q[p]=37 represents project p is done in month 37,
then q[p]=19=(1+37)/2 allows project p to be half done in month 1
half in month 37.
OP could get it down to 6 binary variables per project,
but 'tain't obvious that it would help.
The LP relaxation might not be as tight.
The traditional TSP formulation has n*(n-1)/2 binary variables.
It could be got down to 2*n*lg(n),
but so far as I know, no one has tried to deal with the mess.

My suspicion is that OP's problem is equivalent to an assignment problem.
In that case, 12000 variables should not be difficult.

--
Michael   henne...@mail.cs.ndsu.nodak.edu
"SCSI is NOT magic. There are *fundamental technical
reasons* why it is necessary to sacrifice a young
goat to your SCSI chain now and then."   --   John Woods

Re: [Fwd: GLPK doubt]

[Michael Hennebry]

To represent a choice of one out of 61 possibilities,
you will likely need at least 6 integer variables.
A single variable with range 0..61 is
unlikely to produce an MILP formulation.

--
Michael   henne...@mail.cs.ndsu.nodak.edu
"His longhand was fairly good in his youth, but as he got older it got
smaller, more scribbly, and harder to read; although, like being hanged,
one can get used to it." -- Gordon Dickson on H.P. Lovecraft's handwriting

Re: glpsol will not handle example

[Michael Hennebry]

On Sun, 12 Nov 2023, Chris Matrakidis wrote:


You need --math instead of --glp.


Thanks.
I figured it would be a duh moment.
I'd mistaken GLPK format for GMPL format.

--
Michael   henne...@mail.cs.ndsu.nodak.edu
"I was just thinking about the life of a pumpkin.  Grow up in the sun,
happily entwined with others, and then someone comes along,
cuts you open, and rips your guts out."  --   Buffy

glpsol will not handle example

[Michael Hennebry]

From the glpk manual, I copied example E.1 to ex1.gmpl .

glpsol did not like it:
[hennebry@fedora triangle-free]$ glpsol --glp ex1.gmpl
GLPSOL--GLPK LP/MIP Solver 5.0
Parameter(s) specified in the command line:
 --glp ex1.gmpl
Reading problem data from 'ex1.gmpl'...
ex1.gmpl:1: error: problem line missing or invalid
GLPK LP/MIP file processing error
[hennebry@fedora triangle-free]$

Here is ex1.gmpl:
# A TRANSPORTATION PROBLEM
#
# This problem finds a least cost shipping schedule that meets
# requirements at markets and supplies at factories.
#
# References:
#
Dantzig G B, "Linear Programming and Extensions."
#
Princeton University Press, Princeton, New Jersey, 1963,
#
Chapter 3-3.
set I;
/* canning plants */
set J;
/* markets */
param a{i in I};
/* capacity of plant i in cases */
param b{j in J};
/* demand at market j in cases */
param d{i in I, j in J};
/* distance in thousands of miles */

param f;
/* freight in dollars per case per thousand miles */
param c{i in I, j in J} := f * d[i,j] / 1000;
/* transport cost in thousands of dollars per case */
var x{i in I, j in J} >= 0;
/* shipment quantities in cases */
minimize cost: sum{i in I, j in J} c[i,j] * x[i,j];
/* total transportation costs in thousands of dollars */
s.t. supply{i in I}: sum{j in J} x[i,j] <= a[i];
/* observe supply limit at plant i */
s.t. demand{j in J}: sum{i in I} x[i,j] >= b[j];
/* satisfy demand at market j */
data;

set I := Seattle San-Diego;
set J := New-York Chicago Topeka;
param a := Seattle
San-Diego350
600;
param b := New-York
Chicago
Topeka325
300
275;
param d :New-York
2.5
2.5
Seattle
San-Diego
Chicago
1.7
1.8
param f := 90;
end;

What is going on and what can I do about it?

--
Michael   henne...@mail.cs.ndsu.nodak.edu
"I was just thinking about the life of a pumpkin.  Grow up in the sun,
happily entwined with others, and then someone comes along,
cuts you open, and rips your guts out."  --   Buffy

Re: bpp plus type constrain

[Michael Hennebry]

On Wed, 11 Oct 2023, Leonardo Corato wrote:


About the upper bound, I realized the bins could't have been enough, so my
first code was a greedy solution: 1 bin per 1 item.


Two items per bin would also work.


Do you think I should write the full bpp with types, code? Maybe it could
help someone.


I'm not sure what you are asking.
If you are asking whether you should publish your gmpl,
why not?
It couldn't hurt.

BTW you still have not dealt with symmetry.
10 bins can be permuted more than 3 million ways.
15 bins more than a trillion ways.

--
Michael   henne...@mail.cs.ndsu.nodak.edu
"Occasionally irrational explanations are required"  --  Luke Roman

Re: bpp plus type constrain

[Michael Hennebry]

On Fri, 6 Oct 2023, Michael Hennebry wrote:


YY{y in mouldTypes, b in 1..n, i in I: mo[i]==t} y[t, b] >= x[i, b] ;


Oops. A y where a t was needed.  The corrected version:
YY{t in mouldTypes, b in 1..n, i in I: mo[i]==t} y[t, b] >= x[i, b] ;

--
Michael   henne...@mail.cs.ndsu.nodak.edu
"Occasionally irrational explanations are required"  --  Luke Roman

Re: bpp plus type constrain

[Michael Hennebry]

On Fri, 6 Oct 2023, Michael Hennebry wrote:


Your estimate of the number of bins necessary could be an underestimate.
It does not enforce the only two types in a bin requirement.
For larger problems, I think that that would be necessary.


I think that all that is needed is another else if:
else if exists i1 in 1..i-1 exists i2 in 1..i1  z[i1, j] and z[i2, j] and
 mo[i1] != mo[i2] != mo[i] != mo[i1] then 0
This could be a rather slow way to do it.
I think that, with effort, I could get it down to three levels of loops.

--
Michael   henne...@mail.cs.ndsu.nodak.edu
"Occasionally irrational explanations are required"  --  Luke Roman

Re: bpp plus type constrain

[Michael Hennebry]

Your estimate of the number of bins necessary could be an underestimate.
It does not enforce the only two types in a bin requirement.
For larger problems, I think that that would be necessary.

--
Michael   henne...@mail.cs.ndsu.nodak.edu
"Occasionally irrational explanations are required"  --  Luke Roman

Re: bpp plus type constrain

[Michael Hennebry]

On Fri, 6 Oct 2023, Leonardo Corato wrote:


As you can see in bin 2 and 3 there are 3 mold types, so sadly s.t. fred is
not limiting to 2


I'd misunderstood.
I'd thought that you want no more than two of a given type.

Using an auxillary array is probably easiest:
y[t, b] == 1 iff bin b has an item of type t.
It need not be binary or have an upper bound.
An upper bound of one would not hurt and might help.
An upper bound of two can be inferred from other constraints.

greg{b in 1..n} sum{t in mouldTypes} y[t, b] <= 2 ;

YY{y in mouldTypes, b in 1..n, i in I: mo[i]==t} y[t, b] >= x[i, b] ;

Without y, I think that O(n*|I|**3) constraints might be necessary.
cube{b in 1..n, i1 in I, i2 in I, i3 in I: i1< i2 < i3 and
   mo[i1] != mo[i2] != mo[i3] != moi10] }
x[i1, b] + x[i2, b] + x[i3, b] <= 2 ;
This is the kind of thing I'd be inclined to generate on the fly.

I'm not sure which set is stronger.
They might be equivalent.


Apparently you problems are small enough so that it does not matter much,
but you have rather a lot of symmetry.
That sort of thing plays havoc with branch and bound.


--
Michael   henne...@mail.cs.ndsu.nodak.edu
"Occasionally irrational explanations are required"  --  Luke Roman


Please do not quote boilerplate.

--
Michael   henne...@mail.cs.ndsu.nodak.edu
"Occasionally irrational explanations are required"  --  Luke Roman

Re: bpp plus type constrain

[Michael Hennebry]

ird variable in z[i,j,ti] but
in this latter I would get that i can be of each type while each i is just
one type.
Any tips?

Il giorno mer 4 ott 2023 alle ore 20:08 Michael Hennebry <
henne...@web.cs.ndsu.nodak.edu> ha scritto:


On Sat, 30 Sep 2023, Leonardo Corato wrote:


param m := 6;
param w := 1 50, 2 60, 3 30, 4 40, 5 40, 6 40;
--> param t := 1 A,  2 B , 3 B, 4 C, 5 C, 6 C;
param c := 100;

end;

I have to add a constraint so that the number of types for every bin is
limited to maximum 2.

Each bin can contain a number of the same type of items (i.e. A) or max 2
different types (i.e. A and C).
it is not regarding the number of items, of course, I can have multiple
items.


--
Michael   henne...@mail.cs.ndsu.nodak.edu
"Occasionally irrational explanations are required"  --  Luke Roman

Re: bpp plus type constrain

[Michael Hennebry]

On Sat, 30 Sep 2023, Leonardo Corato wrote:


param m := 6;
param w := 1 50, 2 60, 3 30, 4 40, 5 40, 6 40;
--> param t := 1 A,  2 B , 3 B, 4 C, 5 C, 6 C;
param c := 100;

end;

I have to add a constraint so that the number of types for every bin is
limited to maximum 2.

Each bin can contain a number of the same type of items (i.e. A) or max 2
different types (i.e. A and C).
it is not regarding the number of items, of course, I can have multiple
items.


If you want the types to have names, they will have to be a set.
You could just give them indices.
You will need a 2D boolean array indexed by item and type.
Once you have that, the rest should be obvious.

--
Michael   henne...@mail.cs.ndsu.nodak.edu
"Occasionally irrational explanations are required"  --  Luke Roman

Re: Nonlinear constraint in MPS format

[Michael Hennebry]

On Tue, 18 Jul 2023, Prabhu Manyem wrote:


I have a non-linear model in AMPL format (which is very similar to
GMPL format)... I would like to convert this to free-MPS format..
Unfortunately,  glpsol  is unable to convert non-linear models to
MPS.. (And the free version of AMPL which I have does NOT allow file
conversions).

The objective function is linear..  Most of the constraints are
linear, except one constraint which is non-linear..  The single
non-linear constraint looks like this:


My understanding is that standard MPS allows
for linear constraints and objectives only.
There are extentions allowing quadratic objectives and constraints.


ax + b(x)(x) + c(x)(x)(x) + d/x + e/x/x + f/x/x/x = C.


I know of no extention that allows seven distinct, -3..3, powers of x.



If we remove the constraint above, then we have an LP.



My question -- Is it easy to edit the MPS file obtained above, and
input the single non-linear constraint?

Or, is there any other way to obtain an MPS file for the entire
non-linear model?


No.
No.

--
Michael   henne...@mail.cs.ndsu.nodak.edu
"Occasionally irrational explanations are required"  --  Luke Roman

Re: [Fwd: Integer solutions]

[Michael Hennebry]

On Wed, 18 Jan 2023, Andrew Makhorin wrote:


 Forwarded Message 

Date: Tue, 17 Jan 2023 20:33:01 -0800
Subject: Integer solutions
To: 'Help-glpk@gnu.org' 
From: neillcl...@gmail.com

Re: [Fwd: Inquiry about using GNU MathProg]

[Michael Hennebry]

Traditionally, the way to represent a subset
of edges has been an array of booleans.
As there appear to be multiple subsets of edges,
an array of arrays of edges might be needed.

A path represented as a sequence of nodes is hard to exploain to a solver.

--
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

Re: Linear Program Optimal Extreme Points

[Michael Hennebry]

My first thought on such a task is to fix all variablee,
structural and otherwise, with nonzero reduced costs.
Unless using exact arithmetic,
that is an interesting task in itself.
Even so, I'd expect it to be better than using
a single linear constraint to implicitly fix them.

A better tactic might be to take a step back
to the reason you want them.

--
Michael   henne...@web.cs.ndsu.nodak.edu
"I was just thinking about the life of a pumpkin.
Grow up in the sun, happily entwined with others,
and then someone comes along, cuts you open, and rips your guts out." -- Buffy

Re: GLPK memory problem

[Michael Hennebry]

This is a bit late.

On Wed, 4 May 2022, Domingo Alvarez Duarte wrote:

You are right about the maximum index is limited by using an 32 bits integer 
but that doesn't mean that the memory allocation is also limited, we can have 
several GigaBytes of allocated memory on 64 bits platforms and still have 
less that 2^32 indices.


GLPK's xmalloc and xcalloc each take an int as its parameter.
Most ints can represent up to 2**31-1 .

Changing their parameters and a small amount of other code
would likely enlarge the available memory.
It would not solve the indexing issue.

xmalloc and xcalloc go through some gyrations to
ensure that the memory requested is a multiple of 16.
This seems unnessary.
The stated reason is already incorporated int malloc and calloc.

malloc and calloc return either NULL or
a pointer to suitably aligned memory.
Even if an odd block is requested,
there is no way for the immediately following byte to be allocated.

The code likely does little harm.
I'd remove it to reduce the code size.

--
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

Re: [Fwd: GLPK Linear Programming solver]

[Michael Hennebry]

From: Prabhu Manyem 

I get an optimal solution with the SAME objective function value, but
now, some variables are NOT integers... I get a fractional solution.

Why the difference between the 2 methods?
How to fix this problem for the command line execution of GLPK?


Since they have the same objective function,
both solutions qualify as optimal.
You did not ask for an integer solution,
--nomip makes that clear,
so there was no reason for you to get one.
glp_simplex does not guarantee an integer solution either.
For that you need glp_intopt .

--
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

RE: [Fwd: Discussion on GLPK]

[Michael Hennebry]

I expect that 50 million wss not quite arbitrary.
If GLPK runs out of real RAM,
'twill become grindingly slow running from swap.
Even with enough RAM, the time required is superlinear in problem size.

On Tue, 19 Apr 2022, Meketon, Marc wrote:


Typically when I see that many coefficients, it suggests that you need to 
reformulate your problem.


+1

That said, if you must:

Use the API.
Start with a subset of the constraints.
Include variable bounds and equalities.
repeat
Solve the reduced problem.
If all constraints are satisfied:
done
Add a violated constraint
forever

Major details are left as an exercise for the reader.


My guess is that this is the fastest solution.
Another possibility is to recompile GLPK with a larger limit.
My guess is that you will discover that 50 million was not a bad choice.

Yet another possibility for the skilled, brave or foolish
programmer is to rewrite GLPK to use mostly floats.
Simple variables and 1D array can still be doubles,
but 2D arrays become arrays of floats.
'Tain't just a matter of changing types.
Some thresholds will need to be changed.
Arithmetic should probably be done with double intermediates.
Also, GLPK is written in C89.
It's been a long time since I looked at the GLPK code.
I'm not sure what if anything GLPK does to deal with some of the
more interesting things some platforms do with floating point arithmetic.
Some platforms use long doubles for all floating point temporaries.
Often that just adds to the accuracy.
Sometimes the result is double rounding.
When done badly, as in the case of at least some versions of gcc,
one can get truly anomalous results: values that, according to the C,
are computed identically turn out to be unequal.
C99 introduced the types float_t and double_t
to help deal with the situation.
If you want to use them, you will need to use at least C99
or define float_t and double_t as part of your configuration.

BTW I've been assuming that the problem is a pure LP.
If it's an integer problem, lots of luck.
Reformulation would really seem to be in order.

--
Michael   henne...@web.cs.ndsu.nodak.edu
"Well, before my sword can pass all the way through your neck, it has
to pass *half way* through your neck. But before it can do *that*, it
has to first pass *one-fourth* of the way through your neck. And
before it can do *that*"  -- Ray Radlein quoting Zeno, Warrior Princess

Re: [Fwd: identifying infeasible problem without using the LP presolver]

[Michael Hennebry]

On Mon, 21 Mar 2022, Andrew Makhorin wrote:


 Forwarded Message 
From: Will Tipton 
To: help-glpk@gnu.org
Cc: John Rice 
Subject: identifying infeasible problem without using the LP presolver
Date: Mon, 21 Mar 2022 11:15:44 -0400



Running without the presolver usually works great. However, we can't
rely on the results in this case, because the simplex algorithm
returns an OK error code even when it fails to find a feasible
solution.


If the presolver is not used,
glp_simplex will return 0 iff it was able to do its job.
That includes discovering that the problem has no solution.
To get the desired information, use glp_get_status.

If the presolver is used,
glp_simplex will return 0 iff it was able to do its job
and the presolver did not determine that
the problem was primal or dual infeasible.

--
Michael   henne...@web.cs.ndsu.nodak.edu
Electic cars run on coal.

Re: specially ordered sets variables in Mathprog

[Michael Hennebry]

On Tue, 15 Mar 2022, Tommaso Cucinotta wrote:

I'd like to know whether Mathprog supports (or is there any plan to support) 
SOS (special ordered sets) variables, at least type 1.


I often use mathprog and glpsol to convert MILP problems (actually, BLP 
mostly) for other solvers (CBC, CPLEX), and I'm seeing these other solvers 
support these types of variables, what makes me think that there might be 
some advantages in formalizing a problem this way, as perhaps the solver 
might be quicker in scanning through the possible branches etc... I mean, 
using the SOS1 native formalization, instead of equivalent formulations as in


As noted by wikibooks, if one has binary variables,
SOS1 is equivalent to a single additional linear constraint.

My understanding is that some solvers that will handle
SOS1 constraints on continuous variables directly
without auxillary variables, but I do not know which.


https://en.wikibooks.org/wiki/GLPK/Modeling_tips#Special_ordered_sets


--
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

Re: [Fwd: gmpl question]

[Michael Hennebry]

On Fri, 17 Dec 2021, Andrew Makhorin wrote:


 Forwarded Message 
From: Davor Ocelic 
To: m...@gnu.org
Subject: gmpl question
Date: Fri, 17 Dec 2021 10:07:38 +0100



In the glpk example `assign.mod`, the constraint is that
an agent can have only one task assigned:

s.t. phi{i in I}: sum{j in J} x[i,j] <= 1;
/* each agent can perform at most one task */

I would need to change this rule so that an agent doesn't
have a limit on number of tasks, but all tasks need to be
distributed among a limited number of agents. (For example,
distribute the 8 tasks in the example to 4 agents).


Is there a reason not to just drop the constraint?

--
Michael   henne...@web.cs.ndsu.nodak.edu
I disapprove of winter, but winter doesn't care.

Re: [Fwd: Feeding an initial feasible solution to GLPK for MILP in CVXPy]

[Michael Hennebry]

On Thu, 9 Sep 2021, Andrew Makhorin quoted "Vasebi, Saeed [JJCUS]" 
:


I have a MILP problem in GLPK, using CVXPy library. GLPK quickly finds
a primary solution (optimal but not integer). But when GLPK switches
to branch-and-cut to find an optimal integer solution, it moves very
slowly. The main reason is
 that GLPK does not find any feasible integer solution after many
iterations (see the below log). I can use a simple heuristic algorithm
to find an initial feasible and integer solution, which can help GLPK
to quickly eliminate non-optimal branches. I am wondering
 if there is any way to feed this initial feasible integer solution to
GLPK, or its objective value?  


It's clunky, but I think it can be done with the GLP_IHEUR callback.
Failing that, I think that you can just add a constraint.

--
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

Re: Constraint on a binary variable

[Michael Hennebry]

On Wed, 30 Jun 2021, Philippe Jugla wrote:


In my model, I have a variable "p" which has an upper bound pmax := 2.5 and a 
lower bound pmin := -2.5.
I would simply like to add a binary variable "sign" which takes the values :

1 if variable p is positive
0 if variable p is negative (or vice-versa)


A solution is the convex hull of two line segments in (sign, x)-space:
(0, -2.5) (0, 0) and
(1,0) (1, 2.5)

This is 2-dimensional and the parallelogram is easily drawn.
Two of the sides are 0<=sgn<=1 .
The other two are -2.5 <= p - 2.5*sign <= 2.5 .

No need to play games with the objective function.

--
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

Re: [Fwd: Constraint not respected]

[Michael Hennebry]

From: Gioia Lorusso 

Hi GLPK team,I am using GLPK and I am struggling in understanding why
an upper bound constraint is not respected. 
I have submitted a question on Stack Overflow but I was not able to
find an answer. This is my question https://stackoverflow.com/question
s/67982099/glpk-upper-bound-constraint-does-not-work-properly , I
reported there my problem details and the GLPK output. Could you check
it and possibly help me in understanding why the constraint c1 is not
respected? Is there any kind of "relaxation" that I can avoid/forbid?
Thanks a lot in advance for your help, 


As a guess, your exposition is wrong.
To make such errors less likely,
try replacing expression <= 7200 with
Q = expression
Q <= 7200

In case you are not handing GLPK the problem you think you are,
have GLPK print out the problem.

--
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

Re: Solver delivers wrong answer when 2 constraints are close

[Michael Hennebry]

I suspect the best value for eps might be sqrt(DBL_EPSILON),
usually 2**-26, roughly 1.6*10**-8 .

If a model requires distinguishing between 1-eps and 1+eps,
another model might be in order.
Not a lot of generic advice can be given,
that said, X >= L1, X>= L2 can always become X>=max(L1, L2).


--
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

Re: Small program that seems to loop

[Michael Hennebry]

The problem seems to be that lack of an objective function.
In the transition from branch and bound to branch and bound and cut,
bound lost billing: branch and cut.
With an all-zero objective function, the solver cannot do bounding.
Every solution will be dual-degenerate.
That messes up selection of entering variables for dual pivots.

Try giving the problem an arbitrary objective,
perhaps index numbers or their recipricols.

--
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

Re: GLPSOL in webassemby faster than native ?

[Michael Hennebry]

On Thu, 1 Oct 2020, Domingo Alvarez Duarte wrote:

But in reality it seems that musl/qsort results in "stable sort" but actually 
for hashi.mod and tiling.mod the order of the "tie-breaker" results in a lot 
shorter solving time.


Note that you have achieved consistency of result,
not necessarily consistently better performance.

--
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

Re: GLPSOL in webassemby faster than native ?

[Michael Hennebry]

On Thu, 1 Oct 2020, Heinrich Schuchardt wrote:


On 9/30/20 10:02 PM, Michael Hennebry wrote:

On Tue, 29 Sep 2020, Domingo Alvarez Duarte wrote:


I found why GLPK in wasm was faster with "--cuts" option than native,
it was due wasm using qsort from muslc that is a "stable sort", I've
added it to my GLPK repository and running all models in the
"examples" folder only "color.mod" produces a different solution (that
seems to be valid anyway).


My expectation is that all sort algorithms produce the same result if
you supply a sort key that is different for all elements.


In the case of ties, tie-breaking matters.
For a stable sort, the tie-breaker is the original position.

--
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

Re: GLPSOL in webassemby faster than native ?

[Michael Hennebry]

On Tue, 29 Sep 2020, Domingo Alvarez Duarte wrote:

I found why GLPK in wasm was faster with "--cuts" option than native, it was 
due wasm using qsort from muslc that is a "stable sort", I've added it to my 
GLPK repository and running all models in the "examples" folder only 
"color.mod" produces a different solution (that seems to be valid anyway).


Michael Hennebry wrote:


Roadblocks include the toolchain and the system libraries.



The math library can matter.



How did you find it?

--
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

Re: GLPSOL in webassemby faster than native ?

[Michael Hennebry]

On Sat, 26 Sep 2020, Domingo Alvarez Duarte wrote:

I did a revision of the usage of "glp_long_double" see here 
https://github.com/mingodad/GLPK/commit/4941d1633e52b802bdc5f102715ac3db25db5245




Revised usage of glp_long_double, now it does solve hashi.mod and tiling.mod 
faster with "--cuts" option but hashi.mod without it's a lot slower.




- Standard glpsol  => 67.6 secs

- glpsol with some "long double" => 3.1 secs


I'd expect strategic use of long double to affect accuracy,
but not to have a consistent effect on speed.

Iterative refinement is one place where computing
with extra precision would be especially useful.

Note that long double=double*double raises at least three possibilities:
The product is done as double*double and assigned to long double.
The product is done as long double*long double and
converted to double before being assigned to long double.
The product is done as long double*long double and assigned to long double.
Casting a factor to long double would ensure the third.
The second really should not happen, as the product is a sub-expression,
but I would not be surprised to se it.

Storing some things as floats could speed up memory bound computations.
The constraint matrix comes to mind.
An all-integer constraint matrix with absolute values
less than 16 million could be represented exactly.
Storing them as 32-bit ints would extend the range..

Matrix factors might not be so good an idea.
It might work, but the criteria for detecting
singularity would likely have to be relaxed.

--
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

Re: GLPSOL in webassemby faster than native ?

[Michael Hennebry]

On Fri, 25 Sep 2020, Andrew Makhorin wrote:


Why do you want glpk to produce absolutely identical results on
different platforms? This has no practical sense.


In some cases, it does make sense,
but in C89 might be difficult to achieve.
If the different platforms have effectively
identical floating point processors,
getting identical numerical results should be possible.
If not, it suggests bugs or a misunderstanding.
Practicality is another is another issue.

Roadblocks include the toolchain and the system libraries.
C, especially C89, allows compilers plenty of wiggle room.
Removing it might not be possible in C89,
though I think it is in C99.
Even in C99, constants can be tricky.
The compiler has a choice between
evaluating at compile time or at run time.
On a native compiler, the distinction is usually unimportant.
On a cross-compiler, it can matter.

The math library can matter.
IEEE precisely defines square root,
but not trig functions, log or exp10.
C89 does not precisely define square root.
Does GLPK use any of those?
They would not necessarily have to be used in computing a solution.
Using them to score prospective B nodes could cause differences.

Similarly, the IO library can matter.
When reading a floating point number,
scanf has wiggle room.

Removing the above roadbloacks,
even for different platforms on the same machine might be difficult,
but if accomplished, would make a useful check on correctness.

--
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

Re: GLPSOL in webassemby faster than native ?

[Michael Hennebry]

On Thu, 24 Sep 2020, Domingo Alvarez Duarte wrote:

I just got glpsol with "long double" working and add binaries for anyone that 
want to test then here https://github.com/mingodad/GLPK/releases


As noted there it'll benefit from tuning the constants in src/glpk_real.h

Any help/suggestion/comment is welcome !


Note that using long doubles everywhere
would slow down a memory bound computation.
Fetching more data would be required.

One might introduce glp_double_t.
C99 uses double_t for the type in which unnamed
intermediate results of double calculations are stored.

Use glp_double_t for locals that are not arrays,
especially running totals.
Do the casts to ensure that desired calculations
are actually done in glp_double_t.

--
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

Re: GLPSOL in webassemby faster than native ?

[Michael Hennebry]

On Tue, 22 Sep 2020, Domingo Alvarez Duarte wrote:

Due to the big difference in solver time how could we figure out what's is it 
in order to use this knowledge to improve the native solver time ?


I mean what debug/verbose options could help us have a clue ?


I expect the answer is none.
My guess is that neither platform is inherently better than the other.
Which small roundings will be better doubtless depends
on the particular problem and version of GLPK.
Andrew insists on C89.
That pretty much eliminates control over how floating point is done.

double x=1./3., y=1./3.;
C89 does not require x and y to have the same value.
IEEE arithmetic would, despite possible double rounding.

Even with IEEE, platforms are allowed to evaluate floating point
expressions with a precision larger than required by the expressions.
They are not required to be consistent.
double x=2.0+DBLE_EPSILON-2.0, y=2.0+DBL_EPSILON-2.0;
x could be 0 or DBLE_EPSILON, as could y.
They need not be the same.
Once upon a time, that was a real problem with gcc.
For C89, it might still be.

With a lot of casts to long double and sufficient
care in the representation of constants,
Andrew might be able to get consistent behaviour between
IEEE platforms with matching doubles and long doubles.

It's been a while since I looked at any GLPK code.
My expectation is that at least some of it, e.g. dot product, is memory bound.
In such a case, explicitly using long doubles would
not slow it down and could improve its accuracy.
Possibly Andrew already does that.
I haven't looked lately.

--
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

Re: [Help-glpk] Operand following / has invalid type

[Michael Hennebry]

On Thu, 10 Sep 2020, Andrew Makhorin wrote:


On Wed, 2020-09-09 at 18:17 -0300, yami...@cock.li wrote:



I'm trying to make a program that populates a binary matrix keeping
as 
many blank lines as possible, e.g.


Add another variable for each row in the binary matrix:
z[row]>=m[row, col]
minimize its sum.
The z's need not be binary.

It can be done with a single z,
but I expect user-defined cuts would be necessary.
Note that GLPK assumes cuts are not mathematically necessary.
GLPK might return a solution you deem infeasible.
In that case, you would neeed to add a cut and rerun.
Keeping the previously discovered cuts would not be automatic.


Since I know the sum of the lines won't be too big I decided to use
an 
approach based on division, but I'm getting a "operand following /
has 
invalid type" error.

/* binary matrix */
var m{x in X, y in Y} binary;
/* minimizes total (sum of line)^-1, a full line is better than two 
half-full lines*/
minimize maxEmpty: sum{x in X} 1/(1 + sum{y in Y} m[x,y]);


This can be done, sort of.
Again you would need an auxillary variable for each matrix row.
I expect the additional constraints
could be inserted with the original set.

Again it coulod be done with a single z
and the same complications are before.


In constraints and objectives you can divide only by a constant
expression. In your case you divide by a linear form that leads to a
non-linear objective function, which is not allowed. Probably you need
to reformulate your model.


--
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

Re: Excessive copies of set elements in GMPL

[Michael Hennebry]

On Fri, 24 Jul 2020, Andrew Makhorin wrote:


The issue can be illustrated by the following example:

 for (i = 0; i < 100; i++)
 for (j = 0; j < 100; j++)
 for (k = 0; k < 100; k++)
   if (j == i+1 && j == j+2)
 foo(i, j, k);

Would you expect the C compiler to optimize this fragment in order not
to perform obvious excessive computations?


My recollection is that gcc does make that
kind of optimization for linear constraints.
At the very least, most optimizing compilers
would hoist the j==i+1 test ouside the k loop.
That might be just enough to allow it to run in a practical amount of time:
a few trillion cycles plus whatever foo requires.

That said, the coder can, as noted,
provide equivalent code that requires no optimization.

--
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

Re: Excessive copies of set elements in GMPL

[Michael Hennebry]

On Tue, 21 Jul 2020, Domingo Alvarez Duarte wrote:


Do you have any example doing what you are talking about ?

In theory it should work.

Right now it process all models in the "examples" folder and the output is 
identical to the original GLPK/GMPL except that uses less memory and is 
slightly faster.


Things like the GMPL equivalent of { (a,b,c) in A x B x C : b=a+1, c=b+2 }
My understanding is that the current GMPL processor will form A x B x C
before applying the filtering.
If A, B and C have 100 items each, the inefficiency can probably be lived with.
If they have 1,000 items each, it will be grindly slow, assuming it finishes.
If they have 10,000 items each,
the set will be to big for the handler to store.

Of course, done right, a set of 10,000 3-tuples should not be a problem.


On 21/7/20 15:24, Michael Hennebry wrote:

Are these changes supposed to deal with things like nested set iterations?


--
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

Re: Excessive copies of set elements in GMPL

[Michael Hennebry]

Are these changes supposed to deal with things like nested set iterations?

--
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

Re: GLPK and OPENMP - GLP_SIMPLEX running concurrently

[Michael Hennebry]

On Wed, 13 May 2020, Sierra Ansuas, Juan Pablo wrote:


The program is returning correct values as long as the call to glp_simplex is 
enclosed inside an OMP CRITICAL region. This is the only part requiring a 
mutex. The rest of the glp_* functions are called concurrently by several 
threads with no issue at all.


Globals and statics used directly by GLPK.
Globals and statics used by things GLP calls.

--
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

Re: [Fwd: Need help in Fixing GUSEK Code]

[Michael Hennebry]

On Fri, 10 Apr 2020, Andrew Makhorin wrote:


 Forwarded Message 
From: sahani rathnasiri 
To: help-glpk@gnu.org
Subject: Need help in Fixing GUSEK Code
Date: Fri, 10 Apr 2020 19:08:39 +1000


...

I am running code in GUSEK and I need to define three indexes. I am
getting a syntax error. Please help me fix this.
My constraint;
subject to order_quantity_constraint_min {i in I, j in J, n in N: i
<= t, j <> 2 and n <= r}: Z[i,j]* Qmin[i,n] <= a[i,n];

The result I receive in NEOS;

amplin, line 50 (offset 2865):
        syntax error
context:  subject to order_quantity_constraint_min {i in I, j in J, n
in N: i <=  >>> t, <<<  j <> 2 and n <= r}: Z[i,j]* Qmin[i,n] <=
a[i,n];


Presumably the offending t is supposed to be j or n.

--
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

Re: Gmpl How can I do this?

[Michael Hennebry]

On Thu, 26 Mar 2020, siirto1 wrote:


I am trying to do some simple gmpl model but as a complete beginner I noticed I 
cannot do it.


THe issue appears not to be representing a model in GMPL,
but getting a model to represent.


   col1 col2 col3
row1  x
row2  xx
row3  xxx

Assign numbers 1..6 to the x cells so that every number has different row and 
col than the previous number.


I suggest 2 2D arrays of binary values.
xincol[x, c] == 1 iff x in column c.
xinrow[x, r] == 1 iff x in row r.

Constraints are left as an exercise for the reader.

--
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

Re: Help with slow model translation

[Michael Hennebry]

On Fri, 21 Feb 2020, Greg Gruber wrote:


I came across this on the wikipedia entry: " The take-home message is that
nested set iterations should be avoided where possible, as these greatly
expand the dimensionality and size of the model space to be processed.",
and it discusses a case on the OSeMOSYS energy model where the execution
time was reduced from 15 hours to 9 minutes by a reformulation.


I think it refers to the MathProg equivalent of something like this:
S=1..1000
T= { (x, y, z): x in S, y in S, z in S, y=x+1, z=y+1 }

--
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

Re: Off-by-one error when solving integer linear program

[Michael Hennebry]

On Tue, 17 Dec 2019, Michael Hennebry wrote:


On Tue, 17 Dec 2019, Matthew Keeter wrote:

I used GLPK to solve a problem in this year?s Advent of Code [1], and 
noticed

that it produces a very slightly wrong answer for one of the examples.


As noted elsewhere, an upper bound of a trillion
requires more precision than GLPK will normally require.
I do not get an integer objective.



The correct answer is 82892753, and I?m getting 82892752.


The correct answer is 82,892,753.14  .



From a two-step process, I get 82,892,800-47=82,892,753 unit of fuel

from 1,000,000,000,000-99=999,999,999,901 units of ore.

For the second step, I solved for differences with the first step solution.
The RHSs ranged from -17,520 to 24,000.
None of the structural variables were at their bounds.

aximize out: produced_fuel

Subject to
NZVS: 5 equation1 -29 equation3 -7 equation9 >=  2200
ORE: -157 equation1 -165 equation2 -179 equation5 -177 equation6 -165 equation8 +1 
consumed_ore >=  -381000
DCFZ: 6 equation2 -7 equation7 -3 equation9 >=  24000
FUEL: 1 equation3 -1 produced_fuel >=  0
XJWVT: -44 equation3 +2 equation7 >=  3200
KHKGT: -5 equation3 +8 equation9 >=  0
QDVJ: -1 equation3 +9 equation4 >=  10
GPVTF: -9 equation3 -1 equation4 +2 equation8 >=  -490
HKGWZ: -48 equation3 -12 equation4 +5 equation6 -5 equation9 >=  3120
PSHF: -8 equation4 +7 equation5 -7 equation7 -10 equation9 >=  -17520
ore_consumption: 1 consumed_ore <=  0
bounds
produced_fuel >= -82892800
consumed_ore >= -1
equation9 >= -51808000
equation8 >= -377623000
equation7 >= -182364
equation6 >= -869683000
equation5 >= -190818
equation4 >= -9210310
equation3 >= -82892800
equation2 >= -215348
equation1 >= -553309000
integer
produced_fuel
consumed_ore
equation9
equation8
equation7
equation6
equation5
equation4
equation3
equation2
equation1
end

--
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

Re: Off-by-one error when solving integer linear program

[Michael Hennebry]

On Wed, 18 Dec 2019, Matthew Keeter wrote:


Ah, I just realized that you only see Part 2 if you're logged in and have
solved Part 1.

The goal of Part 2 is to maximize production of the FUEL element, starting
with 1 trillion
units of ORE; that's the problem that I'm solving in my LP file.


That helps some.
I'm seeing the 1 trillion now.
Where is the other data?


Since each reaction occurs an integer number of times (and both consumes and
produces an integer number of reagents / products), the answer should be an
integer.


82,892,753.14 was a joke, son.

--
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

Re: Off-by-one error when solving integer linear program

[Michael Hennebry]

On Tue, 17 Dec 2019, Matthew Keeter wrote:


I used GLPK to solve a problem in this year?s Advent of Code [1], and noticed
that it produces a very slightly wrong answer for one of the examples.


As noted elsewhere, an upper bound of a trillion
requires more precision than GLPK will normally require.
I do not get an integer objective.

I'm really confused about what problem is being solved.
The given ILP does not resemble the problem of producing one unit of fuel.
For the puzzle data I found, one would have 59 variables (columns),
one for each reaction.
I saw mention of more than one part,
so I expect I am missing something.


It?s an integer linear programming problem, pasted below the fold in CPLEX LP 
format.

The correct answer is 82892753, and I?m getting 82892752.


The correct answer is 82,892,753.14  .

--
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

Re: Off-by-one error when solving integer linear program

[Michael Hennebry]

On Tue, 17 Dec 2019, Michael Hennebry wrote:


What problem are you trying to solve?
If it's not this one:
71 ORE => 8 CNZTR


Oops.  Should have benn 171 ORE 

Now I get 2,210,736 which I now see is the value
listed above the example I mistook for puzzle data.

I infer that "To play" includes getting a look puzzle data.

I have a python script that turns the puzzle data into glpsol --lp data.
It works for examples.
For the puzzle data, I get 399063 .
Where are you getting your correct value?

--
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

Re: Off-by-one error when solving integer linear program

[Michael Hennebry]

What problem are you trying to solve?
If it's not this one:
71 ORE => 8 CNZTR
7 ZLQW, 3 BMBT, 9 XCVML, 26 XMNCP, 1 WPTQ, 2 MZWV, 1 RJRHP => 4 PLWSL
114 ORE => 4 BHXH
14 VRPVC => 6 BMBT
6 BHXH, 18 KTJDG, 12 WPTQ, 7 PLWSL, 31 FHTLT, 37 ZDVW => 1 FUEL
6 WPTQ, 2 BMBT, 8 ZLQW, 18 KTJDG, 1 XMNCP, 6 MZWV, 1 RJRHP => 6 FHTLT
15 XDBXC, 2 LTCX, 1 VRPVC => 6 ZLQW
13 WPTQ, 10 LTCX, 3 RJRHP, 14 XMNCP, 2 MZWV, 1 ZLQW => 1 ZDVW
5 BMBT => 4 WPTQ
189 ORE => 9 KTJDG
1 MZWV, 17 XDBXC, 3 XCVML => 2 XMNCP
12 VRPVC, 27 CNZTR => 2 XDBXC
15 KTJDG, 12 BHXH => 5 XCVML
3 BHXH, 2 VRPVC => 7 MZWV
121 ORE => 7 VRPVC
7 XCVML => 6 RJRHP
5 BHXH, 4 VRPVC => 5 LTCX
what problem is it?

I get 1,341,336 from ILP with GLPK.
One variable for each of 17 reactions.
I have no idea why you would need an explicit bound on ORE consumption.
A trillion seems a bit excessive.

From where are you getting your correct answer?


--
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

Re: next question - find some element of a set

[Michael Hennebry]

I think the answer is no:
GMPL does not believe in the axiom of choice.

--
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

Re: Use more precision for bounds, GMP

[Michael Hennebry]

On Wed, 27 Nov 2019, Daniel Jour wrote:


Hi, I have a problem whose bounds are values which need (really) a lot
of precision.  Much more than double can offer.  I've handled these
values so far with GNU MPFR, which can AFAIK convert to GNU GMP types
which are (?) internally used by GLPK if it's built with support for
that.


You are barking up a very large tree.
My first thought is to try to reformulate the
problem to remove the need for such precision.


Looking through the source I see that the functions to set bounds as
well as the structures (for example struct GLPROW) use double. Thus I
guess I'd need to change that at least ...


It means the variables have to be GMP types,
otherwise the precision of the bound is meaningless.


Given I have no knowledge (yet?) about the internal complexities of
GLPK ... how hard do you estimate it to be to change GLPK to allow
bounds set from GMP numbers?


GLPK already includes an exact solver.
Not surprisingly, it is slow.
IIRC its input is required to be ordinary doubles,
so getting the desired bounds would require some effort, e,g,:
xUpHi=...
xUpLo=...
x<=xUpHi+xUpLo

The usally method for using it
is to run the inexact LP solver first
and use that result to start the exact solver.

--
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

Re: Redefine parameter in Monte Carlo analysis

[Michael Hennebry]

On Tue, 12 Nov 2019, Guidati  Gianfranco wrote:


I am using GLPK to optimize an energy system model for Switzerland. Lots of 
parameters such as costs or efficiencies are defined in a dat file. Now I want 
to systematically vary some of these parameters using a Monte Carlo approach. 
The easiest way to do this would be to just create a small addendum to the dat 
file that redefines / overrides the parameter values that were previously 
defined in the dat file, and to paste these two together. Unfortunately, that 
doesn't work, the solver just complains that a parameter was already defined.


Include parameters Xnormal and Xadjust along with parameter X.
Read in Xnormal and Xadjust instead of X.
Have X computed from Xnormal and Xadjust.

--
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

Re: [Help-glpk] ERROR = basis matrix is singular to working precision

[Michael Hennebry]

On Thu, 30 Aug 2018, Garcia, Christophe wrote:


I have a problem understanding GLPK behavior with my model when I get this 
error message :

GLPK Simplex Optimizer, v4.65
5157 rows, 5980 columns, 892762 non-zeros
 0: obj =  0.0e+000 inf =  2.300e+001 (23)
Perturbing LP to avoid stalling [199]...


GLPK is temporarily modifying yur problem so that it can keep going.


Warning: basis matrix is ill-conditioned (cond = 1.13e+015)
Warning: basis matrix is ill-conditioned (cond = 1.45e+015)
Warning: basis matrix is ill-conditioned (cond = 1.48e+015)
Warning: basis matrix is ill-conditioned (cond = 2.2e+014)
Error: basis matrix is singular to working precision (cond = 1.54e+017)

I thought it could be numeric overflow so I added a divider to all my values in 
the constraints and the objective function but it did not solve my problem


Condition numbers are dimesionless.
Such scaling does not affect them.
There is scaling that might help,
but I think that GLPK does that on its own.


Q1 : what "matrix is ill-conditioned" means ? do I have any kind of 
inconsistencies in my constraints ?


The condition number is equivalent to the magnitude
of a matrix time the magnitude of its inverse.
It is a measure of how much errors in the
inputs could be magnified in the output,
even with exact arithmetic.
10**15=1000**5
1024**5=2**50


Q2 : what is this "working precision" ?


double precision is often 53 bits.
See above.


Q3 : what can be the source of this problem : my constraints ? my objective ?


Not your objective.

Two constraints, almost the same and both binding might produce this.

I'd suggest telling GLPK to use the dual simplex method.
If that does not work, I'd turn off preprocessing.
If that does not work, I'd try dropping constraints (not variable bounds)
until I got a solution.
If it's feasible, done.
Otherwise, use it as the basis from which to start the dual simplex method.


--
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] TRYING TO GET A NON-OPTMIAL SOLUTION OF A MIP MODEL.

[Michael Hennebry]

On Wed, 13 Jun 2018, Joshua Friedman wrote:


The technique you described of relaxing all but 1-2 days and fixing the
integer part sounds interesting. Are there any published works implenting
the technique. I am also working on a timetabling/student enrollment
problem at my college.


Probably, but I do not know of any.
Note that the particulars were selected for
ease of exposition rather than efficacy.
My suspicion is that starting in the middle would be more effective.

Another possibility is lagrangean optimization.
There are lots of articles on that.
The idea is that one drops enough constraints to make it easy to solve.
If the solution obtained works, well and good.
If not, adjust the objective function and try again.
The details are in the constraints dropped and subsequent adjustments.
Often constraints dropped usually allow the
problem to be broken into independent subproblems.

In any case, I'd try depth-first before anything too novel.

--
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] Slow performance on "Select minimum" task

[Michael Hennebry]

On Wed, 6 Jun 2018, Jan van Rijn wrote:


The way I interpreted your solution was that 'at least one y-value per
column will be >= 1'.
I don't see exactly which constraint makes sure that there will be exactly
one y-value per column 1
(which, again, we don't need if all values in M are >= 0).


You are correct.
The y's have no upper bound, not even one.


If M contains negative values, it could be that:
* an ideal solution would have multiple y-values per column bigger than
zero, and
* These values will not necessarily be one, but can take even higher values
(due to this GLPK gave an error message, and this is how I found out)


In the case of negative M's,

Adding SUM y[r,c] = 1
r

is sufficient.
The y's still do not need to be declared binary.

Being an added constraint, it might speed things up with positive M's.

--
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] Slow performance on "Select minimum" task

[Michael Hennebry]

On Tue, 5 Jun 2018, Jan van Rijn wrote:


2018-06-05 23:39 GMT-04:00 Michael Hennebry 
:


On Tue, 5 Jun 2018, Jan van Rijn wrote:



- M[r,c] should contain positive values (which guarantees that y[r,c] == 1

iff x[r] - SUM x[s] == 1)



I'm pretty sure that is not necessary.
the y's depend only on the x's and the order of the M values.
In any case, I think the zeros in your original problem
will not be much of an issue.




I should rephrase: The array should contain values >= zero.
(negative values are an issue, but these can be scaled away easily. )


I'm not sure where that is coming from.
The y's are determined by the x's and by sets
of rows determined by the order of the M values, not their signs.
Only one y value in a column can be one.

--
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] Slow performance on "Select minimum" task

[Michael Hennebry]

On Tue, 5 Jun 2018, Jan van Rijn wrote:


I need to add two things:
- It is my conjecture that there should be an additional constraint, i.e.,
y[r,c] > 0 (Otherwise non-selected rows could participate towards a lower
score)


Correct,


- M[r,c] should contain positive values (which guarantees that y[r,c] == 1
iff x[r] - SUM x[s] == 1)


I'm pretty sure that is not necessary.
the y's depend only on the x's and the order of the M values.
In any case, I think the zeros in your original problem
will not be much of an issue.
Consistent tie-breaking is important.

--
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] Slow performance on "Select minimum" task

[Michael Hennebry]

On Tue, 29 May 2018, Jan van Rijn wrote:


Yes, it is indeed a matrix of floats.



2018-05-29 15:45 GMT-04:00 Kevin Martin :



I have re-read your problem and I may have misinterpreted it. I thought
your matrix was binary, as in each element was in {0,1}, the sum condition
was supposed to be i:M(j,i)=0, which would be the sum of all the row
inclusion (x_j) variables where the Matrix element for the column was 0.
The idea being that if none of the rows corresponding to a are 0 selected,
the minimum of the column must be 1.

As I re-read your original email, I now think that each element may be
fractional somewhere in the closed interval [0,1]. If this is the case, I
think the problem may be quite hard, for general M, I can?t think of an
obvious way to formulate it better.


A similar mechanism still works:

y[r,c] >= x[r] - SUM x[s]
 s in Q[r,c]

x is binary
y need not be specified binary
Q[r,c] = { s : M[s,c]< M[r,c] }
The objective is SUM y[r,c]*M[r,c]
 r,c

The definition of Q assumes no ties.
Ties may be broken arbitrarily, but must be consistent.
You may turn M[s,c]< M[r,c] into a lexigraphic comparison
of (M[s,c], s) and (M[r,c], r) .

--
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] How to linearize a weighted average with a decision variable?

[Michael Hennebry]

On Tue, 24 Apr 2018, Matt wrote:


*max sum(i) { enabled[i] * value[i] * weight[i] } / sum(i) { enabled[i] *
weight[i] }*

*s.t. sum (i) enabled[i] = M*

- *value* is a vector of decimal numbers in [0, 1] (precomputed)
- *weight* is a vector of decimal numbers in [0, 1] (precomputed)
- *enabled* is a vector of either 0 or 1 (decision variable)


For linear constraints, there is a tranformation to an LP:
https://en.wikipedia.org/wiki/Linear-fractional_programming#Transformation_to_a_linear_program
It does not convert an integer problen to an integer problem.
My suggestion is to use it to get an LP-based bound, call it q.
Then maximize numerator - q*denominator as an IP.
If it's zero, you are done.
If it's negative, the true objective gives you another q.
If it's positive, you made a mistake.

You might need to explicitly bound the denominator.

--
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: Antonio Carlos Moretti <moretti+dated+1521124706.e2c...@ime.unicamp.br>]

[Michael Hennebry]

On Sun, 11 Mar 2018, Andrew Makhorin wrote:


 Forwarded Message 
From: Antonio Carlos Moretti 
To: help-glpk@gnu.org
Subject:
Date: Sat, 10 Mar 2018 11:38:24 -0300

Hello,
Is there any way to call glpk from a fortran program?


Probably.
I called FORTRAN 77 from C when doing my thesis in the 1980's.
According to Wikipedia, Fortran 2003 included C interoperability.
Fortran 2018, whenever it arrives,
is supposed to be even more interoperable.

I have no subsequence experience.

Getting the external names compatible
might require compiler or linker options.
For some reason, underscores_ are often involved.
I never understood why.

C does call by value.
At the time, my FORTRAN did call by reference, i.e. pointer.
My recollection is the the standard at the time
allowed either call by reference or by value-result.
The program was ill-formed if the difference mattered.
My guess is that this was handled in Fortran 2003.
If not handled by Fortran, a C wrapper function will work.

C array indices are most significant index first.
Fortran array indices are most significant index last.

I think that Fortran now has the equivalent of C structs.
If not, passing the appropriate member of a common block
woud be equivalent to passing a pointer to a struct.

If all else fails, my guess is that C++ wrapper functions would work.

extern "C" int fredC();

extern "FORTRAN"
int fredF()
{
return fredC();
}

--
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: Re: [Fwd: graceful tree labeling example]]

[Michael Hennebry]

On Thu, 5 Oct 2017, Heinrich Schuchardt wrote:


your model uses more integers than needed. This typically makes problems
harder to solve.

You just need the binaries gt, vx, and ex. All other variables can be
float. The constraints enforce that they will be integer.


Of course not labeling them integer implies that the
solver will not be able to use their integrality.

Constraint-enforced integer might be a useful variable type.
The solver would not need to branch on them,
but could use their integrality for things like Gomory cuts.

--
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] MathProg, glpk and C language

[Michael Hennebry]

On Wed, 4 Oct 2017, Lyndon D'Arcy wrote:


Below is some example code for reading MathProg using my extension:

 int status;
 char *buf = "var x1;\
 var x2;\
 maximize obj: 0.6 * x1 + 0.5 * x2;\
 s.t. c1: x1 + 2 * x2 <= 1;\
 s.t. c2: 3 * x1 + x2 <= 2;\
 end;";
 glp_prob *lp;
 glp_tran *tran = glp_mpl_alloc_wksp();
 status = glp_mpl_read_buffer_into_model(tran, buf, strlen(buf), 0);
 ck_assert_int_eq(status, 0);
   if (!status) {
 status = glp_mpl_generate(tran, NULL);
 if (!status) {
 lp = glp_create_prob();
 glp_mpl_build_prob(tran, lp);
 }
 }
 glp_mpl_free_wksp(tran);
 glp_delete_prob(lp);
 glp_free_env();


The example does not solve the problem or retrieve the solution.

--
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] MathProg, glpk and C language

[Michael Hennebry]

On Wed, 4 Oct 2017, john tass wrote:


One possible way I suppose that is to use the API's of Glpk inside that
function, using #include "glpk.h". But this way has the following drawback:
in order to declare a structural variable of my model, say X1, I have to
write something like glp_set_col_name(lp, 1, "x1"); That means that I
declare the X1 variable by a hard-code. But my model is quite large, having
hundreds of variables. In addition, I do not know in advance the exact
number of them since they should be created dynamically. As you understand


GLPK does not require you to name your variables at all.
Using GLPK's API, I only named variables if I wanted GLPK to print.
Even then, I generated the names with the program.
How else with a variable number of names?

With MathProg, my program would have trouble reading the solution.
What column was X[7]?
What name did X[7] have?
At the time, and maybe still,
how GLPK's MathProg generated names was not documented.

--
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] non-official updated version of glpk (4.63 pre-release)

[Michael Hennebry]

<
On Mon, 2017-08-07 at 10:18 -0500, Michael Hennebry wrote:


I get a zero-byte document.


Sorry. I don't know why that url doesn't work now.
Try http://www.ia.pw.edu.pl/~wogrycza/publikacje/artykuly/mymps87.pdf
It should work.


It does.

--
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] non-official updated version of glpk (4.63 pre-release)

[Michael Hennebry]

On Sun, 6 Aug 2017, Andrew Makhorin wrote:


On Sun, 2017-08-06 at 12:13 +0300, Andrew Makhorin wrote:



Interesting to note that exactly the same picture (cycling on two bases
near the optimum on solving LP with MPSX/370) is described in the paper:
W.Ogryczak, On practical stopping rules for the simplex method,
Math.Prog.Study 31 (1987), pp.167-174.


BTW, this article is freely available at:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.703.6576=rep1=pdf


I get a zero-byte document.

--
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: Re: Objective function defined with max, min.]

[Michael Hennebry]

On Fri, 6 Jan 2017, Andrew Makhorin wrote:


 Forwarded Message 
From: Alexey Karakulov <ankaraku...@gmail.com>
To: Michael Hennebry <henne...@web.cs.ndsu.nodak.edu>
Cc: Andrew Makhorin <m...@gnu.org>, help-glpk@gnu.org
Subject: Re: [Help-glpk] Objective function defined with max, min.
Date: Fri, 6 Jan 2017 19:46:31 +0200

Andrew & Michael,


Thanks a lot for the advice. I implemented binary variables, for f(x) =
max(x, 0). It seems to give a correct result, but works extremely slower
than LP problem. It takes like 10s for have a few dozen points with
binary variables, and I don't know how long for real problem with
hundreds of points.


How?
Details matter.
If you used a big-M method, how did you choose M?

--
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.

[Michael Hennebry]

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.

[Michael Hennebry]

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] Formulate a large scale linear programing model by reducing the number of similar constraints and keeping them all satisfied

[Michael Hennebry]

On Tue, 6 Sep 2016, Michael Hennebry wrote:


Let us name the constraints.



First, I am unclear as to what the exact model is.
This is what I got from yur first post:

The i SUMs run from 1 to N.
The j SUMs run from 1 to L.


Max SUM P_i*X_i
 i


Constraint A:

T + SUM K_j  <=   SUM Q*P_i*X_i
 j i


Constraint B:

SUM E_i*X_i <= D*SUM E_i
 ii


Constraints C_1 ... C_L

K_j >= SUM V_j_i*X_i - T   j in 1..L
i

T no explicit bound
0 <= X_i <= 1   i in 1..N
0 <= K_ii in 1..L



I suspect that with a bit of algrebra one
could get rid of the K_j's and T altogether.
That would leave the X_i's as the remaining variables.
The price would be an exponential number of constraints.
I'd expect the task of finding the most
violated constraint to not be very difficult.


No need to get rid of T.
Getting rid of the K_j's is easy:
Replace Constraint A and constraints C with

D:
T +  SUM   (SUM V_j_i*X_i - T)  <= SUM Q*P_i*X_i   for all S subsetof 1..L
j in S  i in 1..N

This is 2**L constraints.
For given values of X and T,
a most violated is D_S with S = { j in 1..L: SUM V_j_i*X_i - T > 0 }

--
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] Formulate a large scale linear programing model by reducing the number of similar constraints and keeping them all satisfied

[Michael Hennebry]

On Tue, 6 Sep 2016, usa usa wrote:


*   A:  "an exponential number of constraints." will cause "run out of
memory" error ? *


No.
The idea would be that the constraints could be generated from a formula.
Finding the most violated constraint would
mean finding the formula input that generates it.
Getting rid of the K_j's fixes the number of variables,
hence we are out of the realm of column generation.


I'd expect the task of finding the most

violated constraint to not be very difficult.


--
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] Formulate a large scale linear programing model by reducing the number of similar constraints and keeping them all satisfied

[Michael Hennebry]

Let us name the constraints.

On Sun, 4 Sep 2016, usa usa wrote:


On Fri, Sep 2, 2016 at 3:36 PM, Michael Hennebry <
henne...@web.cs.ndsu.nodak.edu> wrote:


First, I am unclear as to what the exact model is.
This is what I got from yur first post:

The i SUMs run from 1 to N.
The j SUMs run from 1 to L.


Max SUM P_i*X_i
 i


Constraint A:

T + SUM K_j  <=   SUM Q*P_i*X_i
 j i


Constraint B:

SUM E_i*X_i <= D*SUM E_i
 ii


Constraints C_1 ... C_L

K_j >= SUM V_j_i*X_i - T   j in 1..L
i

T no explicit bound
0 <= X_i <= 1   i in 1..N
0 <= K_ii in 1..L



On Thu, 1 Sep 2016, usa usa wrote:

Also, in my LP model, each constraint will introduce a new decision

variable.



That makes it trickier.  Look up column generation.

decVarK_j >= decVarX_i * constValue_i  - decVarT




Did you mean decVarK_j >= decVarX_i * constValue_j_i - decVarT  ?



*A:  It means decVarK_j >=  SUM E ( decVarX_i * constValue_j_i for i in
1...N) - decVarT  ?*


Is this supposed to be constraint C_j ?
Is E suposed to be there?  Should it have an index?


If I used the solutions from solving the model with part of the constraints

and then replace the "decVarX_i" and "decVarT" with the solution values
and
set

 decVarK_j = decVarX_i * constValue_i  - decVarT



Did you mean decVarK_j = SUM decVarX_i * constValue_j_i  - decVarT ?
  i

 *   A:  It means decVarK_j = SUM E( decVarX_i * constValue_j_i  for i in

1...N ) - decVarT ?*
 i



If decVarK_j is in the current LP, use that value.
Traditionally, values of non-explicit variables are often zero,
though other computations are possible.
Will most of the K_j's be zero?



*A:  No, the values of K_j depend on SUM E ( decVarX_i * constValue_j_i
for i in 1...N) - decVarT *



If not, most of the j-indexed constraints will be active.
In that case, you would still want an algorithm that
does not do as much work as solving the entire LP at once.
I have an idea, but will not guarantee it will work.
If you use max(0, decVarX_i * constValue_j_i - decVarT) ,


Should have been max(0, SUM decVarX_i*constValue_j_i - decVarT)
 i
Doesn't help.


all the nonzero decVarK_j's are likely to change with every iteration.
That said, for every feasible solution, changing each decVarK_j to
max(0, decVarX_i * constValue_j_i - decVarT)
will preserve feasibility and optimality.






*   A: I do not quite understand this. For j=1 ... L, if in one iteration,
I chose j =1 ... M with M is much smaller than L. For example, L = 10,
and M = 1000. So, in the LP model, I only have optimal solutions for the
constraints ofdecVarK_j >=  SUM E ( decVarX_i * constValue_j_i for
i in 1...N)*




*for j =1...M. *

*How can I use the solutions for j=1...M to change each decVarK_j to max(0,
decVarX_i * constValue_j_i - decVarT)  with j = 1... N ? *


I do not know that you can.
That was more or less the point.
When one does column generation,
one usually arranges for the unmentioned variables to be zero.
To do column generation, you will need to reformulate without the K_j's.
Replace them with something that you expect to be mostly zero.
You will almost certainly need to represent nonzero variables.

I suspect that with a bit of algrebra one
could get rid of the K_j's and T altogether.
That would leave the X_i's as the remaining variables.
The price would be an exponential number of constraints.
I'd expect the task of finding the most
violated constraint to not be very difficult.


--
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] Formulate a large scale linear programing model by reducing the number of similar constraints and keeping them all satisfied

[Michael Hennebry]

On Wed, 31 Aug 2016, usa usa wrote:


The problem is that the number of constraints of   decVarK_i for i=1 to L
and L can be very large, e.g. 100,.


I think that the given constraints were not what you really intended.


It means that it will have 100,000 constraints in the LP, which I want to
avoid.



How to combine them so that I can reduce the size of the LP model meanwhile
keeping all constraints satisfied ?


In general, you can't.
The usual solution is iterative LP.
Solve the problem with a subset of constraints.
If the solution satisfies all your constaints, you are done.
Otherwise select one or more violated constraints and resolve.
Rinse and repeat until you have a solution or fatigue sets in.
The tricky part is in the constraint selection.
Unless you are doing something silly like working from an explicit list,
it will be problem-specific.

--
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] quadruple precision

[Michael Hennebry]

On Wed, 1 Jun 2016, zephod wrote:


Does GLPK support quadruple precision for floating point operations? If yes, 
how to enable it? If
not, could it be achieved by textually replacing the types in the whole source? 
  Kind Regards,  Placek


GLPK has double built in.
I expect a global change to long double would
get you most of the way to long double.
Input, output and literal constants would still need fixing.
The values of tolerances could be left the same,
but reducing them would likely be useful.

BTW long double usually has 53- or 64-bit precision, not 106.
I think that gcc has a __float128 type that would do most of what you want.
It does literals, but not formatted IO.
Problem reformulation might be a better choice.

--
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] MIP problems

[Michael Hennebry]

On Mon, 7 Mar 2016, ΤΑΣΣΟΠΟΥΛΟΣ ΙΩΑΝΝΗΣ wrote:


I have been aware that MIP problems are NP-Complete or even NP-Hard.
Does any one know a reference (perhaps a published paper) in which it is
*proven* that MIP problems are NP- Complete or NP- Hard?


MILP can solve satisfiability, the seminal NP-complete problem.

As noted by others, special cases of MILP are not necessarily NP-complete.
E.g. LP and assignment.

--
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: glp_intopt conversion of solutions via callback]

[Michael Hennebry]

On Sat, 16 Jan 2016, Chris Matrakidis wrote:


On 16 January 2016 at 17:17, Sascha Brügmann <sascha.bruegm...@gmail.com>
wrote:



Michael Hennebry  web.cs.ndsu.nodak.edu> writes:

Perhaps it would be a good idea to make the presolving and
scaling transformation available to the user program.
It could just be a matter of documentation.
The information must already be somewhere,
otherwise glpsol could not invert it.

Yes, thats what I'm talking about!



Unfortunately it's not just a matter of documentation: internally, only the
transformations to convert solutions of the preprocessed problem back to
the original problem are available.


That might be sufficient.
I'd be surprised if the transformation were not effectively invertible,
i.e. a feasible solution in the original variables could not
be transformed to a solution for the proprocessed problem.

--
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: glp_intopt conversion of solutions via callback]

[Michael Hennebry]

On Fri, 15 Jan 2016, Heinrich Schuchardt wrote:


Looking at the code in src/glpkapi09.c and glpapi13.c the documentation
is wrong.

The problem accessible in the MIP callback is the presolved and scaled
problem. So if you have a heuristic solution expressed in your original
variables you should switch off presolving and scaling.


Perhaps it would be a good idea to make the presolving and
scaling transformation available to the user program.
It could just be a matter of documentation.
The information must already be somewhere,
otherwise glpsol could not invert it.

--
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: Help]

[Michael Hennebry]

On Thu, 14 Jan 2016, L. Felipe Castañeda G.  wrote:

CHd {(i,t) in GH: t-1 != 0}:V[i,t] = V[i,t-1] + g[i,t]*r[i,t] - 
S[i,t] - g[i,t]*k[i,t];


But I need to set an initial value for V[i,t]. I mean, I want to set 
V[i,1] = 60.


How can I do that?


You mean
fred { (i,t) in GH: t=1 } : V[i,1] = 60
?

--
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] Improving the execution time of the MILP program

[Michael Hennebry]

On Thu, 7 Jan 2016, esma mehiaoui wrote:


Is it true that the expression of the logical constraint (a and b) with the following 
constraints { x <=a ; x <= b ; a+b <= x+1} is less time consuming then its expression 
with the only constraint 0 <= a + b – 2x <= 1 ? 


It took me a while to suspect the by "logical constraint"
you meant that a, b and x were binary variables.

Quite probably, it is true.
The linear relaxation of the former is tighter than that of the latter.
Assuming the linear relaxation includes 0<=a,b,x<=1,
The first set of constraints defines the convex hull.
Tighter is not possible with linear constraints.
The second set of constraints allows a=1=b, x=0.5 ,
but the first does not.



Another question, in my program i have a constraint that computes the value of 
the variable V as the sum of variables V1, V2 and V3 (V=V1+V2+V3 ). My problem 
is that the value of V is integer and it sould be real. For instance, V= 23 
rather than 23.3. Do you have any suggestion for the origin of the problem ?


Perhaps you have a flag that says all variables are integer.

--
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] build and solve large scale linear programming model by GLPK

[Michael Hennebry]

On Thu, 17 Dec 2015, usa usa wrote:


I need to build and solve large scale linear programming model by GLPK
(4.57) from C# (4.0) VS2013 oin win 7 with 8GB memory.

The model size can be as large as 1 million decision variables and 1
million constraints.

Are there some limits on this kind of model scale in GLPK ?

If yes, what are they ? Is it possible to work around them ?


The memory required to hold a problem is determined mostly
by number of nonzeros in the constraint matrix.
Solving it involves factoring basis matrices.
If you are unlucky, that could be a trillion entries.
If you are lucky, the basis factors might only have as
many entries as the basis as much room as the basis.

--
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] Computation on outputs on outputs

[Michael Hennebry]

On Sun, 13 Dec 2015, Shaghayegh Mokarami wrote:


Hi Dear All
I solved two separated LP problems at the same time,  using .awk in my mac.
the optimal solution of two LPs are saved in 2 files which are attached
here,

Now I need to compute sum {(i,j) in E} tau_scenario(i,j)*x_nominal_opt(i,j)

Could you please let me know how I can compute it?


min z
s.t. z = sum {(i,j) in E} tau_scenario(i,j)*x_nominal_opt(i,j)

--
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] the theoretic formula about the integrality gap for MILP and 0-1 knapsack integer programing model

[Michael Hennebry]

GLPK uses |best_found - best_bound|/(|best_found| + DBL_EPSILON) .

A better formula would be to get rid of the absolute values
and replace DBL_EPSILON with -lp_obj,
the negative of the LP relaxation's objective value.

The man that matters disagrees and is more interested in copying CLPEX.

My suggestion can result in 0/0 iff the MIP has
the same objective value as its LP relaxation.
At that point, the MIP has been solved.

--
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] Problem has no feasible solution.

[Michael Hennebry]

On Wed, 18 Nov 2015, Fernando Garcia wrote:


Hello everyone, I am having some problems when solving a problem because it
is not feasible. I have checked the code hundreds times and I still dont
know where can be the unfeasibility.

Is there any routine in the glpk packet in c++ to show in which row/column
appears the unfeasibility?


I think that even after infeasibility is discovered,
you can print the solution and its basis.
Might not be as useful for integer programs.

--
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] Non linear constraint

[Michael Hennebry]

On Sun, 8 Nov 2015, esma mehiaoui wrote:


I just need to be sure that the no linear following constraint cannot be 
expressed in a MIP program or linearised.

Prod{i in 1..4} sum {j in 1..5} V[i,j] * C[i] * R[i]

Ps: V is a boolean variable
 C is a boolean parameter
 R is a real parameter


I'm taking this to mean can
P = Prod{i in 1..4} sum {j in 1..5} V[i,j] * C[i] * R[i]
be linearized.

Expanding the product one gets a sum of up to 5**4=625
products of boolean variables times real parameters.
An auxillary boolean for each product will give you a linearization.

The continuous relaxations of linearizations tend to be rather loose.
I expect that the one above will be more loose than most.
Getting the convex hull might involve 2**20 constraints or variables,
so I expect that that is out of the question.

A common technique is to start with a set of constraints
that is mathematically sufficient and add additional
constaints (cutting planes) during solution.
The separation problem between(P, V) and
conv{ (p, v) : p = Prod ... } is solvable,
but might involve solving a sequence of rather large LPs.
What one might do instead is to take the gradient of P with respect to V.
Test whether g . V - P is in range.
Starting from scratch, that could require around 4*5*2**20 operations.

--
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] Non linear constraint

[Michael Hennebry]

Other constraints might be obtained from formulas for
minimizing the difference between a product of variables
and a linear combination of same.

min PROD x[j] - SUM c[k]*x[k]
j in 1..n   k in 1..n

set the derivative with respect to x[L] to 0:

   PROD x[j] - c[L] = 0for L in 1..n
j in 1..n - {L}

   PROD x[j] =  c[L]for L in 1..n
j in 1..n - {L}

multiplying n equations:

  PROD x[j]**(n-1)  = PROD c[j]
  j in 1..n   j in 1..n

  PROD x[j]   = PROD c[j]**(1/(n-1)
  j in 1..n k in 1..n

dividing:

  x[L] = c[L]**-1 * PROD c[j]**(1/(n-1))
j in 1..n

Note that I have assumed c> 0 and x> 0 .

--
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] expressing a constraint depending on a boolean variable

[Michael Hennebry]

On Wed, 4 Nov 2015, Heinrich Schuchardt wrote:


Hello Esma,
 
please, see
https://en.wikibooks.org/wiki/GLPK/Modeling_tips#Big_M


Be sure take the advice to use the smallest M that you know works.
Done right, you will get the convex hull of allowed solutions.

--
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] glp_mip_col_val is returning negative zero

[Michael Hennebry]

On Fri, 1 May 2015, Andrew Makhorin wrote:


On Fri, 2015-05-01 at 15:17 +, Agostina Kodelia wrote:

Hi!
 I'm solving a very simple postman travelling problem with
the glp_intopt method. When I retrieved the column value
with glp_mip_col_val, it returns a negative zero. The zero is alright,
but I don't understand why has a minus, could anyone explain to me why
is this happening?



This is because the IEEE 754 standard which most of modern FPUs conform
to claims that a floating-point zero has the sign bit. A negative zero
may appear, for example, on computing (2. - 3.) * (5. - 5.) = -1. * +0.
= -0.


The minus sign was not actually necessary.
C89 is not required to notice the sign of zero.
That printf did suggests that its author made a special effort.
So far as I know,
none of C89's successors are required to notice the sign of zero.
C99 implementations *may* choose to honor IEEE floating point
and to note the fact in a C99-defined preprocessor symbol.
C99 defines said choice to include noticing the sign of zero.

--
Michael   henne...@web.cs.ndsu.nodak.edu
SCSI is NOT magic. There are *fundamental technical
reasons* why it is necessary to sacrifice a young
goat to your SCSI chain now and then.   --   John Woods

___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk

Re: [Help-glpk] [Fwd: GLPK enhancement]

[Michael Hennebry]

On Fri, 20 Mar 2015, Erik Quaeghebeur wrote:


Heinrich Schuchardt:


On Linux you can create a FIFO with mkfifo and pass the path to the
GLPK.

On Windows you can create a named pipe and use its path
(CreateNamedPipe).


Thanks for the idea. Sadly enough for my needs, Python does not provide
a unified interface for named pipes it seems, so a temporary files is
still better from the portability perspective.


If you are dead set against a temporary file
and have the documentation for your C,
you could create your own pseudo-FILE that simply read from the string.
It's probably not worth the effort.

--
Michael   henne...@web.cs.ndsu.nodak.edu
SCSI is NOT magic. There are *fundamental technical
reasons* why it is necessary to sacrifice a young
goat to your SCSI chain now and then.   --   John Woods

___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk

Re: [Help-glpk] Modeling exclusive OR in Mathprog language

[Michael Hennebry]

I'm a bit fuzzy on what you want.
If you want to express x=a XOR b, where a, b and x are binaries,
you just need four constraints,
the constraints that cut off 001, 010, 100 and 111.
That will give you the convex hull, which is as good as can be done.

   n
To express, x=XOR a[j]  ,  for some large n,
  j=1
 n
note that 0 = x XOR XOR a[j]  .
j=1

Add another integer variable:
 n
0 = x + SUM a[j] - 2*s
j=1

The range of s in 0..floor((n+1)/2)

--
Michael   henne...@web.cs.ndsu.nodak.edu
SCSI is NOT magic. There are *fundamental technical
reasons* why it is necessary to sacrifice a young
goat to your SCSI chain now and then.   --   John Woods

___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk

Re: [Help-glpk] Modelling constaints

[Michael Hennebry]

On Thu, 26 Mar 2015, john tass wrote:


Let U, K in {-6, .. , 6} integers
Let A in {0, 1} binary
Let D in {0, 1} binary
What I want to do  is to model the condition:
D = 1, iff (U  0 OR K  0) AND A = 1
Otherwise, D should equal 0.
I can not figure out how to model this situation.
Can any one give me an answear or even a hint? It would be very welcome.


I'd suggest two binaries to flag U=1 and K=1 .
Call them Qu and Qk respectively.

u want Qu = 1 - U=1
U = 1 - (1-Qu)*M
making M big enough will ensure that U can be in -6..0 when Qu=0
-6 = 1 - (1-0)*M
M=7 will work
U - 7*Qu = -6

You want Qu = 0 - -U=0 .
The same kind of math gives
-U + 6*Qu = 0

Likewise for Qk:
U - 7*Qk = -6
-U +6*Qk =  0

Another way to get those constraints is to graph the valid values.
The extreme points for (Qu, U) are:
(0, -6) (0, 0) (1, 1) (1, 6)

Now you just need constraints on the binaries A, D, Qu and Qk.
Doing it crudely, you could use 8 constraints
to cut off each of 8 invalid combinations.
Actually, you only need 4 constraints.
To help you find them, a Karnaugh Map might help:
http://en.wikipedia.org/wiki/Karnaugh_map
You will be more interested in zeros than in ones.

--
Michael   henne...@web.cs.ndsu.nodak.edu
SCSI is NOT magic. There are *fundamental technical
reasons* why it is necessary to sacrifice a young
goat to your SCSI chain now and then.   --   John Woods

___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk

Re: [Help-glpk] Name assignments to a large number of variables

[Michael Hennebry]

On Sun, 22 Mar 2015, john tass wrote:


I do not care whether the problem is going to be solved in a reasonable
amount of time or not. I can wait for a long time. The only thing I do care
is to get an answer to my question. So, if you can help me I would
appreciate it.


The unreasonable time referenced is not a year or even a century.
More likely it's a large multiple of the age of the universe.

That said, you have other problems before you get that far.
An algorithm to name your variables uses pretty much the same kind
of logic required to get them into a solver in the first place.
If you cannot do that, you will have a hard time entering your problem.

--
Michael   henne...@web.cs.ndsu.nodak.edu
SCSI is NOT magic. There are *fundamental technical
reasons* why it is necessary to sacrifice a young
goat to your SCSI chain now and then.   --   John Woods

___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk

Re: [Help-glpk] csv_driver:unable to create ....csv - Permission denied

[Michael Hennebry]

On Tue, 6 Jan 2015, Martin Albrecht wrote:

I am running a GLPK model that is sequentially started from a frame program 
in Java.


In this contex, what is a frame program?
What OS are you running?


Unfortunately,  I get sometime error when opening the .csv files.
Here is an example:
/
csv_driver: unable to open BOM.csv - Permission denied
allocation.mod:113: error on opening table tab_BOM
glp_mpl_build_prob: invalid call sequence
Error detected in file ..\src\glpapi14.c at line 93/

I do not get this error at each call of the Java model (one error after 
approx. 50 calls). Moreover, these errors do not occur in a deterministic 
manner, they cannot be reproduced. I each run of the Java program they occur 
at another place.


Looks like a thread issue to me.
Do the open and close occur in different threads?
Perhaps the open is attempted before the close has gone through.

--
Michael   henne...@web.cs.ndsu.nodak.edu
SCSI is NOT magic. There are *fundamental technical
reasons* why it is necessary to sacrifice a young
goat to your SCSI chain now and then.   --   John Woods

___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk

Re: [Help-glpk] Variable Assigned to itself

[Michael Hennebry]

On Fri, 12 Sep 2014, Nigel Galloway wrote:


I think you will find that this error is being reported by Codan, a
truncation of Code Analysis I presume. This is an Eclipse Tool and not
part of the compiler tool chain. I think you'll find a separate output
window in Eclipse with the output from the compiler in it. There should
be no error as t=t is not illegal in C or C++, and I would expect GLPK
to have compiled correctly.


t=t is valid C, but that does not make it a good idea.

The statement is either as intended or not.
The statement is either a nullity or doing something subtle.

In any case, the code should be changed.
If nothing else,
the code should have documentation to inform its next reader.


On Wed, Sep 10, 2014, at 04:48 PM, Norman Jessup wrote:

I'm trying to compile the glpk source using the Eclipse IDE (I'm not
terribly familiar with either).  One module, glpini01.c, is generating
multiple errors of the form:

 Assignment to istelf 't = t' 


--
Michael   henne...@web.cs.ndsu.nodak.edu
SCSI is NOT magic. There are *fundamental technical
reasons* why it is necessary to sacrifice a young
goat to your SCSI chain now and then.   --   John Woods

___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk

Re: [Help-glpk] Variable Assigned to itself

[Michael Hennebry]

On Thu, 11 Sep 2014, Norman Jessup wrote:

I'm trying to compile the glpk source using the Eclipse IDE (I'm not terribly 
familiar with either).  One module, glpini01.c, is generating multiple errors 
of the form:


   Assignment to istelf 't = t' 

On looking at the code this does seem to be the case.  I'm not sure if this 
is allowed by the C++ standard or not, and there is an option I can set to 
ignore this error.  However, as the starting value of t is established just 
a few lines before the error it seems it would be very straightforward to 
modify this so that no compiler or pre-compiler complains.  Is there any 
reason why this can't be done ?   I'd be happy to submit proposed changes,


Make sure you understand the error first.
Use -save-temps and look at the .ii file.

though given these are trivial it may be easier for the guardians of the code 
to change themselves rather than vet my updates.


--
Michael   henne...@web.cs.ndsu.nodak.edu
SCSI is NOT magic. There are *fundamental technical
reasons* why it is necessary to sacrifice a young
goat to your SCSI chain now and then.   --   John Woods

___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk

Re: [Help-glpk] Objective value issue

[Michael Hennebry]

On Fri, 11 Jul 2014, Mattia Buccarella wrote:


When I use glpsol to solve my model (written in MathProg, with separate
data input file), all the variables are configured properly as I expect (I
am referring to a dummy input I use to verify the correctness of my
model). Nevertheless, the value of the objective function is shifted and I
get the following message:

Model has been successfully generated
*glp_mpl_build_prob: row obje; constant term 84384 ignored*
GLPK Integer Optimizer, v4.52
...etc...


Perhaps preprocessing introduces the constant term.

--
Michael   henne...@web.cs.ndsu.nodak.edu
SCSI is NOT magic. There are *fundamental technical
reasons* why it is necessary to sacrifice a young
goat to your SCSI chain now and then.   --   John Woods

___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk

Re: [Help-glpk] Interior point method and MIPs

[Michael Hennebry]

On Tue, 1 Jul 2014, Andrew MacFie wrote:


I understand that for MIPs, GLPK uses branch-and-bound and only
offers the simplex method. I would be interested in knowing why
the interior point method is only allowed for LPs, not MIPs.


Branching is rather hard to do with interior point methods.

--
Michael   henne...@web.cs.ndsu.nodak.edu
SCSI is NOT magic. There are *fundamental technical
reasons* why it is necessary to sacrifice a young
goat to your SCSI chain now and then.   --   John Woods

___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk

Re: [Help-glpk] Linking errors when using cfg.h in a MacOs X

[Michael Hennebry]

On Wed, 18 Jun 2014, Jose L Walteros wrote:


In the Linux machine I don't have access to root so, when I installed GLPK,
I configured it as:
./configure --disable-shared --prefix=/home/jwalteros/GLPK/GLPK-4.54-ins/


That why it linked.
Exported symbols are a dynamic library thing.
With your static library, all non-local symbols are visible.

--
Michael   henne...@web.cs.ndsu.nodak.edu
SCSI is NOT magic. There are *fundamental technical
reasons* why it is necessary to sacrifice a young
goat to your SCSI chain now and then.   --   John Woods

___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk

Re: [Help-glpk] Linking errors when using cfg.h in a MacOs X

[Michael Hennebry]

On Wed, 18 Jun 2014, Heinrich Schuchardt wrote:

So I wonder how you made you program compile on your Linux machine. Did you 
manipulate the list of exported symbols?


I think that exporting non-local symbols is the default on Linux.
Occasionally I see threads about making dynamic libraries
work on Windows without peppering the source with Windows-isms.
This is likely the reason.
I do not recall a good solution.

--
Michael   henne...@web.cs.ndsu.nodak.edu
SCSI is NOT magic. There are *fundamental technical
reasons* why it is necessary to sacrifice a young
goat to your SCSI chain now and then.   --   John Woods

___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk

Re: [Help-glpk] Solving linear/nonlinear systems of equations via glpk

[Michael Hennebry]

On Tue, 29 Apr 2014, Fatih Gürdal wrote:


In an academic paper it is claimed finding all solutions to non linear
systems of equations by using glpk.There, dual simplex method is said to
use.


For the general case, color me dubious.
Some problem classes are inherently unsolvable.


My question is how we can define this problem in glpk to have the solutions.
In other words how can we define a problem about solving systems of
linear/nonlinear equations using glpk?


GLPK does continous and integer linear programming.
Iterative programming can get you a bit more,
but I expect that even among solvable problems,
iterative MILP is not suitable for some.

--
Michael   henne...@web.cs.ndsu.nodak.edu
SCSI is NOT magic. There are *fundamental technical
reasons* why it is necessary to sacrifice a young
goat to your SCSI chain now and then.   --   John Woods___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk

Re: [Help-glpk] Applying a threshold to the solution using GMPL?

[Michael Hennebry]

On Sun, 10 Nov 2013, Meketon, Marc wrote:


Instead of Awk, there is another way of doing this which I often find is easier 
because all the calculations stay within GMPL:


I expect that your GMP will work as advertised,
but that what OP wants is a bit more compilcated than that.

What I expect OP wants is to have as many X's as possible
forced to zero without damaging the L1 norm too much.

I'm not clear whether that is best expressed as a bound
on the L1 norm or providing a penalty for nonzero X's.

More than two iterations might be useful.

The first iteration is, of course,
to find an optimal solution for the problem without considering sparsity.

If, from simple arthmetic, one can find X's that can be forced
to zero without changing other X's, one should do so.
OP's original approach seemed to be intended select each X independently,
so that even if all met the threshold and the damage was
completely additive, the total damage would not be too much. (*)
After re-solving, that approach could be used
again until it failed to zero any more X's.

Subsequent iterations wouuld involve separately forcing
each nonzero X to zero and assessing the damage.
After that, one could force X's to zero in ascending
order of damage until the L1 threshold had been reached.


(*) If one can sort, Add in the X's in ascending
order of damage until the sum is too big.
If one prefers GMPL, I think that one can do something like this:
TDA=total damage allowed
S1={ (i,j) : damage[i,j]=TDA }   # probably too big
S2={ (i,j) : damage[i,j]*|S1|=TDA }  # probably too small
TDA2=SUM{ (i,j) in S2 }(damage[i,j])  # not best formula
S3={ (i,j) : damage[i,j]=TDA-TDA2 } - S2  # probably too big
S4={ (i,j) : damage[i,j]*|S3|=TDA-TDA2 }  # probably too small
Zero X[i,j] : (i,j) in S2+S4

One can sort with GMPL, but I suspect that it is at least quadratic:
http://en.wikibooks.org/wiki/GLPK/GMPL_Workarounds

--
Michael   henne...@web.cs.ndsu.nodak.edu
On Monday, I'm gonna have to tell my kindergarten class,
whom I teach not to run with scissors,
that my fiance ran me through with a broadsword.  --  Lily

___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk

Re: [Help-glpk] Applying a threshold to the solution using GMPL?

[Michael Hennebry]

On Mon, 11 Nov 2013, Reginald Beardsley wrote:


Marc's suggestion fits very nicely with what I'm trying to do at the moment.

I sometimes get terms which constitute much less than 1% of the total result.  
Those are what I want to drop.  Doing so requires recalculating the other terms 
to minimize the error.


Of course you will want to recalculate.
If you have fifty one-percenters,
you will want to recalculate your solution.
If you have a thousand one-percenters,
you will want to recalculate your threshold.
Marc's works if you already know your threshold.


I may want to do something fancier eventually, but right now I'm still trying 
to develop an appropriate mathematical model for the physics.

That said, there's another problem for which what is suggested here looks very 
attractive.  I've attempted to solve that problem several times over the course of 
20+ years without ever finding a satisfactory solution.  It involves finding the 
derivative of a series irregularly sampled in x with truncation errors in both x 
 y.  When the data are finely sampled in x the truncation to 3-4 digits in y 
leads to wild swings in the derivative.  To date the only solution has been 
smoothing based on ersatz heuristics.  Good enough, but not aesthetically 
satisfying.


You might want to consider doing something related to splines.
The values at the knots would have ranges rather than fixed values.
In the case of a cubic spline, you might want to minimize the
sum of the squares of the third derivitives or something.

--
Michael   henne...@web.cs.ndsu.nodak.edu
On Monday, I'm gonna have to tell my kindergarten class,
whom I teach not to run with scissors,
that my fiance ran me through with a broadsword.  --  Lily

___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk

Re: [Help-glpk] Applying a threshold to the solution using GMPL?

[Michael Hennebry]

On Sat, 9 Nov 2013, Reginald Beardsley wrote:


I've been  hoping it can be done with binary variables in GMPL as I'm still 
trying to refine the problem statement.  I'd like to be confident it's a good 
choice before coding it. I'd also like to improve my grasp of expressing 
problems in GMPL.  I started out using CPLEX format and switching to GMPL has 
been a huge improvement when trying to explore various problem formulations.


I'd recommend against.
You end up with constraints like
x = U(x)*b
where U(x) is an upper bound on x.


With a two step solution if i set the weights to 0 or 1 I can probably get what 
I want by light editing of the data file using awk to add the weighting array.  
Not perhaps as elegant as solving in a single step, but it would allow using a 
pure LP solution and avoid the performance hit that a MIP formulation implies.  
Until I read your suggestion I'd been thinking along the lines of writing a 
whole new data file which was pretty painful to contemplate.


In the second stage, binaries might be more useful.
You already have a feasible solution and you
can substitute smaller numbers for the U(x)'s.

If you do not mind writing code:

more=false
do {
for each x[j]:
if x[j] != 0:
if changing x[j] to 0 would not increase L1 too much:
change x[j] to 0
more=true
} while(more)

This would not necessarily be optimal.
The only x's changing are those changed to zero.
You could run the LP again with the new constraints and repeat the process.
Of course, using the API,
each change x[j] to 0 could be followed by a reoptimization.

--
Michael   henne...@web.cs.ndsu.nodak.edu
On Monday, I'm gonna have to tell my kindergarten class,
whom I teach not to run with scissors,
that my fiance ran me through with a broadsword.  --  Lily

___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk

Re: [Help-glpk] Applying a threshold to the solution using GMPL?

[Michael Hennebry]

On Sat, 9 Nov 2013, Reginald Beardsley wrote:


I'm solving Ax=b using an L1 norm.  In some cases I get a number of relatively 
small values in x that I would like to suppress based on the fraction of the 
result that they contribute so as to make the solution more sparse.



From this description, doing what you seem want

in one swell foop would require binary variables
and might be difficult to express even with them.
The desired range is discontinous.
A two-stage process is in order.


Unfortunately I'm unable to recognize from the examples in the distribution 
(4.45) or the discussion in the AMPL book how to implement this using GMPL.  
The following model file shows what I'm trying to do.  I'd like to apply a 
constraint such that:

(sum{i in I}(A[i,j,k]*X[j,k]/b[i]))/ii = threshold


If your L1 norm was the right call before, you should use it again.

On the second stage, put an upper limit on the original L1 norm
and minimize a weighted sum of X's:


# array limits
param ii;
param jj;
param kk;

# array indices
set I := 1..ii;
set J := 1..jj;
set K := 1..kk;

param b{I} ,=0;

param A{I,J,K} ,=0;

# solution variables
var X{J,K} ,=0;

# slack variables
var u{I} ,=0;
var v{I} ,=0;

# objective


new objective:
sum{j in J, k in K} w[j,k]*X[j,k]
where w[j,k]= sum{i in I}b[i]/(A[i,j,k]*X1opt[j,k])


minimize error: sum{i in I}(u[i]+v[i]);


new constraint, make the new L1 norm no more than twice as bad:
sum{i in I}(u[i]+v[i]) = obj1opt*2


#constraints
s.t. eq{i in I}:sum{j in J} (sum{k in K}A[i,j,k]*X[j,k])
   + u[i] - v[i] = b[i];
solve;

# solution output

for{k in K}{
  printf{j in J:X[j,k]0} Tst: %15.8g %8.6f \n
}

end;


I suspect that the stage 1 output could be the stage 2 input.
A more complex version of roughly the same thing is to
combine the objective functions of stage 1 and stage 2.
I'm not all that sure that either would work well.
One might get a lot of cases of close, but no cigar.

Using the API might be simpler.
Select each X in order.
Force it to zero.
Check to see whether the L1 norm is too big.
If it is, unforce the X.

As you might need to sort the X's, the API might be simpler.
Sorting can be done with GMPL, but you might not like it.

--
Michael   henne...@web.cs.ndsu.nodak.edu
On Monday, I'm gonna have to tell my kindergarten class,
whom I teach not to run with scissors,
that my fiance ran me through with a broadsword.  --  Lily

___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk

Re: [Help-glpk] [Fwd: I: Modelling binary variable]

[Michael Hennebry]

On Tue, 8 Oct 2013, Meketon, Marc wrote:


Are you sure that Z = Q[2]-Q[1]?  For the case where x[1]=1, x[2]=0, x[3]=0, we 
have Q[1]=0, Q[2]=0, Q[3]=1, and then Q[3]-Q[2] = 1 which is the correct answer.


Z = Q[1]-Q[2]
he has Q sorted in non-ascending order.
00 no ones  0-0=0
10 one one  1-0=1
11 two or more ones 1-1=0
exactly what you want
The size of N does not matter.

Meketon's code has the advantage of ease of coding and understanding,
but it doubles the dimensionality.

Assume one has an integer expression sum:
0=sum=N
One wants z==1 iff sum==1 else 0
Define N2lo=floor(N/2), N2hi=ceil(N/2)
Note N=N2lo+N2hi, H2hi-N2lo in {0, 1}
Add two (not N) more integer variables:
0=a=N2hi
b binary

require
sum=2a+b
z=b-a
z=b
z=(1-N2hi/N2lo)b - a/N2lo + N2hi/N2lo

The last constraint on z should be multiplied by
N2lo to ensure integrality of the coefficients.

Done.

The first two constraints on z are fairly obvious.
The last needs more explanation.

The diagram below is for N==7.

   3  0 -
   2  0 0
 a 1  0 0
   0  0 1

  0 1
  b

The rectangle gives the values of z for all valid combinations of a and b.
The given constraints on z are all facets of the polyhedron.
The first is for facet (0, 0, 0)(0, 1, 1)(1, 0, 0).
The second for facet (0, 0, 0)(0, 1, 1)(N2hi, 0, 0).
The third for facet (N2lo, 1, 0)(0, 1, 1)(N2hi, 0, 0).
Substitution will verify.


Note that exhaustive testing is possible:
The number of combinations that need testing is at most 2*(N+1)**2 .

--
Michael   henne...@web.cs.ndsu.nodak.edu
On Monday, I'm gonna have to tell my kindergarten class,
whom I teach not to run with scissors,
that my fiance ran me through with a broadsword.  --  Lily

___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk