bugGNU Octave - Bugs: bug #40974, GLPK returns illegal solution

 
 

bug #40974: GLPK returns illegal solution

Submitted by:  None
Submitted on:  Thu 19 Dec 2013 07:33:11 PM UTC  
 
Category: Octave FunctionSeverity: 3 - Normal
Priority: 5 - NormalItem Group: Inaccurate Result
Status: InvalidAssigned to: None
Originator Name: Niels Langager EllegaardOriginator Email: -unavailable-
Open/Closed: ClosedRelease: 3.6.4
Operating System: GNU/Linux

Add a New Comment(Rich Markup)
   

You are not logged in

Please log in, so followups can be emailed to you.

 

Wed 16 Nov 2016 11:31:21 PM UTC, comment #3:

No response from the OP to Arun's comments in several years, closing as invalid on the assumption that comment #2 is correct and the problem can be solved by setting the tolerance.

Mike Miller <mtmiller>
Project Administrator
Thu 19 Dec 2013 11:37:02 PM UTC, comment #2:

*Edit to say: "max(abs(A),[],2) ./ min(abs(A),[],2) ranges in the thousands".

Also note to Niels: best to enclose code more than 2 or 3 lines long with the verbatim[1] tags, as the asterisks for multiplication get munged as bold markers.

[1] https://savannah.gnu.org/cookbook/?func=detailitem&item_id=125

Arun Giridhar <arungiridhar>
Thu 19 Dec 2013 11:29:07 PM UTC, comment #1:

This just looks like a convergence tolerance issue and not a software bug to me?

Try lowering tolint to something less than the default 1e-5:

options.tolint = 1e-9;
[x1,x2,x3,x4] = glpk ( [YOUR EXISTING ARGUMENTS FOLLOWED BY], options)

That should get you the solution for N = 7 and N = 8.

Note that the problem as formulated is inherently poorly scaled, with the coefficients of A such that max(abs(A),2) ./ min(abs(A),2) ranges in the thousands, and absolute coefficient values exceeding 2^31 for N=10. In such cases, all MILP formulations will behave poorly or fail. This behavior is really indicating that posing the problem as an integer program is not the best approach.

BTW your constraints as stated say both "Ax <= b" and "Ax >= b". You could use only arow instead of duplicating it, and replace "UU" in glpk with "S" for equality.

Arun Giridhar <arungiridhar>
Thu 19 Dec 2013 07:33:11 PM UTC, original submission:

The following line invokes glpk to solve an integer problem. But sadly GLPK returns a solution that is not legal. If the solution was legal then A*x1 should be [0,0].

N=8; arow=10.^[0:N-1]-410.^[N-1:-1:0]; A=[arow;-arow];b=[0;0];c=[N-1:-1:0]; lb=zeros(1,N);ub=9ones(1,N);[x1,x2,x3,x4]=glpk (c, A, b, lb, ub, "UU", repmat("I",[1,N]), -1), A*x1
x1 =

1
9
9
9
9
9
9
7

x2 = 196.00
x3 = 171
x4 =

scalar structure containing the fields:

time = 0
mem = 0

ans =

3
-3

If glpk has found an illegal solution, then the solver should probably warn he user that the solution is illegal. Perhaps the wrapper could perform an extra check to make sure that glpk is right.

Note: You can change the problem size by changing N. if you choose N=7, the the code tuns nicely.

BTW: The code find numbers such as 2199978 that fullfills

4*2199978 = 8799912

IN other words you can reverse the ciphers by multiplying with 4.

Anonymous

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach File(s):
   
   
Comment:
   

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -unavailable- added by mtmiller (Updated the item)
  • -unavailable- added by arungiridhar (Posted a comment)
  • -unavailable- added by None (Submitted the item)
  •  

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    This task has 0 encouragements so far.

    Only project members can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 4 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Wed 16 Nov 2016 11:31:21 PM UTCmtmillerStatusNeed Info=>Invalid
      Open/ClosedOpen=>Closed
    Wed 15 Jan 2014 05:07:33 AM UTCmtmillerCategoryNone=>Octave Function
      StatusNone=>Need Info

    Back to the top


    Powered by Savane 3.1-cleanup1