Bug 1199955 - Nearby selection should force that the originalEntitySelector is a mimic replaying entity selector.
Summary: Nearby selection should force that the originalEntitySelector is a mimic repl...
Keywords:
Status: CLOSED EOL
Alias: None
Product: JBoss BRMS Platform 6
Classification: Retired
Component: OptaPlanner
Version: 6.1.0
Hardware: Unspecified
OS: Unspecified
medium
medium
Target Milestone: DR1
: 6.2.0
Assignee: Geoffrey De Smet
QA Contact: Lukáš Petrovický
URL:
Whiteboard:
Depends On:
Blocks:
TreeView+ depends on / blocked
 
Reported: 2015-03-09 11:15 UTC by jvahala
Modified: 2020-03-27 19:05 UTC (History)
2 users (show)

Fixed In Version:
Clone Of:
Environment:
Last Closed: 2020-03-27 19:05:02 UTC
Type: Bug
Embargoed:


Attachments (Terms of Use)
anti reproducer (117.87 KB, text/plain)
2015-03-24 10:31 UTC, Geoffrey De Smet
no flags Details
reproducer (39.86 KB, application/zip)
2015-03-30 14:28 UTC, jvahala
no flags Details

Description jvahala 2015-03-09 11:15:35 UTC
Description of problem:

I've made up my own TSP problem which contains from nodes in one line. CH founds best solution, ofc, but I am testing next pick planner figures out. I am forcing planner to start with first entity in chain and then pick move from block distribution (see attach. ).

How blockDistribution with nearbySelection should work: 
- it gets entity and pick value for this entity with constant probability from first N values(entities) specified in config file. 

It means, that if I specify in solver config as
<blockDistributionSizeMaximum>2</blockDistributionSizeMaximum>
planner should be able to do only two moves from that first entity. 

ok well, I have PRODUCTION mode in my solver config and I run 100_000 solvers on same initialized soluton, collecting all first moves in map and it's counts.

after all solvers are finished, I have in map stored 3 types of moves: 
"2(after1) => 3(after2)" cca 62%
"2(after1) => 4(after3)" cca 25%
"2(after1) => 5(after4)" cca 13%

the last move shouldn't be there at all. 

Also, first two moves should be both generated with P[0.5], but I need to examine distribution issue more, there may be mistake on my side. (I am not sure with settings I have in config)

Comment 3 jvahala 2015-03-12 11:24:01 UTC
Note: Geoffrey, could you double-check the config file, please?

Comment 4 Geoffrey De Smet 2015-03-23 14:47:44 UTC
The config file looks good. I agree that this looks like a genuine bug.

Comment 5 Geoffrey De Smet 2015-03-24 09:08:53 UTC
To make a reproducer, it's possible to configure a with a randomSeed: <solver><randomSeed>123</randomSeed></solver>.

Comment 6 Geoffrey De Smet 2015-03-24 10:31:10 UTC
Created attachment 1005792 [details]
anti reproducer

I cannot reproduce this. See attached txt file antireproducer.
I tried a different 1000 randomSeeds (even random randomSeeds, but also just 0 to 1000), and I never got a ChangeMove other than the 2 nearest cities (Paris or London) from the selected entity (Dublin).

I was wondering if it might be because of UndoMove's that got counted too in your code, but even those would never involve Brussels. Weird. Let's investigate further. I did use a TSP with 40 locations.

Comment 7 jvahala 2015-03-30 14:28:57 UTC
Created attachment 1008520 [details]
reproducer

just run mvn clean install

without changes, test should pass. when you switch europe.xml to line.xml (there is commented line) and run mvn agian, test should fail. If doesn't you may try to run more solver instances, but I suppose it should be fine. 

another interesting part is, that on europe the scale is 1:1 in moves, but there it is 60:27:13. Which is also wrong. I suppose that fixing bug should also solve this issue.

Comment 8 Geoffrey De Smet 2015-04-01 15:57:48 UTC
Reproduced with reproducer.
It looks like a bug in the mimic selection probably. 5 is too far from 2, yet it gets selected as a value. When it creates the move "2 => 5", the RandomEntityNearbyValueIterator believes that the origin is 4, not 2.

Comment 9 jvahala 2015-04-02 09:15:56 UTC
btw when you run reproducer with blockSize == 1, it picks only one correct move "2(after 1) => 3(after 2)", so it goes wrong when blockSize > 1, just making a note, it might help you find a bug.

Comment 10 Geoffrey De Smet 2015-04-02 13:29:29 UTC
Problem found.
It's not a runtime bug, it's a misconfiguration (that should throw a fail fast exception at bootstrap):

    <changeMoveSelector>
      <selectionOrder>ORIGINAL</selectionOrder>
      <entitySelector><!-- Should have an ID -->
        <selectionOrder>ORIGINAL</selectionOrder><!-- Obsolete btw -->
      </entitySelector>
      <valueSelector>
        <selectionOrder>RANDOM</selectionOrder>
        <nearbySelection>
          <originEntitySelector><!-- Should mimic the entitySelector above -->
            <selectionOrder>ORIGINAL</selectionOrder>
          </originEntitySelector>
          <nearbyDistanceMeterClass>org.optaplanner.examples.tsp.domain.solver.nearby.VisitNearbyDistanceMeter</nearbyDistanceMeterClass>
          <blockDistributionSizeMaximum>2</blockDistributionSizeMaximum>
        </nearbySelection>
      </valueSelector>
    </changeMoveSelector>

What happened:
- The config above first selects an entity (for example Madrid), then it selects a nearby value. When it selects that nearby value it looks for values which are nearby... a newly selected entity Ankarra (but it should look for values which are nearby Madrid, the original entity!).
- Why did it work most of the time? Because of the ORIGINAL order: the first entity selector starts with Dublin and so those the second. If we turn on trace logging we see that with the randomSeed that triggers the exception, first 2 undoable moves are selected, causing the first entity selector to be past Dublin already.

I hope that clears things up :) I 'll add the fail fast now.

Comment 11 Geoffrey De Smet 2015-04-02 13:46:35 UTC
Fail fast fixed on master for optaplanner 6.3.0.Beta1:
   http://github.com/droolsjbpm/optaplanner/commit/c95be1609
No plans to backport currently.

Comment 12 jvahala 2015-10-02 08:32:05 UTC
Verified with 6.2.0ER3


Note You need to log in before you can comment on or make changes to this bug.