The Christmas Card Conundrum 2022

Problem Description:

The job is to determine the most optimal way to craft this year’s Christmas card, by selecting the most efficient path of both moving the robotic arm and changing the print color to craft this year’s image. Each link of the printer arm can be moved independently each step, but you'll also need to account for the time needed to change the printing color.

Considerations:

  • 8-axis robotic arm print one pixel of the card at a time
  • It is neccesariy to spend the least amount of cost possible making the card, minimizing Reconfiguration Cost and Color Change Cost.

This can be solve as a TPS optimization problem.

Import Libraries

¶

In [448]:
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns

Proposed Solution

¶

The problem can be divided in two:

  • Set contraints to the arm configurations space.
  • Find a solution in color space with these constrains

Set contraints to the arm configurations space¶

There is a robotic arm with eight links with lengths [64,32,16,8,4,2,1,1][64,32,16,8,4,2,1,1], this arm must "print" each point of the 257x257 image.

image.png

The configuration of the arm is described by a list of displacement vectors, like:

[(x1,y1),(x2,y2),(x3,y3),(x4,y4),(x5,y5),(x6,y6),(x7,y7),(x8,y8)][(x1,y1),(x2,y2),(x3,y3),(x4,y4),(x5,y5),(x6,y6),(x7,y7),(x8,y8)] where a vector (xi,yi)(xi,yi) of length lili must satisfy max(|xi|,|yi|)=limax(|xi|,|yi|)=li.

This condition means that at least one of the components of the vector must be equal to plus-or-minus the length of the vector. But also, implies a non-Eclidean space problem since the Ecludian length of vectors change to satisfy this condition.

E.g.:

Displacement vector: [(64,4),(32,4),(16,8),(8,4),(4,2),(2,2),(1,1),(1,1)]==(64,72)[(64,4),(32,4),(16,8),(8,4),(4,2),(2,2),(1,1),(1,1)]==(64,72) final pixel.

image.png

As you can expect, there are equivalent arm configurations that end up in the same pixel, but there is a differente cost for them. In total there are ~4.8x10114.8x1011 possible arm configurations, which is the most cost-efficient sequence?.

It was stated here that is possible to reduce the arm configuration search. "The robot has been constrained so that the first (longest) arm always points to the right side and the other seven arms always point upwards.". In such a way that is possible to match each (x,y) point to a certain arm configuration for the top-right quarter of the image, and even the others the configurations are rotated in multiples of 90 degress.

For each quadrant of the image a certain arm configuration form is obtained:



    

  • Top right quarter:     [( 64,   ), (   , 32), (  ,  16), (   , 8 ), (   ,  4), (   ,  2), (   ,  1), (   ,  1)]
    • 

  • Bottom right quarter:  [(   ,-64), ( 32,   ), ( 16,   ), (  8,   ), (  4,   ), (  2,   ), (  1,   ), (  1,   )]
    • 

  • Top left quarter:      [(   , 64), (-32,   ), (-16,   ), ( -8,   ), ( -4,   ), ( -2,   ), ( -1,   ), ( -1,   )]
    • 

  • Bottom left quarter:   [(-64,   ), (   ,-32), (   ,-16), (   ,-8 ), (   , -4), (   , -2), (   , -1), (   , -1)]

This is a 8-dimension problem that can be reduced with this constrain.
    •
In [452]:
def standard_config_topright(x, y):
    """Return the preferred configuration (list of eight pairs) for the point (x,y)"""
    assert x > 0 and y >= 0, "This function is only for the upper right quadrant"
    r = 64
    config = [(r, y-r)] # longest arm points to the right
    x = x - config[0][0]
    while r > 1:
        r = r // 2
        arm_x = np.clip(x, -r, r)
        config.append((arm_x, r)) # arm points upwards
        x -= arm_x
    arm_x = np.clip(x, -r, r)
    config.append((arm_x, r)) # arm points upwards
    assert x == arm_x
    return config

def prefer_config(x,y):
    #assert ~(x==0 and y==0), "Do not consider origin (0,0)" 
    
    if x>0 and y >= 0: # top right quadrant
        return standard_config_topright(x, y)
    
    if x>=0 and y<0: # bottom right quadrant
        rotated_config = standard_config_topright(-y, x)
        return [(y, -x) for (x, y) in rotated_config]
    
    if x<=0 and y>0: # top left quadrant
        rotated_config = standard_config_topright(y, -x)
        return [(-y, x) for (x, y) in rotated_config]
    
    if x<0 and y<=0: # bottom left quadrant
        rotated_config = standard_config_topright(-x, -y)
        return [(-x,-y) for (x,y) in rotated_config]
    
    return None #"Do not considered origin (0,0)"
In [453]:
def df_to_image(df):
    side = int(len(df) ** 0.5)  # assumes a square image
    df1 = df.set_index(['x', 'y']).to_numpy().reshape(side, side, -1)
    return np.array(df1, dtype='float32')
In [454]:
df_image = pd.read_csv('/kaggle/input/santa-2022/image.csv')
image = df_to_image(df_image)
In [455]:
df_q1 = df_image[(df_image['x']>=1) & (df_image['y']>=0)].reset_index(drop=True)

df_q2 = (df_image[(df_image['x']>=0) & (df_image['y']<=-1)]
         .sort_values(by=['y','x'], ascending=[0,0])
         .reset_index(drop=True))

df_q3 = df_image[(df_image['x']<=-1) & (df_image['y']<=0)].iloc[::-1].reset_index(drop=True)

# ignore section x=0, y>0
df_q4 = (df_image[(df_image['x']<=-1) & (df_image['y']>=1)]
         .sort_values(by=['y','x'], ascending=[1,1])
         .reset_index(drop=True))
In [456]:
### Auxiliar Dictionaries

df_q1_dict = {(el[0], el[1]):cnt for cnt,el in enumerate(df_q1[['x','y']].values)}
df_q2_dict = {(el[0], el[1]):cnt for cnt,el in enumerate(df_q2[['x','y']].values)}
df_q3_dict = {(el[0], el[1]):cnt for cnt,el in enumerate(df_q3[['x','y']].values)}
df_q4_dict = {(el[0], el[1]):cnt for cnt,el in enumerate(df_q4[['x','y']].values)}

df_q1_dict_rev = {v: k for k, v in df_q1_dict.items()}
df_q2_dict_rev = {v: k for k, v in df_q2_dict.items()}
df_q3_dict_rev = {v: k for k, v in df_q3_dict.items()}
df_q4_dict_rev = {v: k for k, v in df_q4_dict.items()}

LKH Implementation

¶

As stated here, LKH is an effective implementation of the Lin-Kernighan heuristic for solving the traveling salesman problem .

In [8]:
%%bash -e
wget http://akira.ruc.dk/~keld/research/LKH-3/LKH-3.0.8.tgz
tar xvfz LKH-3.0.8.tgz

cd LKH-3.0.8
make

--2023-09-26 14:49:17--  http://akira.ruc.dk/~keld/research/LKH-3/LKH-3.0.8.tgz
Resolving akira.ruc.dk (akira.ruc.dk)... 130.225.220.230
Connecting to akira.ruc.dk (akira.ruc.dk)|130.225.220.230|:80... connected.
HTTP request sent, awaiting response... 200 OK
Length: 2318525 (2.2M) [application/x-gzip]
Saving to: ‘LKH-3.0.8.tgz’

     0K .......... .......... .......... .......... ..........  2% 1.62M 1s
    50K .......... .......... .......... .......... ..........  4% 2.48M 1s
   100K .......... .......... .......... .......... ..........  6% 4.34M 1s
   150K .......... .......... .......... .......... ..........  8% 6.76M 1s
   200K .......... .......... .......... .......... .......... 11% 7.01M 1s
   250K .......... .......... .......... .......... .......... 13% 14.1M 1s
   300K .......... .......... .......... .......... .......... 15% 13.1M 0s
   350K .......... .......... .......... .......... .......... 17% 25.7M 0s
   400K .......... .......... .......... .......... .......... 19% 12.8M 0s
   450K .......... .......... .......... .......... .......... 22% 13.9M 0s
   500K .......... .......... .......... .......... .......... 24% 16.2M 0s
   550K .......... .......... .......... .......... .......... 26% 37.4M 0s
   600K .......... .......... .......... .......... .......... 28% 17.4M 0s
   650K .......... .......... .......... .......... .......... 30% 9.44M 0s
   700K .......... .......... .......... .......... .......... 33% 61.8M 0s
   750K .......... .......... .......... .......... .......... 35% 29.6M 0s
   800K .......... .......... .......... .......... .......... 37% 53.8M 0s
   850K .......... .......... .......... .......... .......... 39%  580M 0s
   900K .......... .......... .......... .......... .......... 41%  444M 0s
   950K .......... .......... .......... .......... .......... 44%  621M 0s
  1000K .......... .......... .......... .......... .......... 46%  172M 0s
  1050K .......... .......... .......... .......... .......... 48% 35.4M 0s
  1100K .......... .......... .......... .......... .......... 50% 69.4M 0s
  1150K .......... .......... .......... .......... .......... 52% 41.4M 0s
  1200K .......... .......... .......... .......... .......... 55% 65.0M 0s
  1250K .......... .......... .......... .......... .......... 57% 42.1M 0s
  1300K .......... .......... .......... .......... .......... 59% 21.0M 0s
  1350K .......... .......... .......... .......... .......... 61% 10.7M 0s
  1400K .......... .......... .......... .......... .......... 64% 39.6M 0s
  1450K .......... .......... .......... .......... .......... 66% 43.7M 0s
  1500K .......... .......... .......... .......... .......... 68% 68.6M 0s
  1550K .......... .......... .......... .......... .......... 70% 34.5M 0s
  1600K .......... .......... .......... .......... .......... 72%  106M 0s
  1650K .......... .......... .......... .......... .......... 75% 32.5M 0s
  1700K .......... .......... .......... .......... .......... 77%  169M 0s
  1750K .......... .......... .......... .......... .......... 79% 37.5M 0s
  1800K .......... .......... .......... .......... .......... 81% 6.78M 0s
  1850K .......... .......... .......... .......... .......... 83%  146M 0s
  1900K .......... .......... .......... .......... .......... 86% 35.0M 0s
  1950K .......... .......... .......... .......... .......... 88% 36.9M 0s
  2000K .......... .......... .......... .......... .......... 90%  298M 0s
  2050K .......... .......... .......... .......... .......... 92% 53.8M 0s
  2100K .......... .......... .......... .......... .......... 94% 12.2M 0s
  2150K .......... .......... .......... .......... .......... 97%  297M 0s
  2200K .......... .......... .......... .......... .......... 99%  363M 0s
  2250K .......... ....                                       100% 14.6M=0.1s

