bug-glpk
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Bug-glpk] Constraints violated


From: Andrew Makhorin
Subject: Re: [Bug-glpk] Constraints violated
Date: Wed, 06 Apr 2016 00:40:52 +0300

On Tue, 2016-04-05 at 17:13 -0400, Carolyn Kim wrote:
> Hi GLPK team, 
> 
> 
> I'm using GLPK solver with Pulp object model in Python. We are using
> it to optimize the allocation of positions (where a position object
> has an account and product). The following is the simplified version
> of our problem:
> 
> 
> Variables: final_allocation_var for each position
> 
> 
> Objective value: Sum of rate * price * final_allocation_var for each
> position (where rate and price are constants)
> 
> 
> Constraints:
>      1. final_allocation_var <= available quantity for each position
>         (where available quantity is a constant)
>      2. Sum of price * final_allocation_var that has the same account
>         <= account's maximum release value, which is also constant. 
>      3. Sum of final_allocation_var that has the same product >=
>         product's minimum release quantity, which is constant
> GLPK solves this quite fast, but some constraints are violated. For
> example, for one position, the final allocation is 42 greater than the
> available quantity, breaking the 1st constraint. I attached the lp and
> mps problem file. And also our excel report that shows the constraints
> that are being violated. ('positions' tab will show the 1st
> constraint, 'groups' tab will show the 2nd constraint, and the
> 'products' tab will show the 3rd constraint). I've been searching
> online for many days trying to figure out why the constraints are
> being violated (all of our three data sets show similar constraint
> violations), but I could not figure out why. 
> 
> 
> Could you help me in trying to understand this problem? Please let me
> know if you need any more information. 
> 
> 
> Thank you so much!
> Carolyn 

I'm unable to reproduce the effect. Though your model is badly scaled
(ratio ~= 1e10), the optimal solution found by glpsol has sufficient
accuracy according to the KKT optimality conditions (see below).

You may try to disable the presolver (--nopresol) and/or automatic
scaling (--noscale). This may help.


Andrew Makhorin


GLPSOL: GLPK LP/MIP Solver, v4.60
Parameter(s) specified in the command line:
 --lp problem.lp -o foo.txt --log foo.log
Reading problem data from 'problem.lp'...
5936 rows, 5152 columns, 12117 non-zeros
16587 lines were read
GLPK Simplex Optimizer, v4.60
5936 rows, 5152 columns, 12117 non-zeros
Preprocessing...
521 rows, 5037 columns, 6560 non-zeros
Scaling...
 A: min|aij| =  2.000e-05  max|aij| =  2.160e+05  ratio =  1.080e+10
GM: min|aij| =  7.910e-01  max|aij| =  1.264e+00  ratio =  1.598e+00
EQ: min|aij| =  6.304e-01  max|aij| =  1.000e+00  ratio =  1.586e+00
Constructing initial basis...
Size of triangular part is 521
      0: obj =   1.097867533e+08 inf =   1.725e+08 (374)
    500: obj =   4.661065130e+08 inf =   9.525e+07 (176)
    894: obj =   6.832993910e+08 inf =   1.028e-10 (0)
*  1000: obj =   1.033599061e+09 inf =   1.028e-10 (2921)
*  1500: obj =   1.635520329e+09 inf =   1.109e-10 (1968)
*  2000: obj =   1.745385247e+09 inf =   2.946e-11 (801) 1
*  2456: obj =   1.775745840e+09 inf =   3.522e-11 (0)
OPTIMAL LP SOLUTION FOUND
Time used:   1.0 secs
Memory used: 3.8 Mb (3964304 bytes)
Writing basic solution to 'foo.txt'...

Karush-Kuhn-Tucker optimality conditions:

KKT.PE: max.abs.err = 2.98e-08 on row 5244
        max.rel.err = 1.75e-14 on row 5748
        High quality

KKT.PB: max.abs.err = 1.36e-12 on row 1404
        max.rel.err = 1.89e-13 on column 2532
        High quality

KKT.DE: max.abs.err = 3.64e-12 on column 2594
        max.rel.err = 8.50e-15 on column 3231
        High quality

KKT.DB: max.abs.err = 0.00e+00 on row 0
        max.rel.err = 0.00e+00 on row 0
        High quality











reply via email to

[Prev in Thread] Current Thread [Next in Thread]