Versions Compared

Old Version 8

changes.mady.by.user Ross Michael Anderson

Saved on

compared with

New Version 9

changes.mady.by.user Ross Michael Anderson

Saved on

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.
Comment: Migration of unmigrated content due to installation of a new plugin
{
Wiki Markup
Composition Setup
 Section
 Column
width300px
 Page Tree
rootTutorial
}
{composition-setup}
{section} 
{column:width=300px} 
{pagetree:root=Tutorial} 
{column} 
{column} 

h1. Medium Instance Performance

Lets take a look at where we are with all the bells and whistles added.  If you expand the toggle below, you will see the log file from our failed attempt to solve {{d657}}.
{toggle-cloak:id=d657log}_Show d657 log_
{cloak:id=d657log}
{excerpt-include:excerpt d657 log}
{cloak}
As stated on the [TSPLIB website|http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/STSP.html], the optimal solution for this problem is 48912.  By looking through the logs, you see that after only about 25,000 nodes, we reach a solution with objective 48913.  Unfortunately, our lower bound, while initially 99.3% of the optimal solution, increases very slowly.  Using the _
 Column
Medium Instance Performance
Lets take a look at where we are with all the bells and whistles added. If you expand the toggle below, you will see the log file from our failed attempt to solve d657.
 Toggle Cloak
idd657log
Show d657 log
 Cloak
idd657log
 excerpt d657 log
As stated on the TSPLIB website, the optimal solution for this problem is 48912. By looking through the logs, you see that after only about 25,000 nodes, we reach a solution with objective 48913. Unfortunately, our lower bound, while initially 99.3% of the optimal solution, increases very slowly. Using the 
src/output/NodeLog.java
_
, 
 
 we 
 
 turned 
 
 the 
 
 node 
 
 log 
 
 into 
 
 the 
 
 plot 
 
 below 
 
 illustrating 
 
 how 
 
 slowly 
 
 our 
 
 lower 
 
 bound 
 
 is 
 
 converging, 
 
 in 
 
 comparison 
 
 to 
 
 our 
 
 upper 
 
 bound. 
  
 Even 
 
 after 
 
 creating 
 
 over 
 
 300,000 
 
 nodes 
 
 in 
 
 branch 
 
 and 
 
 bound, 
 
 we 
 
 have 
 
 quite 
 
 a 
 
 way 
 
 to 
 
 go 
 
 proving 
 
 optimality. 
  
 This 
 
 suggests 
 
 that 
 
 our 
 
 next 
 
 few 
 
 optimizations 
 
 should 
 
 be 
 
 in 
 
 trying 
 
 to 
 
 improve 
 
 our 
 
 lower 
 
 bounds.


{
 Excerpt Include
:
excerpt d657 table
excerpt 
 
 d657 
 
 table
}


Looking 
 
 more 
 
 closely 
 
 at 
 
 the 
 
 log 
 
 file, 
 
 we 
 
 see 
 
 that 
 
 there 
 
 were 
 
 not 
 
 many 
 
 instances 
 
 where 
 
 two-opt 
 
 was 
 
 able 
 
 to 
 
 improve 
 
 an 
 
 integer 
 
 solution 
 
 generated 
 
 by 
 
 CPLEX. 
  
 We 
 
 see 
 
 that 
 
 every 
 
 "
\
*" 
 
 in 
 
 the 
 
 log, 
 
 which 
 
 indicate 
 
 where 
 
 new 
 
 incumbent 
 
 solutions 
 
 have 
 
 been 
 
 found, 
 
 is 
 
 accompanied 
 
 by 
 
 a 
 
 "+", 
 
 which 
 
 indicates 
 
 that 
 
 a 
 
 heuristic 
 
 of 
 
 some 
 
 kind 
 
 (either 
 
 heuristic 
 
 callback 
 
 or 
 
 internal 
 
 CPLEX 
 
 heuristic) 
 
 was 
 
 used 
 
 (as 
 
 opposed 
 
 to 
 
 the 
 
 solution 
 
 to 
 
 the 
 
 LP 
 
 at 
 
 a 
 
 node 
 
 being 
 
 integral). 
  
 We 
 
 can 
 
 see 
 
 from 
 
 the 
 
 print 
 
 statements 
 
 that 
 
 the 
 
 first 
 
 few 
 
 "
\
*" 
 
 are 
 
 from 
 
 the 
 
 heuristic 
 
 callback, 
 
 and 
 
 that 
 
 two-opt 
 
 significantly 
 
 improved 
 
 the 
 
 quality 
 
 of 
 
 these 
 
 solutions. 
   
 However, 
 
 for 
 
 the 
 
 remaining 
 
 solutions, 
 
 we 
 
 see 
 
 that 
 
 two-opt 
 
 generally 
 
 made 
 
 no 
 
 improvement. 
  
 Perhaps 
 
 this 
 
 is 
 
 because 
 
 CPLEX's 
 
 internal 
 
 heuristics 
 
 already 
 
 applied 
 
 some 
 
 kind 
 
 of 
 
 local 
 
 search, 
 
 (read 
 
 about 
 
 RINS 
 [
in 
 
 the 
 
 manual
|http://pic.dhe.ibm.com/infocenter/cosinfoc/v12r5/index.jsp?topic=%2Filog.odms.cplex.help%2FCPLEX%2FUsrMan%2Ftopics%2Fdiscr_optim%2Fmip%2Fheuristics%2F42_heur_title_synopsis.html]
). 
  
 However, 
 
 if 
 
 we 
 
 considered 
 
 a 
 
 more 
 
 powerful 
 
 heuristic 
 
 than 
 
 two-opt, 
 
 perhaps 
 
 we 
 
 could 
 
 still 
 
 make 
 
 some 
 
 improvement. 
  
 Note 
 
 that 
 
 in 
 
 general, 
 
 our 
 {{
IncumbentCallback
}} 
 can 
 
 still 
 
 improve 
 
 the 
 
 optimal 
 
 solution. 
  
 To 
 
 see 
 
 it 
 
 in 
 
 action, 
 
 turn 
 
 off 
 
 the 
 
 option 
 {{
christofidesHeuristic
}} 
 and 
 
 run 
 {{
d493
}}
.







{column} 
{section}