2023-09-26 14:49:17 (15.3 MB/s) - ‘LKH-3.0.8.tgz’ saved [2318525/2318525]


LKH-3.0.8/
LKH-3.0.8/pr2392.par
LKH-3.0.8/whizzkids96.atsp
LKH-3.0.8/Makefile
LKH-3.0.8/whizzkids96.par
LKH-3.0.8/pr2392.tsp
LKH-3.0.8/DOC/
LKH-3.0.8/README.txt
LKH-3.0.8/SRC/
LKH-3.0.8/SRC/Penalty_CVRPTW.c
LKH-3.0.8/SRC/RestoreTour.c
LKH-3.0.8/SRC/SolveKMeansSubproblems.c
LKH-3.0.8/SRC/IsCommonEdge.c
LKH-3.0.8/SRC/Penalty_TSPPD.c
LKH-3.0.8/SRC/ReadProblem.c
LKH-3.0.8/SRC/BestKOptMove.c
LKH-3.0.8/SRC/Distance_SPECIAL.c
LKH-3.0.8/SRC/Penalty_TSPDL.c
LKH-3.0.8/SRC/Penalty_PDPTW.c
LKH-3.0.8/SRC/Penalty_ACVRP.c
LKH-3.0.8/SRC/CreateCandidateSet.c
LKH-3.0.8/SRC/OBJ/
LKH-3.0.8/SRC/Forbidden.c
LKH-3.0.8/SRC/Penalty_CCVRP.c
LKH-3.0.8/SRC/Penalty_M_PDTSP.c
LKH-3.0.8/SRC/Best5OptMove.c
LKH-3.0.8/SRC/RecordBetterTour.c
LKH-3.0.8/SRC/Best4OptMove.c
LKH-3.0.8/SRC/Exclude.c
LKH-3.0.8/SRC/C.c
LKH-3.0.8/SRC/IsCandidate.c
LKH-3.0.8/SRC/Make3OptMove.c
LKH-3.0.8/SRC/Make2OptMove.c
LKH-3.0.8/SRC/ResetCandidateSet.c
LKH-3.0.8/SRC/LKHmain.c
LKH-3.0.8/SRC/SolveSFCSubproblems.c
LKH-3.0.8/SRC/ERXT.c
LKH-3.0.8/SRC/fscanint.c
LKH-3.0.8/SRC/eprintf.c
LKH-3.0.8/SRC/Distance_SOP.c
LKH-3.0.8/SRC/Distance_MTSP.c
LKH-3.0.8/SRC/Penalty_VRPPD.c
LKH-3.0.8/SRC/SINTEF_WriteSolution.c
LKH-3.0.8/SRC/Gain23.c
LKH-3.0.8/SRC/Heap.c
LKH-3.0.8/SRC/GetTime.c
LKH-3.0.8/SRC/SolveRoheSubproblems.c
LKH-3.0.8/SRC/ReadPenalties.c
LKH-3.0.8/SRC/Excludable.c
LKH-3.0.8/SRC/SolveCompressedSubproblem.c
LKH-3.0.8/SRC/Statistics.c
LKH-3.0.8/SRC/PatchCycles.c
LKH-3.0.8/SRC/MergeWithTourGPX2.c
LKH-3.0.8/SRC/Sequence.c
LKH-3.0.8/SRC/SolveDelaunaySubproblems.c
LKH-3.0.8/SRC/WritePenalties.c
LKH-3.0.8/SRC/NormalizeNodeList.c
LKH-3.0.8/SRC/FreeStructures.c
LKH-3.0.8/SRC/SolveKarpSubproblems.c
LKH-3.0.8/SRC/Makefile
LKH-3.0.8/SRC/CVRP_InitialTour.c
LKH-3.0.8/SRC/Between_SL.c
LKH-3.0.8/SRC/Penalty_OVRP.c
LKH-3.0.8/SRC/SOP_InitialTour.c
LKH-3.0.8/SRC/INCLUDE/
LKH-3.0.8/SRC/Penalty_MLP.c
LKH-3.0.8/SRC/IsPossibleCandidate.c
LKH-3.0.8/SRC/Penalty_VRPBTW.c
LKH-3.0.8/SRC/NormalizeSegmentList.c
LKH-3.0.8/SRC/Penalty_BWTSP.c
LKH-3.0.8/SRC/STTSP2TSP.c
LKH-3.0.8/SRC/Hashing.c
LKH-3.0.8/SRC/LinKernighan.c
LKH-3.0.8/SRC/Penalty_CVRP.c
LKH-3.0.8/SRC/gpx.c
LKH-3.0.8/SRC/AdjustCandidateSet.c
LKH-3.0.8/SRC/AllocateStructures.c
LKH-3.0.8/SRC/Flip_SSL.c
LKH-3.0.8/SRC/MakeKOptMove.c
LKH-3.0.8/SRC/BuildKDTree.c
LKH-3.0.8/SRC/SolveTourSegmentSubproblems.c
LKH-3.0.8/SRC/Random.c
LKH-3.0.8/SRC/CreateDelaunayCandidateSet.c
LKH-3.0.8/SRC/MTSP_WriteSolution.c
LKH-3.0.8/SRC/Penalty_PDTSPF.c
LKH-3.0.8/SRC/SolveSubproblemBorderProblems.c
LKH-3.0.8/SRC/Penalty_PDTSPL.c
LKH-3.0.8/SRC/ReadParameters.c
LKH-3.0.8/SRC/MTSP_Report.c
LKH-3.0.8/SRC/Penalty_TRP.c
LKH-3.0.8/SRC/FixedOrCommonCandidates.c
LKH-3.0.8/SRC/Penalty_CTSP.c
LKH-3.0.8/SRC/Penalty_SOP.c
LKH-3.0.8/SRC/Best2OptMove.c
LKH-3.0.8/SRC/Best3OptMove.c
LKH-3.0.8/SRC/ReadCandidates.c
LKH-3.0.8/SRC/Make4OptMove.c
LKH-3.0.8/SRC/Make5OptMove.c
LKH-3.0.8/SRC/CreateNNCandidateSet.c
LKH-3.0.8/SRC/GenerateCandidates.c
LKH-3.0.8/SRC/Between.c
LKH-3.0.8/SRC/Flip_SL.c
LKH-3.0.8/SRC/SOP_RepairTour.c
LKH-3.0.8/SRC/Activate.c
LKH-3.0.8/SRC/SegmentSize.c
LKH-3.0.8/SRC/SolveSubproblem.c
LKH-3.0.8/SRC/MergeWithTourIPT.c
LKH-3.0.8/SRC/StoreTour.c
LKH-3.0.8/SRC/GreedyTour.c
LKH-3.0.8/SRC/PrintParameters.c
LKH-3.0.8/SRC/Penalty_M1_PDTSP.c
LKH-3.0.8/SRC/SFCTour.c
LKH-3.0.8/SRC/Penalty_PDTSP.c
LKH-3.0.8/SRC/Penalty_VRPB.c
LKH-3.0.8/SRC/Minimum1TreeCost.c
LKH-3.0.8/SRC/MTSP2TSP.c
LKH-3.0.8/SRC/MergeTourWithBestTour.c
LKH-3.0.8/SRC/ReadEdges.c
LKH-3.0.8/SRC/BridgeGain.c
LKH-3.0.8/SRC/WriteCandidates.c
LKH-3.0.8/SRC/PDPTW_Reduce.c
LKH-3.0.8/SRC/Flip.c
LKH-3.0.8/SRC/WriteTour.c
LKH-3.0.8/SRC/Delaunay.c
LKH-3.0.8/SRC/TSPDL_InitialTour.c
LKH-3.0.8/SRC/VRPB_Reduce.c
LKH-3.0.8/SRC/CreateQuadrantCandidateSet.c
LKH-3.0.8/SRC/IsBackboneCandidate.c
LKH-3.0.8/SRC/Penalty_MTSP.c
LKH-3.0.8/SRC/ReadLine.c
LKH-3.0.8/SRC/RecordBestTour.c
LKH-3.0.8/SRC/CandidateReport.c
LKH-3.0.8/SRC/OrderCandidateSet.c
LKH-3.0.8/SRC/CTSP_InitialTour.c
LKH-3.0.8/SRC/AddExtraCandidates.c
LKH-3.0.8/SRC/Distance.c
LKH-3.0.8/SRC/Genetic.c
LKH-3.0.8/SRC/AdjustClusters.c
LKH-3.0.8/SRC/AddTourCandidates.c
LKH-3.0.8/SRC/BIT.c
LKH-3.0.8/SRC/KSwapKick.c
LKH-3.0.8/SRC/Connect.c
LKH-3.0.8/SRC/RemoveFirstActive.c
LKH-3.0.8/SRC/Ascent.c
LKH-3.0.8/SRC/TrimCandidateSet.c
LKH-3.0.8/SRC/StatusReport.c
LKH-3.0.8/SRC/LKH.c
LKH-3.0.8/SRC/TSPTW_Reduce.c
LKH-3.0.8/SRC/printff.c
LKH-3.0.8/SRC/Between_SSL.c
LKH-3.0.8/SRC/SOP_Report.c
LKH-3.0.8/SRC/Create_POPMUSIC_CandidateSet.c
LKH-3.0.8/SRC/MTSP_InitialTour.c
LKH-3.0.8/SRC/Improvement.c
LKH-3.0.8/SRC/GeoConversion.c
LKH-3.0.8/SRC/FindTour.c
LKH-3.0.8/SRC/TSPTW_MakespanCost.c
LKH-3.0.8/SRC/SymmetrizeCandidateSet.c
LKH-3.0.8/SRC/ChooseInitialTour.c
LKH-3.0.8/SRC/SolveKCenterSubproblems.c
LKH-3.0.8/SRC/Penalty_1_PDTSP.c
LKH-3.0.8/SRC/AddCandidate.c
LKH-3.0.8/SRC/MergeWithTourCLARIST.c
LKH-3.0.8/SRC/Penalty_TSPTW.c
LKH-3.0.8/SRC/Penalty_RCTVRP.c
LKH-3.0.8/SRC/MinimumSpanningTree.c
LKH-3.0.8/SRC/BestSpecialOptMove.c
LKH-3.0.8/SRC/INCLUDE/Genetic.h
LKH-3.0.8/SRC/INCLUDE/Segment.h
LKH-3.0.8/SRC/INCLUDE/Delaunay.h
LKH-3.0.8/SRC/INCLUDE/GeoConversion.h
LKH-3.0.8/SRC/INCLUDE/LKH.h
LKH-3.0.8/SRC/INCLUDE/BIT.h
LKH-3.0.8/SRC/INCLUDE/CLARIST.h
LKH-3.0.8/SRC/INCLUDE/Sequence.h
LKH-3.0.8/SRC/INCLUDE/GainType.h
LKH-3.0.8/SRC/INCLUDE/Heap.h
LKH-3.0.8/SRC/INCLUDE/Hashing.h
LKH-3.0.8/SRC/INCLUDE/gpx.h
LKH-3.0.8/DOC/POPMUSIC_REPORT.pdf
LKH-3.0.8/DOC/LKH_Genetic.pdf
LKH-3.0.8/DOC/LKH_REPORT.pdf
LKH-3.0.8/DOC/LKH-2_USER_GUIDE.pdf
LKH-3.0.8/DOC/TSPLIB_DOC.pdf
LKH-3.0.8/DOC/LKH-3_PARAMETERS.pdf
LKH-3.0.8/DOC/LKH-3_REPORT.pdf
make -C SRC
make[1]: Entering directory '/kaggle/working/LKH-3.0.8/SRC'
make LKH
make[2]: Entering directory '/kaggle/working/LKH-3.0.8/SRC'
cc -c -o OBJ/Activate.o Activate.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/AddCandidate.o AddCandidate.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/AddExtraCandidates.o AddExtraCandidates.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/AddTourCandidates.o AddTourCandidates.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/AdjustCandidateSet.o AdjustCandidateSet.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/AdjustClusters.o AdjustClusters.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/AllocateStructures.o AllocateStructures.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Ascent.o Ascent.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Best2OptMove.o Best2OptMove.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Best3OptMove.o Best3OptMove.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Best4OptMove.o Best4OptMove.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Best5OptMove.o Best5OptMove.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/BestKOptMove.o BestKOptMove.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/BestSpecialOptMove.o BestSpecialOptMove.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Between.o Between.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Between_SL.o Between_SL.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Between_SSL.o Between_SSL.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/BridgeGain.o BridgeGain.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/BuildKDTree.o BuildKDTree.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/C.o C.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/CandidateReport.o CandidateReport.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/ChooseInitialTour.o ChooseInitialTour.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Connect.o Connect.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/CreateCandidateSet.o CreateCandidateSet.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/CreateDelaunayCandidateSet.o CreateDelaunayCandidateSet.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/CreateNNCandidateSet.o CreateNNCandidateSet.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Create_POPMUSIC_CandidateSet.o Create_POPMUSIC_CandidateSet.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/CreateQuadrantCandidateSet.o CreateQuadrantCandidateSet.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/CTSP_InitialTour.o CTSP_InitialTour.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/CVRP_InitialTour.o CVRP_InitialTour.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Delaunay.o Delaunay.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Distance.o Distance.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Distance_MTSP.o Distance_MTSP.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Distance_SOP.o Distance_SOP.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Distance_SPECIAL.o Distance_SPECIAL.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/eprintf.o eprintf.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/ERXT.o ERXT.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Excludable.o Excludable.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Exclude.o Exclude.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/FindTour.o FindTour.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/FixedOrCommonCandidates.o FixedOrCommonCandidates.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Flip.o Flip.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Flip_SL.o Flip_SL.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Flip_SSL.o Flip_SSL.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Forbidden.o Forbidden.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/FreeStructures.o FreeStructures.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/fscanint.o fscanint.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Gain23.o Gain23.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/GenerateCandidates.o GenerateCandidates.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Genetic.o Genetic.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/GeoConversion.o GeoConversion.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/GetTime.o GetTime.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/GreedyTour.o GreedyTour.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Hashing.o Hashing.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Heap.o Heap.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Improvement.o Improvement.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/IsBackboneCandidate.o IsBackboneCandidate.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/IsCandidate.o IsCandidate.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/IsCommonEdge.o IsCommonEdge.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/IsPossibleCandidate.o IsPossibleCandidate.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/KSwapKick.o KSwapKick.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/LinKernighan.o LinKernighan.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/LKHmain.o LKHmain.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Make2OptMove.o Make2OptMove.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Make3OptMove.o Make3OptMove.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Make4OptMove.o Make4OptMove.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Make5OptMove.o Make5OptMove.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/MakeKOptMove.o MakeKOptMove.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/MergeTourWithBestTour.o MergeTourWithBestTour.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/MergeWithTourIPT.o MergeWithTourIPT.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Minimum1TreeCost.o Minimum1TreeCost.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/MinimumSpanningTree.o MinimumSpanningTree.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/MTSP2TSP.o MTSP2TSP.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/MTSP_InitialTour.o MTSP_InitialTour.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/MTSP_Report.o MTSP_Report.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/MTSP_WriteSolution.o MTSP_WriteSolution.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/NormalizeNodeList.o NormalizeNodeList.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/NormalizeSegmentList.o NormalizeSegmentList.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/OrderCandidateSet.o OrderCandidateSet.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/PatchCycles.o PatchCycles.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Penalty_ACVRP.o Penalty_ACVRP.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Penalty_BWTSP.o Penalty_BWTSP.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Penalty_CCVRP.o Penalty_CCVRP.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Penalty_CVRP.o Penalty_CVRP.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Penalty_CVRPTW.o Penalty_CVRPTW.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Penalty_CTSP.o Penalty_CTSP.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Penalty_1_PDTSP.o Penalty_1_PDTSP.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Penalty_MLP.o Penalty_MLP.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Penalty_M_PDTSP.o Penalty_M_PDTSP.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Penalty_M1_PDTSP.o Penalty_M1_PDTSP.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Penalty_MTSP.o Penalty_MTSP.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Penalty_OVRP.o Penalty_OVRP.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Penalty_PDPTW.o Penalty_PDPTW.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Penalty_PDTSP.o Penalty_PDTSP.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Penalty_PDTSPF.o Penalty_PDTSPF.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Penalty_PDTSPL.o Penalty_PDTSPL.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Penalty_RCTVRP.o Penalty_RCTVRP.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Penalty_SOP.o Penalty_SOP.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Penalty_TRP.o Penalty_TRP.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Penalty_TSPDL.o Penalty_TSPDL.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Penalty_TSPPD.o Penalty_TSPPD.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Penalty_TSPTW.o Penalty_TSPTW.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Penalty_VRPB.o Penalty_VRPB.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Penalty_VRPBTW.o Penalty_VRPBTW.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Penalty_VRPPD.o Penalty_VRPPD.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/PDPTW_Reduce.o PDPTW_Reduce.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/printff.o printff.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/PrintParameters.o PrintParameters.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Random.o Random.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/ReadCandidates.o ReadCandidates.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/ReadEdges.o ReadEdges.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon

