[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
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- Re: [Bug-glpk] Constraints violated,
Andrew Makhorin <=