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

 
 

bug #40974: GLPK returns illegal solution

Submitter:  None
Submitted:  Thu 19 Dec 2013 07:33:11 PM UTC
   
 
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Inaccurate Result
Status:  Invalid / Not an Octave Bug Assigned to:  None
Originator Name:  Niels Langager Ellegaard Originator Email:  -email is unavailable-
Open/Closed:  * Closed Release:  * 3.6.4
Operating System:  * GNU/Linux Fixed Release:  None
Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

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>
Group Member
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>
Group Member
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>
Group Member
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]-4*10.^[N-1:-1:0]; A=[arow;-arow];b=[0;0];c=[N-1:-1:0]; lb=zeros(1,N);ub=9*ones(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 Files:
   
   
Comment:
   

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

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

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only group members can vote.

     

    Follow 4 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2016-11-16 mtmiller StatusNeed Info Invalid / Not an Octave Bug
        Open/ClosedOpen Closed
    2014-01-15 mtmiller CategoryNone Octave Function
        StatusNone Need Info

    Back to the top

    Powered by Savane 3.13-d3ae.
    Corresponding source code