ReadEdges.c: In function ‘ReadEdges’:
ReadEdges.c:31:9: warning: ignoring return value of ‘fscanf’, declared with attribute warn_unused_result [-Wunused-result]
   31 |         fscanf(EdgeFile, "%d %d\n", &i, &Edges);
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ReadEdges.c:36:13: warning: ignoring return value of ‘fgets’, declared with attribute warn_unused_result [-Wunused-result]
   36 |             fgets(line, 80, EdgeFile);
      |             ^~~~~~~~~~~~~~~~~~~~~~~~~

cc -c -o OBJ/ReadLine.o ReadLine.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/ReadParameters.o ReadParameters.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/ReadPenalties.o ReadPenalties.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/ReadProblem.o ReadProblem.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon

ReadProblem.c: In function ‘Read_EDGE_DATA_SECTION’:
ReadProblem.c:1209:21: warning: ignoring return value of ‘fscanf’, declared with attribute warn_unused_result [-Wunused-result]
 1209 |                     fscanf(ProblemFile, "%lf", &w);
      |                     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

cc -c -o OBJ/RecordBestTour.o RecordBestTour.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/RecordBetterTour.o RecordBetterTour.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/RemoveFirstActive.o RemoveFirstActive.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/ResetCandidateSet.o ResetCandidateSet.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/RestoreTour.o RestoreTour.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/SegmentSize.o SegmentSize.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Sequence.o Sequence.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/SFCTour.o SFCTour.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/SolveCompressedSubproblem.o SolveCompressedSubproblem.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/SINTEF_WriteSolution.o SINTEF_WriteSolution.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/SOP_RepairTour.o SOP_RepairTour.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/STTSP2TSP.o STTSP2TSP.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/SolveDelaunaySubproblems.o SolveDelaunaySubproblems.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/SolveKarpSubproblems.o SolveKarpSubproblems.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/SolveKCenterSubproblems.o SolveKCenterSubproblems.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/SolveKMeansSubproblems.o SolveKMeansSubproblems.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/SolveRoheSubproblems.o SolveRoheSubproblems.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/SolveSFCSubproblems.o SolveSFCSubproblems.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/SolveSubproblem.o SolveSubproblem.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/SolveSubproblemBorderProblems.o SolveSubproblemBorderProblems.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/SolveTourSegmentSubproblems.o SolveTourSegmentSubproblems.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/SOP_InitialTour.o SOP_InitialTour.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/SOP_Report.o SOP_Report.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/StatusReport.o StatusReport.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/Statistics.o Statistics.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/StoreTour.o StoreTour.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/SymmetrizeCandidateSet.o SymmetrizeCandidateSet.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/TrimCandidateSet.o TrimCandidateSet.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/TSPDL_InitialTour.o TSPDL_InitialTour.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/TSPTW_MakespanCost.o TSPTW_MakespanCost.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/TSPTW_Reduce.o TSPTW_Reduce.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/VRPB_Reduce.o VRPB_Reduce.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/BIT.o BIT.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/WriteCandidates.o WriteCandidates.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/WritePenalties.o WritePenalties.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/WriteTour.o WriteTour.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/MergeWithTourGPX2.o MergeWithTourGPX2.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/gpx.o gpx.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/MergeWithTourCLARIST.o MergeWithTourCLARIST.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -c -o OBJ/LKH.o LKH.c -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon
cc -o ../LKH OBJ/Activate.o OBJ/AddCandidate.o OBJ/AddExtraCandidates.o OBJ/AddTourCandidates.o OBJ/AdjustCandidateSet.o OBJ/AdjustClusters.o OBJ/AllocateStructures.o OBJ/Ascent.o OBJ/Best2OptMove.o OBJ/Best3OptMove.o OBJ/Best4OptMove.o OBJ/Best5OptMove.o OBJ/BestKOptMove.o OBJ/BestSpecialOptMove.o OBJ/Between.o OBJ/Between_SL.o OBJ/Between_SSL.o OBJ/BridgeGain.o OBJ/BuildKDTree.o OBJ/C.o OBJ/CandidateReport.o OBJ/ChooseInitialTour.o OBJ/Connect.o OBJ/CreateCandidateSet.o OBJ/CreateDelaunayCandidateSet.o OBJ/CreateNNCandidateSet.o OBJ/Create_POPMUSIC_CandidateSet.o OBJ/CreateQuadrantCandidateSet.o OBJ/CTSP_InitialTour.o OBJ/CVRP_InitialTour.o OBJ/Delaunay.o OBJ/Distance.o OBJ/Distance_MTSP.o OBJ/Distance_SOP.o OBJ/Distance_SPECIAL.o OBJ/eprintf.o OBJ/ERXT.o OBJ/Excludable.o OBJ/Exclude.o OBJ/FindTour.o OBJ/FixedOrCommonCandidates.o OBJ/Flip.o OBJ/Flip_SL.o OBJ/Flip_SSL.o OBJ/Forbidden.o OBJ/FreeStructures.o OBJ/fscanint.o OBJ/Gain23.o OBJ/GenerateCandidates.o OBJ/Genetic.o OBJ/GeoConversion.o OBJ/GetTime.o OBJ/GreedyTour.o OBJ/Hashing.o OBJ/Heap.o OBJ/Improvement.o OBJ/IsBackboneCandidate.o OBJ/IsCandidate.o OBJ/IsCommonEdge.o OBJ/IsPossibleCandidate.o OBJ/KSwapKick.o OBJ/LinKernighan.o OBJ/LKHmain.o OBJ/Make2OptMove.o OBJ/Make3OptMove.o OBJ/Make4OptMove.o OBJ/Make5OptMove.o OBJ/MakeKOptMove.o OBJ/MergeTourWithBestTour.o OBJ/MergeWithTourIPT.o OBJ/Minimum1TreeCost.o OBJ/MinimumSpanningTree.o OBJ/MTSP2TSP.o OBJ/MTSP_InitialTour.o OBJ/MTSP_Report.o OBJ/MTSP_WriteSolution.o OBJ/NormalizeNodeList.o OBJ/NormalizeSegmentList.o OBJ/OrderCandidateSet.o OBJ/PatchCycles.o OBJ/Penalty_ACVRP.o OBJ/Penalty_BWTSP.o OBJ/Penalty_CCVRP.o OBJ/Penalty_CVRP.o OBJ/Penalty_CVRPTW.o OBJ/Penalty_CTSP.o OBJ/Penalty_1_PDTSP.o OBJ/Penalty_MLP.o OBJ/Penalty_M_PDTSP.o OBJ/Penalty_M1_PDTSP.o OBJ/Penalty_MTSP.o OBJ/Penalty_OVRP.o OBJ/Penalty_PDPTW.o OBJ/Penalty_PDTSP.o OBJ/Penalty_PDTSPF.o OBJ/Penalty_PDTSPL.o OBJ/Penalty_RCTVRP.o OBJ/Penalty_SOP.o OBJ/Penalty_TRP.o OBJ/Penalty_TSPDL.o OBJ/Penalty_TSPPD.o OBJ/Penalty_TSPTW.o OBJ/Penalty_VRPB.o OBJ/Penalty_VRPBTW.o OBJ/Penalty_VRPPD.o OBJ/PDPTW_Reduce.o OBJ/printff.o OBJ/PrintParameters.o OBJ/Random.o OBJ/ReadCandidates.o OBJ/ReadEdges.o OBJ/ReadLine.o OBJ/ReadParameters.o OBJ/ReadPenalties.o OBJ/ReadProblem.o OBJ/RecordBestTour.o OBJ/RecordBetterTour.o OBJ/RemoveFirstActive.o OBJ/ResetCandidateSet.o OBJ/RestoreTour.o OBJ/SegmentSize.o OBJ/Sequence.o OBJ/SFCTour.o OBJ/SolveCompressedSubproblem.o OBJ/SINTEF_WriteSolution.o OBJ/SOP_RepairTour.o OBJ/STTSP2TSP.o OBJ/SolveDelaunaySubproblems.o OBJ/SolveKarpSubproblems.o OBJ/SolveKCenterSubproblems.o OBJ/SolveKMeansSubproblems.o OBJ/SolveRoheSubproblems.o OBJ/SolveSFCSubproblems.o OBJ/SolveSubproblem.o OBJ/SolveSubproblemBorderProblems.o OBJ/SolveTourSegmentSubproblems.o OBJ/SOP_InitialTour.o OBJ/SOP_Report.o OBJ/StatusReport.o OBJ/Statistics.o OBJ/StoreTour.o OBJ/SymmetrizeCandidateSet.o OBJ/TrimCandidateSet.o OBJ/TSPDL_InitialTour.o OBJ/TSPTW_MakespanCost.o OBJ/TSPTW_Reduce.o OBJ/VRPB_Reduce.o OBJ/BIT.o OBJ/WriteCandidates.o OBJ/WritePenalties.o OBJ/WriteTour.o OBJ/MergeWithTourGPX2.o OBJ/gpx.o OBJ/MergeWithTourCLARIST.o OBJ/LKH.o -O3 -Wall -IINCLUDE -DTWO_LEVEL_TREE -g -fcommon -lm
make[2]: Leaving directory '/kaggle/working/LKH-3.0.8/SRC'
make[1]: Leaving directory '/kaggle/working/LKH-3.0.8/SRC'

To use the LKH provided software, predefined cost functions can be used as cost funcitons such as Euclidean or Manhattan distance. However in this case the predifined cost has this form:

Cost Function per Step=√# links changed+3.0∗abs (color difference)Cost Function per Step=# links changed+3.0∗abs (color difference)
  • There is no conflict with color cost calculations between pixels directly, but in the case of reconfiguration cost, it depends on the configurations of the robotic arm where it came from and where it needs to go.
  • Due to the predefined constrains, it is possible to obtain all configurations of the robotic arm within a given quadrant of the image. With this, it is possible to calculate all the pixel changes that can be achieved in a single pass of the robotic arm, and then calculate how many links need to be changed per pixel.
In [458]:
################  Defined cost function for the TPS problem 

from functools import reduce

def check_integrity_config(config1, config2):
    t1 = np.array(config1)
    t2 = np.array(config2)
    return np.max(np.abs(t1 - t2), axis=1).max()

def cost_file(from_position, to_position, image):
    if from_position == to_position: return 0
    
    x1 = 128+from_position[0] ; y1 = 128-from_position[1]
    x2 = 128+to_position[0] ;   y2 = 128-to_position[1]
    
    scale_factor = 3 # color cost
    precision = 100
    
    dx = abs(x1-x2)
    dy = abs(y1-y2)
    
    if dx>3 or dy>3:
        return 14 * precision# high cost
    else:
        from_config = prefer_config(x=from_position[0], y=from_position[1])
        to_config   = prefer_config(x=to_position[0],   y=to_position[1])
        
        if check_integrity_config(from_config, to_config)==1:
            r = np.abs(image[(y2,x2)] - image[(y1,x1)]).sum() * scale_factor
            # allow to go one or two two pixels horizontally at one step
            #dx = 1 if (dx==2 and dy==0) else dx
            
            #diff = max(dx, dy)
            #extra =  dx*0.414 if dx==dy else 0 # sqrt(2)-1 at ~extra cost to move a step at diagonal
            #diff = np.sqrt(dx+dy)
            diff = np.sqrt(dx+dy)
            return int((r+diff) * precision) #int((r+(diff-1+extra))*10000) 
        else:
            return 14 * precision
In [473]:
def quadrant(x,y):
    if x==0 and y==0:
        return 0
    if x>0 and y>=0:
        return 1
    elif x>=0 and y<0:
        return 2
    elif x<0 and y<=0:
        return 3
    elif y>0 and x<=0:
        return 4

def map_config_difff(point, radius, ax):
    x0,y0 = point #(5,64)
    if point==(0,0):
        return np.zeros(shape=(radius*2+1,radius*2+1))  #ignore center point
    
    q0 = quadrant(x0,y0)
    config_base = prefer_config(x=x0,y=y0)
    
    #radius = 4
    r = np.zeros(shape=(radius*2+1,radius*2+1))
    for x in range(-radius,radius+1):
        for y in range(-radius,radius+1):
            if abs(x0+x)<129 and abs(y0+y)<129:
                q1 = quadrant(x0+x,y0+y)
                if q0==q1:
                    r[radius-y,radius-x] = check_integrity_config(prefer_config(x0,y0), prefer_config(x0+x, y0+y))
    
    #f,ax=plt.subplots(figsize=(3,3))
    sns.heatmap(r, annot=True, cbar=False, ax=ax)
    ax.invert_xaxis() #ax.invert_yaxis()
    ax.axis("off")

def temp_cost_file(from_position, to_position, image):
    if from_position == to_position: return 0
    
    x1 = 128+from_position[0] ; y1 = 128-from_position[1]
    x2 = 128+to_position[0] ;   y2 = 128-to_position[1]
    
    dx = abs(x1-x2)
    dy = abs(y1-y2)
    
    diff = np.sqrt(dx+dy)
    return int((diff)*100)


r_n = np.zeros(shape=(9,9))
center_point = (5,64)

for x in range(-4,5):
    for y in range(-4,5):
        t_n  = temp_cost_file(center_point, (center_point[0]+x,center_point[1]+y), image)
        r_n[4+y,4+x] += t_n

f,ax=plt.subplots(figsize=(10,5), ncols=2)
ax[0].set_title("Neighbor pixel reconfiguration cost map")
ax[1].set_title("Steps required to reach neighboring pixels")
ax[0].axis("off")

sns.heatmap(r_n, annot=True, ax=ax[0], fmt=".0f", cbar=False)
map_config_difff(point=(5,64), radius=4, ax=ax[1])

f.suptitle("Point (5,64)")
Out[473]:
Text(0.5, 0.98, 'Point (5,64)')

As can be seen in the color map (left) for pixel (5.64) of the 1st quadrant, the reconfiguration cost can be estimated from the displacement of the vector; however, this pixel change must be achievable in a single step. As can be seen from the color map on the right, these pixels that can be achieved in a single pass are not necessarily symmetrical and can be a maximum distance of 3 pixels from the source pixel depending on the arm configuration. Then the function cost values for this TPS problem can be calculated explicitly considering:

  • If the pixel distance to change is greater than 3 then is not achivable in one step, then it not necessary to calculate specific cost.
  • vector displacament are absulute (same cost independtly of travel direction), then, the EDGE_WEIGHT_FORMAT parameter in Edge Weigth file (TSP file) can be set at Lower Row matrix format, such this:

image.png

In [496]:
# Functions to compute the cost function

# Functions to map between cartesian coordinates and array indexes
def cartesian_to_array(x, y, shape):
    m, n = shape[:2]
    i = (n - 1) // 2 - y
    j = (n - 1) // 2 + x
    if i < 0 or i >= m or j < 0 or j >= n:
        raise ValueError("Coordinates not within given dimensions.")
    return i, j

# Cost of reconfiguring the robotic arm: the square root of the number of links rotated
def reconfiguration_cost(from_config, to_config):
    nlinks = len(from_config)
    diffs = np.abs(np.asarray(from_config) - np.asarray(to_config)).sum(axis=1)
    return np.sqrt(diffs.sum())

# Cost of moving from one color to another: the sum of the absolute change in color components
def color_cost(from_position, to_position, image, color_scale=3.0):
    return np.abs(image[to_position] - image[from_position]).sum() * color_scale


# Total cost of one step: the reconfiguration cost plus the color cost
def step_cost(from_config, to_config, image):
    from_position = cartesian_to_array(*get_position(from_config), image.shape)
    to_position   = cartesian_to_array(*get_position(to_config), image.shape)
    return (
        reconfiguration_cost(from_config, to_config) +
        color_cost(from_position, to_position, image)
    )

# Compute total cost of path over image
def total_cost(path, image):
    return reduce(
        lambda cost, pair: cost + step_cost(pair[0], pair[1], image),
        zip(path[:-1], path[1:]),
        0,
    )


def get_position(config):
    return reduce(lambda p, q: (p[0] + q[0], p[1] + q[1]), config, (0, 0))
In [475]:
def read_tour(filename):
    tour = []
    for line in open(filename).readlines():
        line = line.replace('\n', '')
        try:
            tour.append(int(line) - 1)
        except ValueError as e:
            pass  # skip if not a city id (int)
    return tour[:-1]

Write the specific edge weight for each image quadrant (.tsp files)

In [254]:
from tqdm.auto import tqdm

def write_tsp(df, df_q_dict, filename, name='santa-2022_q', fixed_point=None):
    
    fixed_point = df.index[-1] if fixed_point is None else fixed_point
    
    with open(filename, 'w') as f:
        f.write('NAME : %s\n' % name)
        f.write('COMMENT : %s\n' % name)
        f.write('TYPE : TSP\n')   #TSP
        f.write('DIMENSION : %d\n' % (len(df)))
        f.write('EDGE_WEIGHT_TYPE : EXPLICIT\n') # EXPLICIT/SPECIAL
        f.write('EDGE_WEIGHT_FORMAT : LOWER_DIAG_ROW\n') # Full matrix working
        f.write('FIXED_EDGES_SECTION\n')
        f.write('%d %d\n' % (fixed_point+1, 1))    # fixed travel between start and end points 
        f.write('%d\n' % (-1))
        f.write('EDGE_WEIGHT_SECTION\n')
        for i in tqdm(range(len(df))):
            line = tuple([cost_file(df_q_dict[i], df_q_dict[j], image) for j in range(i+1)])
            base = '%d '*(i) + '%d\n'
            f.write(base % line)
        #f.write('NODE_COORD_TYPE : TWOD_COORDS\n')
        #f.write('NODE_COORD_SECTION\n')
        #for row in df.itertuples():
        #    f.write('%d %d %d\n' % (row.Index + 1, row.x, row.y))
        #print(row.Index + 1, row.x, row.y)
        f.write('EOF\n')


write_tsp(df_q1, df_q1_dict_rev,
          filename='/kaggle/working/LKH-3.0.8/Pixels_Q1_v1.tsp', 
          name='santa-2022_q1')

write_tsp(df_q2, df_q2_dict_rev,
          filename='/kaggle/working/LKH-3.0.8/Pixels_Q2_v1.tsp', 
          name='santa-2022_q2')

write_tsp(df_q3, df_q3_dict_rev,
          filename='/kaggle/working/LKH-3.0.8/Pixels_Q3_v1.tsp', 
          name='santa-2022_q3')

write_tsp(df_q4, df_q4_dict_rev,
          filename='/kaggle/working/LKH-3.0.8/Pixels_Q4_v1.tsp', 
          name='santa-2022_q4', fixed_point = 8191)

  0%|          | 0/16512 [00:00<?, ?it/s]
  0%|          | 0/16512 [00:00<?, ?it/s]
  0%|          | 0/16512 [00:00<?, ?it/s]
  0%|          | 0/16384 [00:00<?, ?it/s]
In [255]:
!head -n 16 /kaggle/working/LKH-3.0.8/Pixels_Q4_v1.tsp

NAME : santa-2022_q4
COMMENT : santa-2022_q4
TYPE : TSP
DIMENSION : 16384
EDGE_WEIGHT_TYPE : EXPLICIT
EDGE_WEIGHT_FORMAT : LOWER_DIAG_ROW
FIXED_EDGES_SECTION
8192 1
-1
EDGE_WEIGHT_SECTION
0
230 0
1400 108 0
1400 1400 101 0
1400 1400 1400 100 0
1400 1400 1400 1400 101 0
In [ ]:
# initial tour, do not mandatory

with open('/kaggle/working/LKH-3.0.8/initial_tour_Q1.tour', 'w') as f:
    f.write('NAME : initial_tour_Q1.tour\n')
    f.write('TYPE : TOUR\n')
    f.write('DIMENSION : %d\n'%(len(r_q1_tour)))
    f.write('TOUR_SECTION\n')
    for node in r_q1_tour:
        f.write('%d\n' % (node+1)) # node count start with 1 instead 0
    f.write('%d\n' % (-1))

It is necessary to define the adequate LKH parameters to solve the TSP problem, the general image path solved per quadrant can be fully connected again if certain fixed edges were defined.

A representative parameter is MOVE_TYPE, it is set to 5-opt moves in this case. Each Quadrant can be solve with this in ~ 30 min.

In [477]:
def write_parameters(parameters, filename='/kaggle/working/LKH-3.0.8/params_Q1.par'):
    with open(filename, 'w') as f:
        for param, value in parameters:
            f.write("{} = {}\n".format(param, value))
    print("Parameters saved as", filename)

    
def generate_params(df=df_q1, quarter_section="Q1"):
    parameters = [
        ("PROBLEM_FILE", f"Pixels_{quarter_section}_v1.tsp"),
        ("OUTPUT_TOUR_FILE", f"tsp_solution_{quarter_section}.csv"),
        #("INITIAL_TOUR_FILE", "tsp_initial_Q1_v1.csv"),
        ("SEED", 2023),
        ("MOVE_TYPE","5"), #5 # 8-opt move
        ("RUNS","1"),
        ("KICKS","6"),
        #("MAX_CANDIDATES", 8),
        ("DEPOT", df.shape[0]//2),
        ('INITIAL_TOUR_ALGORITHM', 'GREEDY'), # BORUVKA | GREEDY |  NEAREST-NEIGHBOR | QUICK-BORUVKA | SIERPINSKI | WALK
        ('PATCHING_C', 5),
        ('PATCHING_A', 1),
        ('RECOMBINATION', 'GPX2'),

        ('CANDIDATE_SET_TYPE', 'NEAREST-NEIGHBOR'), #, 'POPMUSIC' 'NEAREST-NEIGHBOR', 'ALPHA' | DELAUNAY [ PURE ] QUADRANT
        #('ASCENT_CANDIDATES', '100'),
        ('TIME_LIMIT', 10000), #3600*5), # LIMIT in seconds
        ('PRECISION',10),
        ('INITIAL_PERIOD', 10000),
        ('MAX_TRIALS', 1000),
        ('TRACE_LEVEL', 1)
    ]

    write_parameters(parameters, filename=f'/kaggle/working/LKH-3.0.8/params_{quarter_section}.par')

generate_params(df=df_q1, quarter_section="Q1")
generate_params(df=df_q2, quarter_section="Q2")
generate_params(df=df_q3, quarter_section="Q3")
generate_params(df=df_q4, quarter_section="Q4")

Parameters saved as /kaggle/working/LKH-3.0.8/params_Q1.par
Parameters saved as /kaggle/working/LKH-3.0.8/params_Q2.par
Parameters saved as /kaggle/working/LKH-3.0.8/params_Q3.par
Parameters saved as /kaggle/working/LKH-3.0.8/params_Q4.par
In [257]:
!cat /kaggle/working/LKH-3.0.8/params_Q4.par

PROBLEM_FILE = Pixels_Q4_v1.tsp
OUTPUT_TOUR_FILE = tsp_solution_Q4.csv
SEED = 2023
MOVE_TYPE = 5
RUNS = 1
KICKS = 6
DEPOT = 8192
INITIAL_TOUR_ALGORITHM = GREEDY
PATCHING_C = 5
PATCHING_A = 1
RECOMBINATION = GPX2
CANDIDATE_SET_TYPE = NEAREST-NEIGHBOR
TIME_LIMIT = 10000
PRECISION = 10
INITIAL_PERIOD = 10000
MAX_TRIALS = 1000
TRACE_LEVEL = 1
In [258]:
%%time
%%bash -e
cd ./LKH-3.0.8
./LKH params_Q1.par

PARAMETER_FILE = params_Q1.par
Reading PROBLEM_FILE: "Pixels_Q1_v1.tsp" ... done
ASCENT_CANDIDATES = 50
BACKBONE_TRIALS = 0
BACKTRACKING = NO
# BWTSP =
# CANDIDATE_FILE =
CANDIDATE_SET_TYPE = NEAREST-NEIGHBOR
# DISTANCE =
# DEPOT =
# EDGE_FILE =
EXCESS = 6.0562e-05
EXTERNAL_SALESMEN = 0
EXTRA_CANDIDATES = 0 
EXTRA_CANDIDATE_SET_TYPE = QUADRANT
GAIN23 = YES
GAIN_CRITERION = YES
INITIAL_PERIOD = 10000
INITIAL_STEP_SIZE = 1
INITIAL_TOUR_ALGORITHM = GREEDY
# INITIAL_TOUR_FILE = 
INITIAL_TOUR_FRACTION = 1.000
# INPUT_TOUR_FILE = 
KICK_TYPE = 0
KICKS = 6
# MAX_BREADTH =
MAKESPAN = NO
MAX_CANDIDATES = 5 
MAX_SWAPS = 16512
MAX_TRIALS = 1000
# MERGE_TOUR_FILE =
MOVE_TYPE = 5 
# MTSP_MIN_SIZE =
# MTSP_MAX_SIZE =
# MTSP_OBJECTIVE =
# MTSP_SOLUTION_FILE = 
# NONSEQUENTIAL_MOVE_TYPE = 10
# OPTIMUM =
OUTPUT_TOUR_FILE = tsp_solution_Q1.csv
PATCHING_A = 1 
PATCHING_C = 5 
# PI_FILE = 
POPMUSIC_INITIAL_TOUR = NO
POPMUSIC_MAX_NEIGHBORS = 5
POPMUSIC_SAMPLE_SIZE = 10
POPMUSIC_SOLUTIONS = 50
POPMUSIC_TRIALS = 1
# POPULATION_SIZE = 0
PRECISION = 10
PROBLEM_FILE = Pixels_Q1_v1.tsp
RECOMBINATION = GPX2
RESTRICTED_SEARCH = YES
RUNS = 1
SALESMEN = 1
SCALE = 1
SEED = 2023
STOP_AT_OPTIMUM = YES
SUBGRADIENT = YES
# SUBPROBLEM_SIZE =
# SUBPROBLEM_TOUR_FILE = 
SUBSEQUENT_MOVE_TYPE = 5 
SUBSEQUENT_PATCHING = YES
TIME_LIMIT = 10000.0
# TOTAL_TIME_LIMIT =
# TOUR_FILE = 
TRACE_LEVEL = 1
VEHICLES = 1

Cand.min = 5, Cand.avg = 5.0, Cand.max = 6
Edges.fixed = 1 [Cost = 14000]
Preprocessing time = 2.42 sec.
Greedy = 2579184, Time = 0.02 sec.
* 1: Cost = 1821804, Time = 12.55 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 6: Cost = 1821776, Time = 27.16 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 9: Cost = 1821764, Time = 33.31 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 10: Cost = 1821743, Time = 34.91 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 13: Cost = 1821736, Time = 41.42 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 19: Cost = 1821734, Time = 53.60 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 26: Cost = 1821720, Time = 69.20 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 29: Cost = 1821718, Time = 74.59 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 42: Cost = 1821716, Time = 98.12 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 45: Cost = 1821707, Time = 102.89 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 57: Cost = 1821705, Time = 126.12 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 58: Cost = 1821702, Time = 127.89 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 65: Cost = 1821700, Time = 142.81 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 97: Cost = 1821683, Time = 208.73 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 107: Cost = 1821681, Time = 232.67 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 159: Cost = 1821679, Time = 336.22 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 173: Cost = 1821677, Time = 361.92 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 181: Cost = 1821666, Time = 379.24 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 182: Cost = 1821664, Time = 381.26 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 240: Cost = 1821662, Time = 500.01 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 244: Cost = 1821660, Time = 509.65 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 247: Cost = 1821646, Time = 516.00 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 256: Cost = 1821644, Time = 537.29 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 260: Cost = 1821635, Time = 545.95 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 262: Cost = 1821632, Time = 549.71 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 266: Cost = 1821631, Time = 558.20 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 270: Cost = 1821630, Time = 564.39 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 273: Cost = 1821629, Time = 571.99 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 274: Cost = 1821628, Time = 573.72 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 276: Cost = 1821627, Time = 576.53 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 323: Cost = 1821611, Time = 675.04 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 335: Cost = 1821600, Time = 699.59 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 346: Cost = 1821599, Time = 722.18 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 363: Cost = 1821594, Time = 761.07 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 536: Cost = 1821577, Time = 1104.03 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 561: Cost = 1821575, Time = 1155.61 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 615: Cost = 1821561, Time = 1277.58 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 654: Cost = 1821555, Time = 1365.97 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 660: Cost = 1821539, Time = 1381.41 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 665: Cost = 1821525, Time = 1390.82 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 672: Cost = 1821523, Time = 1404.45 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 755: Cost = 1821518, Time = 1564.31 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 853: Cost = 1821515, Time = 1757.32 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 921: Cost = 1821502, Time = 1890.60 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 935: Cost = 1821500, Time = 1918.71 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 953: Cost = 1821498, Time = 1954.87 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
* 967: Cost = 1821494, Time = 1981.47 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q1.csv" ... done
Run 1: Cost = 1821494, Time = 2045.19 sec.

Successes/Runs = 0/1 
Cost.min = 1821494, Cost.avg = 1821494.00, Cost.max = 1821494
Gap.min = 0.0000%, Gap.avg = 0.0000%, Gap.max = 0.0000%
Trials.min = 1000, Trials.avg = 1000.0, Trials.max = 1000
Time.min = 2045.19 sec., Time.avg = 2045.19 sec., Time.max = 2045.19 sec.
Time.total = 2060.13 sec.

CPU times: user 384 ms, sys: 86.5 ms, total: 471 ms
Wall time: 34min 58s
In [259]:
%%time
%%bash -e
cd ./LKH-3.0.8
./LKH params_Q2.par

PARAMETER_FILE = params_Q2.par
Reading PROBLEM_FILE: "Pixels_Q2_v1.tsp" ... done
ASCENT_CANDIDATES = 50
BACKBONE_TRIALS = 0
BACKTRACKING = NO
# BWTSP =
# CANDIDATE_FILE =
CANDIDATE_SET_TYPE = NEAREST-NEIGHBOR
# DISTANCE =
# DEPOT =
# EDGE_FILE =
EXCESS = 6.0562e-05
EXTERNAL_SALESMEN = 0
EXTRA_CANDIDATES = 0 
EXTRA_CANDIDATE_SET_TYPE = QUADRANT
GAIN23 = YES
GAIN_CRITERION = YES
INITIAL_PERIOD = 10000
INITIAL_STEP_SIZE = 1
INITIAL_TOUR_ALGORITHM = GREEDY
# INITIAL_TOUR_FILE = 
INITIAL_TOUR_FRACTION = 1.000
# INPUT_TOUR_FILE = 
KICK_TYPE = 0
KICKS = 6
# MAX_BREADTH =
MAKESPAN = NO
MAX_CANDIDATES = 5 
MAX_SWAPS = 16512
MAX_TRIALS = 1000
# MERGE_TOUR_FILE =
MOVE_TYPE = 5 
# MTSP_MIN_SIZE =
# MTSP_MAX_SIZE =
# MTSP_OBJECTIVE =
# MTSP_SOLUTION_FILE = 
# NONSEQUENTIAL_MOVE_TYPE = 10
# OPTIMUM =
OUTPUT_TOUR_FILE = tsp_solution_Q2.csv
PATCHING_A = 1 
PATCHING_C = 5 
# PI_FILE = 
POPMUSIC_INITIAL_TOUR = NO
POPMUSIC_MAX_NEIGHBORS = 5
POPMUSIC_SAMPLE_SIZE = 10
POPMUSIC_SOLUTIONS = 50
POPMUSIC_TRIALS = 1
# POPULATION_SIZE = 0
PRECISION = 10
PROBLEM_FILE = Pixels_Q2_v1.tsp
RECOMBINATION = GPX2
RESTRICTED_SEARCH = YES
RUNS = 1
SALESMEN = 1
SCALE = 1
SEED = 2023
STOP_AT_OPTIMUM = YES
SUBGRADIENT = YES
# SUBPROBLEM_SIZE =
# SUBPROBLEM_TOUR_FILE = 
SUBSEQUENT_MOVE_TYPE = 5 
SUBSEQUENT_PATCHING = YES
TIME_LIMIT = 10000.0
# TOTAL_TIME_LIMIT =
# TOUR_FILE = 
TRACE_LEVEL = 1
VEHICLES = 1

Cand.min = 5, Cand.avg = 5.0, Cand.max = 6
Edges.fixed = 1 [Cost = 14000]
Preprocessing time = 3.28 sec.
Greedy = 2607941, Time = 0.02 sec.
* 1: Cost = 1876138, Time = 8.93 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q2.csv" ... done
* 2: Cost = 1876115, Time = 10.68 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q2.csv" ... done
* 3: Cost = 1876112, Time = 11.51 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q2.csv" ... done
* 5: Cost = 1876110, Time = 13.57 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q2.csv" ... done
* 8: Cost = 1876108, Time = 17.19 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q2.csv" ... done
* 15: Cost = 1876103, Time = 26.48 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q2.csv" ... done
* 22: Cost = 1876102, Time = 33.48 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q2.csv" ... done
* 31: Cost = 1876096, Time = 43.94 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q2.csv" ... done
* 35: Cost = 1876094, Time = 48.87 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q2.csv" ... done
* 45: Cost = 1876076, Time = 60.60 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q2.csv" ... done
* 48: Cost = 1876073, Time = 63.95 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q2.csv" ... done
* 49: Cost = 1876071, Time = 64.98 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q2.csv" ... done
* 51: Cost = 1876069, Time = 67.11 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q2.csv" ... done
* 53: Cost = 1876066, Time = 68.89 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q2.csv" ... done
* 54: Cost = 1876064, Time = 69.58 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q2.csv" ... done
* 56: Cost = 1876062, Time = 71.60 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q2.csv" ... done
* 66: Cost = 1876060, Time = 83.61 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q2.csv" ... done
* 75: Cost = 1876059, Time = 92.12 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q2.csv" ... done
* 77: Cost = 1876051, Time = 94.54 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q2.csv" ... done
* 98: Cost = 1876048, Time = 120.85 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q2.csv" ... done
* 108: Cost = 1876047, Time = 132.63 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q2.csv" ... done
* 138: Cost = 1876043, Time = 170.22 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q2.csv" ... done
* 154: Cost = 1876042, Time = 193.12 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q2.csv" ... done
* 185: Cost = 1876041, Time = 234.22 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q2.csv" ... done
* 223: Cost = 1876019, Time = 281.70 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q2.csv" ... done
* 226: Cost = 1876012, Time = 285.26 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q2.csv" ... done
* 230: Cost = 1876011, Time = 290.08 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q2.csv" ... done
* 234: Cost = 1876009, Time = 295.54 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q2.csv" ... done
* 242: Cost = 1876007, Time = 306.49 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q2.csv" ... done
* 243: Cost = 1876002, Time = 307.56 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q2.csv" ... done
* 254: Cost = 1875998, Time = 321.28 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q2.csv" ... done
* 256: Cost = 1875990, Time = 324.11 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q2.csv" ... done
* 283: Cost = 1875989, Time = 356.94 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q2.csv" ... done
* 326: Cost = 1875987, Time = 409.08 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q2.csv" ... done
* 343: Cost = 1875980, Time = 430.53 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q2.csv" ... done
* 423: Cost = 1875979, Time = 525.92 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q2.csv" ... done
* 424: Cost = 1875976, Time = 527.21 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q2.csv" ... done
* 426: Cost = 1875971, Time = 529.51 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q2.csv" ... done
Run 1: Cost = 1875971, Time = 1252.28 sec.

Successes/Runs = 0/1 
Cost.min = 1875971, Cost.avg = 1875971.00, Cost.max = 1875971
Gap.min = 0.0000%, Gap.avg = 0.0000%, Gap.max = 0.0000%
Trials.min = 1000, Trials.avg = 1000.0, Trials.max = 1000
Time.min = 1252.28 sec., Time.avg = 1252.28 sec., Time.max = 1252.28 sec.
Time.total = 1268.62 sec.

CPU times: user 320 ms, sys: 81.4 ms, total: 402 ms
Wall time: 21min 45s
In [260]:
%%time
%%bash -e
cd ./LKH-3.0.8
./LKH params_Q3.par

PARAMETER_FILE = params_Q3.par
Reading PROBLEM_FILE: "Pixels_Q3_v1.tsp" ... done
ASCENT_CANDIDATES = 50
BACKBONE_TRIALS = 0
BACKTRACKING = NO
# BWTSP =
# CANDIDATE_FILE =
CANDIDATE_SET_TYPE = NEAREST-NEIGHBOR
# DISTANCE =
# DEPOT =
# EDGE_FILE =
EXCESS = 6.0562e-05
EXTERNAL_SALESMEN = 0
EXTRA_CANDIDATES = 0 
EXTRA_CANDIDATE_SET_TYPE = QUADRANT
GAIN23 = YES
GAIN_CRITERION = YES
INITIAL_PERIOD = 10000
INITIAL_STEP_SIZE = 1
INITIAL_TOUR_ALGORITHM = GREEDY
# INITIAL_TOUR_FILE = 
INITIAL_TOUR_FRACTION = 1.000
# INPUT_TOUR_FILE = 
KICK_TYPE = 0
KICKS = 6
# MAX_BREADTH =
MAKESPAN = NO
MAX_CANDIDATES = 5 
MAX_SWAPS = 16512
MAX_TRIALS = 1000
# MERGE_TOUR_FILE =
MOVE_TYPE = 5 
# MTSP_MIN_SIZE =
# MTSP_MAX_SIZE =
# MTSP_OBJECTIVE =
# MTSP_SOLUTION_FILE = 
# NONSEQUENTIAL_MOVE_TYPE = 10
# OPTIMUM =
OUTPUT_TOUR_FILE = tsp_solution_Q3.csv
PATCHING_A = 1 
PATCHING_C = 5 
# PI_FILE = 
POPMUSIC_INITIAL_TOUR = NO
POPMUSIC_MAX_NEIGHBORS = 5
POPMUSIC_SAMPLE_SIZE = 10
POPMUSIC_SOLUTIONS = 50
POPMUSIC_TRIALS = 1
# POPULATION_SIZE = 0
PRECISION = 10
PROBLEM_FILE = Pixels_Q3_v1.tsp
RECOMBINATION = GPX2
RESTRICTED_SEARCH = YES
RUNS = 1
SALESMEN = 1
SCALE = 1
SEED = 2023
STOP_AT_OPTIMUM = YES
SUBGRADIENT = YES
# SUBPROBLEM_SIZE =
# SUBPROBLEM_TOUR_FILE = 
SUBSEQUENT_MOVE_TYPE = 5 
SUBSEQUENT_PATCHING = YES
TIME_LIMIT = 10000.0
# TOTAL_TIME_LIMIT =
# TOUR_FILE = 
TRACE_LEVEL = 1
VEHICLES = 1

Cand.min = 5, Cand.avg = 5.0, Cand.max = 6
Edges.fixed = 1 [Cost = 14000]
Preprocessing time = 3.31 sec.
Greedy = 2634677, Time = 0.02 sec.
* 1: Cost = 1865117, Time = 8.21 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 2: Cost = 1864062, Time = 10.41 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 3: Cost = 1864060, Time = 12.29 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 4: Cost = 1864056, Time = 13.98 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 7: Cost = 1864051, Time = 20.48 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 9: Cost = 1864036, Time = 22.34 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 11: Cost = 1864031, Time = 25.55 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 12: Cost = 1864016, Time = 26.37 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 14: Cost = 1864012, Time = 29.27 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 18: Cost = 1864009, Time = 33.62 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 20: Cost = 1864006, Time = 36.22 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 21: Cost = 1864000, Time = 37.92 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 24: Cost = 1863995, Time = 42.60 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 26: Cost = 1863993, Time = 46.53 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 28: Cost = 1863988, Time = 50.03 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 32: Cost = 1863959, Time = 57.11 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 33: Cost = 1863924, Time = 58.34 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 36: Cost = 1863920, Time = 63.38 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 37: Cost = 1863898, Time = 64.95 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 38: Cost = 1863896, Time = 66.19 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 39: Cost = 1863886, Time = 67.71 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 40: Cost = 1863882, Time = 68.46 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 43: Cost = 1863879, Time = 72.01 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 44: Cost = 1863878, Time = 74.02 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 45: Cost = 1863875, Time = 74.85 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 58: Cost = 1863873, Time = 90.29 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 65: Cost = 1863869, Time = 98.53 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 67: Cost = 1863867, Time = 101.30 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 69: Cost = 1863843, Time = 103.87 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 72: Cost = 1863840, Time = 107.02 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 73: Cost = 1863838, Time = 109.09 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 75: Cost = 1863836, Time = 111.47 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 78: Cost = 1863834, Time = 115.41 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 89: Cost = 1863833, Time = 129.26 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 104: Cost = 1863831, Time = 149.17 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 120: Cost = 1863816, Time = 168.74 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 149: Cost = 1863814, Time = 205.66 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 157: Cost = 1863811, Time = 215.61 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 160: Cost = 1863807, Time = 218.80 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 166: Cost = 1863805, Time = 226.12 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 176: Cost = 1863804, Time = 237.39 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 177: Cost = 1863801, Time = 238.25 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 185: Cost = 1863797, Time = 248.78 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 206: Cost = 1863796, Time = 273.29 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 225: Cost = 1863790, Time = 297.57 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 319: Cost = 1863779, Time = 413.43 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 329: Cost = 1863774, Time = 425.19 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 671: Cost = 1863773, Time = 844.75 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 835: Cost = 1863772, Time = 1053.13 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 845: Cost = 1863771, Time = 1067.30 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 846: Cost = 1863770, Time = 1068.41 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
* 862: Cost = 1863769, Time = 1088.39 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q3.csv" ... done
Run 1: Cost = 1863769, Time = 1251.46 sec.

Successes/Runs = 0/1 
Cost.min = 1863769, Cost.avg = 1863769.00, Cost.max = 1863769
Gap.min = 0.0000%, Gap.avg = 0.0000%, Gap.max = 0.0000%
Trials.min = 1000, Trials.avg = 1000.0, Trials.max = 1000
Time.min = 1251.46 sec., Time.avg = 1251.46 sec., Time.max = 1251.46 sec.
Time.total = 1267.04 sec.

CPU times: user 326 ms, sys: 53.8 ms, total: 380 ms
Wall time: 21min 41s
In [261]:
%%time
%%bash -e
cd ./LKH-3.0.8
./LKH params_Q4.par

PARAMETER_FILE = params_Q4.par
Reading PROBLEM_FILE: "Pixels_Q4_v1.tsp" ... done
ASCENT_CANDIDATES = 50
BACKBONE_TRIALS = 0
BACKTRACKING = NO
# BWTSP =
# CANDIDATE_FILE =
CANDIDATE_SET_TYPE = NEAREST-NEIGHBOR
# DISTANCE =
# DEPOT =
# EDGE_FILE =
EXCESS = 6.10352e-05
EXTERNAL_SALESMEN = 0
EXTRA_CANDIDATES = 0 
EXTRA_CANDIDATE_SET_TYPE = QUADRANT
GAIN23 = YES
GAIN_CRITERION = YES
INITIAL_PERIOD = 10000
INITIAL_STEP_SIZE = 1
INITIAL_TOUR_ALGORITHM = GREEDY
# INITIAL_TOUR_FILE = 
INITIAL_TOUR_FRACTION = 1.000
# INPUT_TOUR_FILE = 
KICK_TYPE = 0
KICKS = 6
# MAX_BREADTH =
MAKESPAN = NO
MAX_CANDIDATES = 5 
MAX_SWAPS = 16384
MAX_TRIALS = 1000
# MERGE_TOUR_FILE =
MOVE_TYPE = 5 
# MTSP_MIN_SIZE =
# MTSP_MAX_SIZE =
# MTSP_OBJECTIVE =
# MTSP_SOLUTION_FILE = 
# NONSEQUENTIAL_MOVE_TYPE = 10
# OPTIMUM =
OUTPUT_TOUR_FILE = tsp_solution_Q4.csv
PATCHING_A = 1 
PATCHING_C = 5 
# PI_FILE = 
POPMUSIC_INITIAL_TOUR = NO
POPMUSIC_MAX_NEIGHBORS = 5
POPMUSIC_SAMPLE_SIZE = 10
POPMUSIC_SOLUTIONS = 50
POPMUSIC_TRIALS = 1
# POPULATION_SIZE = 0
PRECISION = 10
PROBLEM_FILE = Pixels_Q4_v1.tsp
RECOMBINATION = GPX2
RESTRICTED_SEARCH = YES
RUNS = 1
SALESMEN = 1
SCALE = 1
SEED = 2023
STOP_AT_OPTIMUM = YES
SUBGRADIENT = YES
# SUBPROBLEM_SIZE =
# SUBPROBLEM_TOUR_FILE = 
SUBSEQUENT_MOVE_TYPE = 5 
SUBSEQUENT_PATCHING = YES
TIME_LIMIT = 10000.0
# TOTAL_TIME_LIMIT =
# TOUR_FILE = 
TRACE_LEVEL = 1
VEHICLES = 1

Cand.min = 5, Cand.avg = 5.0, Cand.max = 6
Edges.fixed = 1 [Cost = 14000]
Preprocessing time = 2.97 sec.
Greedy = 2626214, Time = 0.02 sec.
* 1: Cost = 1845233, Time = 9.08 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q4.csv" ... done
* 2: Cost = 1844025, Time = 11.55 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q4.csv" ... done
* 3: Cost = 1844018, Time = 13.21 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q4.csv" ... done
* 5: Cost = 1844011, Time = 16.53 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q4.csv" ... done
* 6: Cost = 1844003, Time = 17.77 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q4.csv" ... done
* 12: Cost = 1844001, Time = 28.04 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q4.csv" ... done
* 16: Cost = 1843973, Time = 34.89 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q4.csv" ... done
* 18: Cost = 1843931, Time = 38.18 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q4.csv" ... done
* 34: Cost = 1843927, Time = 66.11 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q4.csv" ... done
* 35: Cost = 1843923, Time = 68.01 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q4.csv" ... done
* 40: Cost = 1843921, Time = 75.62 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q4.csv" ... done
* 65: Cost = 1843895, Time = 119.13 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q4.csv" ... done
* 66: Cost = 1843871, Time = 121.02 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q4.csv" ... done
* 68: Cost = 1843861, Time = 123.56 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q4.csv" ... done
* 71: Cost = 1843853, Time = 130.16 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q4.csv" ... done
* 72: Cost = 1843850, Time = 131.88 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q4.csv" ... done
* 87: Cost = 1843844, Time = 156.30 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q4.csv" ... done
* 91: Cost = 1843842, Time = 163.64 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q4.csv" ... done
* 104: Cost = 1843841, Time = 183.68 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q4.csv" ... done
* 122: Cost = 1843837, Time = 211.38 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q4.csv" ... done
* 240: Cost = 1843832, Time = 405.41 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q4.csv" ... done
* 241: Cost = 1843806, Time = 406.99 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q4.csv" ... done
* 657: Cost = 1843804, Time = 1074.55 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q4.csv" ... done
* 692: Cost = 1843798, Time = 1131.03 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q4.csv" ... done
* 707: Cost = 1843796, Time = 1154.97 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q4.csv" ... done
* 716: Cost = 1843783, Time = 1170.12 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q4.csv" ... done
* 752: Cost = 1843781, Time = 1229.59 sec.
Writing OUTPUT_TOUR_FILE: "tsp_solution_Q4.csv" ... done
Run 1: Cost = 1843781, Time = 1633.79 sec.

Successes/Runs = 0/1 
Cost.min = 1843781, Cost.avg = 1843781.00, Cost.max = 1843781
Gap.min = 0.0000%, Gap.avg = 0.0000%, Gap.max = 0.0000%
Trials.min = 1000, Trials.avg = 1000.0, Trials.max = 1000
Time.min = 1633.79 sec., Time.avg = 1633.79 sec., Time.max = 1633.79 sec.
Time.total = 1648.94 sec.

CPU times: user 314 ms, sys: 47.9 ms, total: 362 ms
Wall time: 28min 7s
In [491]:
# auxiliar function to read tsp huristic solution
def gen_tour(df=df_q1, tour_file='../working/LKH-3.0.8/tsp_solution_Q1.csv', order=-1, extra=-1, name='Q1'):
    tour = read_tour(tour_file)
    tour = np.roll(tour, -tour.index(0)+extra)[::order]
    #tour = list(np.roll(tour, len(tour)-tour.index(df_q1.shape[0]-1)-1))#[::-1]
    t_points = [tuple(el) for el in df.loc[tour][['x','y']].to_numpy()]
    
    #tour[-1], tour[0]
    print(f"Tour length {name} {len(tour)} ", end='')
    print(f"Init / Final: {t_points[0]}, {t_points[-1]}")
    return t_points
In [492]:
t_points_q1 = gen_tour(df=df_q1, tour_file='../working/LKH-3.0.8/tsp_solution_Q1.csv', name='Q1')
t_points_q2 = gen_tour(df=df_q2, tour_file='../working/LKH-3.0.8/tsp_solution_Q2.csv', name='Q2')
t_points_q3 = gen_tour(df=df_q3, tour_file='../working/LKH-3.0.8/tsp_solution_Q3.csv',order=-1, extra=-1, name='Q3')
t_points_q4 = gen_tour(df=df_q4, tour_file='../working/LKH-3.0.8/tsp_solution_Q4.csv', order=1, extra=0, name='Q4')

Tour length Q1 16512 Init / Final: (1, 128), (128, 0)
Tour length Q2 16512 Init / Final: (128, -1), (0, -128)
Tour length Q3 16512 Init / Final: (-1, -128), (-128, 0)
Tour length Q4 16384 Init / Final: (-128, 1), (-1, 64)
In [498]:
#### search config provided functions

def rotate(config, i, direction):
    config = config.copy()
    config[i] = rotate_link(config[i], direction)
    return config

def get_direction(u, v):
    """Returns the sign of the angle from u to v."""
    direction = np.sign(np.cross(u, v))
    if direction == 0 and np.dot(u, v) < 0:
        direction = 1
    return direction

def rotate_link(vector, direction):
    x, y = vector
    if direction == 1:  # counter-clockwise
        if y >= x and y > -x:
            x -= 1
        elif y > x and y <= -x:
            y -= 1
        elif y <= x and y < -x:
            x += 1
        else:
            y += 1
    elif direction == -1:  # clockwise
        if y > x and y >= -x:
            x += 1
        elif y >= x and y < -x:
            y += 1
        elif y < x and y <= -x:
            x -= 1
        else:
            y -= 1
    return (x, y)

# compress a path between two points
def compress_path(path):
    r = [[] for _ in range(8)]
    for p in path:
        for i in range(8):
            if len(r[i]) == 0 or r[i][-1] != p[i]:
                r[i].append(p[i])
    mx = max([len(x) for x in r])
    
    for rr in r:
        while len(rr) < mx:
            rr.append(rr[-1])
    r = list(zip(*r))
    for i in range(len(r)):
        r[i] = list(r[i])
    return r


def get_path_to_point(config, point):
    """Find a path of configurations to `point` starting at `config`."""
    path = [config]
    # Rotate each link, starting with the largest, until the point can
    # be reached by the remaining links. The last link must reach the
    # point itself.
    for i in range(len(config)):
        link = config[i]
        base = get_position(config[:i])
        relbase = (point[0] - base[0], point[1] - base[1])
        position = get_position(config[:i+1])
        relpos = (point[0] - position[0], point[1] - position[1])
        radius = reduce(lambda r, link: r + max(abs(link[0]), abs(link[1])), config[i+1:], 0)
        # Special case when next-to-last link lands on point. 
        if radius == 1 and relpos == (0, 0):
            config = rotate(config, i, 1)
            if get_position(config) == point:
                path.append(config)
                break
            else:
                continue
        while np.max(np.abs(relpos)) > radius:
            direction = get_direction(link, relbase)
            config = rotate(config, i, direction)
            path.append(config)
            link = config[i]
            base = get_position(config[:i])
            relbase = (point[0] - base[0], point[1] - base[1])
            position = get_position(config[:i+1])
            relpos = (point[0] - position[0], point[1] - position[1])
            radius = reduce(lambda r, link: r + max(abs(link[0]), abs(link[1])), config[i+1:], 0)
    assert get_position(path[-1]) == point
    path_n = compress_path(path)
    return path_n

def get_path_to_configuration(from_config, to_config):
    path = [from_config]
    config = from_config.copy()
    while config != to_config:
        for i in range(len(config)):
            config = rotate(config, i, get_direction(config[i], to_config[i]))
        path.append(config)
    assert path[-1] == to_config
    return path
In [499]:
# search for config given the path of points
def gen_point_config(x,y, pre_config=''):
    
    origin = [(64, 0), (-32, 0), (-16, 0), (-8, 0), (-4, 0), (-2, 0), (-1, 0), (-1, 0)]
    #path   = [origin]
    
    if x==0 and y==0:
        return origin
    
    elif x==0 and y>0:
        #for i in range(1,y+1):
        t_path = get_path_to_point(pre_config, (0,y))
        #path.extend(t_path[-1:])
        return t_path[1:]
    else:
        return prefer_config(x,y)
In [500]:
# soluion per quadrant connected
tsp_path = t_points_q1+t_points_q2+t_points_q3+t_points_q4

# init configurations to avoid overlapping as much as possible
t_config  = [(64, 0), (-32, 32), (-16, 16), (-8, 8), (-4, 4), (-2, 2), (-1, 1), (-1, 1)] # (0,64)
init_path = get_path_to_configuration(gen_point_config(0,0), t_config)

#### define path by points
path = [(0,i) for i in range(65,129)]
total_path = path + tsp_path

#################################### retrive configurations according established constrains
total_path_config = [init_path[-1]]
for (t_x,t_y) in tqdm(total_path):
    t_config = gen_point_config(t_x,t_y, total_path_config[-1])
    
    if t_x==0 and t_y>0:
        total_path_config += t_config
    else:
        total_path_config.append(t_config)
####################################

total_path_config = init_path + total_path_config[1:]

## return to origin
return_to_origin = get_path_to_configuration(total_path_config[-1], gen_point_config(0,0))[1:]
total_path_config  +=  return_to_origin

  0%|          | 0/65984 [00:00<?, ?it/s]

Validate path configuration

In [501]:
def check_integrity_config(config1, config2):
    t1 = np.array(config1)
    t2 = np.array(config2)
    return np.max(np.abs(t1 - t2), axis=1).max()

if max([check_integrity_config(config1, config2) for config1, config2 in zip(total_path_config[:-1], total_path_config[1:])]) == 1:
    print("The path is valid.")

The path is valid.

Final Optimized Path

¶

In [506]:
r_points = [get_position(el) for el in total_path_config]
n_points = [get_position(el) for el in return_to_origin]

x,y = list(zip(*r_points))
x_n,y_n = list(zip(*n_points))

gray = np.mean(image, -1)
f,ax=plt.subplots(figsize=(10,10))

ax.plot(x,y, lw=1, color="navy", label="optimized path")
ax.plot(x_n,y_n, lw=1, color="darkred", label="overlapping path")
#ax.plot(x[:7000], y[:7000], lw=1, color="darkred")
ax.legend()

ax.set_title(f" Heuristic Solution Final Cost: {total_cost(path=total_path_config, image=image):.2f}")
ax.imshow(gray, extent=[-128.5,128.5,-128.5,128.5], cmap='gray')
ax.axis("off")

print(f"Extra steps {len(total_path_config)- 257*257}")

Extra steps 33

Final Considerations¶

  • The heuristic solution found can be further optimized by reviewing the paths of the connectors between quadrants and the overlap path nnecessary to return to the initial configuration of the arm.
  • A general problem instead of image quadrant subproblems may be more efficent.
  • The LKH algorithm can be effectively used to solve any TPS problem with proper parameters.