Modular Forms in Combinatorial Optimization
Varsha Gupta







theoremTheorem





















© 2023 by the author.










Purdue University, West Lafayette, Indiana, United States

conditions*
  
>l<@= >X
1emptyModular Forms in Combinatorial Optimization
    mailto:vvarsha@purdue.eduvvarsha@purdue.edu
    
===============================================


Combinatorial optimization problems, such as the Asymmetric Traveling Salesman Problem (ATSP), find applications across various domains including logistics, genome sequencing, and robotics. Despite their extensive applications, there have not been significant advancements in deriving optimal solutions for these problems. The lack of theoretical understanding owing to the complex structure of these problems has hindered the development of sophisticated algorithms. This paper proposes an unconventional approach by translating the ATSP into the complex domain, revealing an intrinsic modular nature of the problem. Furthermore, we have exploited modularity conditions to gain deeper insights into both unconstrained and constrained optimal solutions. The theoretical framework laid out in this paper can lead to important results at the intersection of combinatorial optimization and number theory.
Keywords:Traveling Salesman Problem, Modular Form, Combinatorial Optimization, Analytical SolutionModular Forms in Combinatorial Optimization
    mailto:vvarsha@purdue.eduvvarsha@purdue.edu
    
===============================================





§ INTRODUCTION

Solving combinatorial optimization problems such as the Asymmetric Travelling Salesman Problem (ATSP) has been an active area of research in optimization. The problem involves finding the optimal route for a salesman who is traveling across various cities, visiting every city only once and finally coming back to the initial point. The asymmetry in ATSP is due to the different costs of to and fro journeys between two points, making it resemble more to real-world scenarios.
In 1962,  Bellman <cit.> showed that the problem could be formulated using dynamic programming and solved computationally for up to 17 cities. While for larger cities, simple manipulations could lead to approximations. Later, Gavish et. al. <cit.> introduced a new formulation for the TSP using tour assignment and flow variables, showing a dual relationship with Miller et al.'s <cit.> formulation. It extends to include various transportation scheduling problems, with preliminary results suggesting tight bounds achievable through Lagrangean relaxation and subgradient optimization. 
 Larranaga et. al <cit.> discussed various representations and operators in genetic algorithms for solving the Traveling Salesman Problem. The paper analyzes binary, path, adjacency, ordinal, and matrix representations, each with its strengths and limitations. 

Halim et al. <cit.> compared the performance of six meta-heuristic algorithms – Nearest Neighbor (NN), Genetic Algorithm (GA), Simulated Annealing (SA), Tabu Search (TS), Ant Colony Optimization (ACO), and Tree Physiology Optimization (TPO). The comparison was made based on computation time, statistical accuracy, and convergence dynamics.

Recently, Stodola et. al. <cit.> presented an improved Ant Colony Optimization algorithm for the Travelling Salesman Problem, featuring node clustering, adaptive pheromone evaporation, and diverse termination conditions, outperforming several state-of-the-art methods in tests with TSPLIB benchmarks. Another similar work was reported <cit.> where a partial optimization metaheuristic under special intensification conditions was used to improve the algorithmic complexity. A similar study was published by Gong et.al. <cit.> who used a hybrid algorithm based on a state-adaptive slime mold model with a fractional-order ant system. 

Despite all the work, the structure of the problem remains mostly unexplained. Given the combinatorial nature of the problem, developing an efficient algorithm that can guarantee the quality of the solution requires deeper insights into the hidden mathematical form of the problem <cit.>. Revealing these forms can lead to a significant breakthrough in the field <cit.>. 

In this work, we introduce a theoretical framework for studying the hidden mathematical form in ATSP. By translating the problem into a complex domain, we unveil and study the modular form in the problem structure. The modularity condition specifically inversion invariance is utilized to study the solutions to unconstrained and constrained problems. The aim is to gain a theoretical understanding of the structure of the problem and thereby, inform the development of future algorithms for finding optimal solutions.



§ FORMULATION
Asymmetric Traveling Salesman Problem

Let r_a,b be the cost of the arc (a,b) ∈A and the binary decision variable, x_a,b is defined as follows:

    ∀ (a, b) ∈A,    x_ab = 
     
    1    if (a, b) is in the cycle;
    
    0    otherwise.


The standard formulation for the Asymmetric Travelling Salesman Problem (ATSP)  can be written <cit.> as follows:

    minimize∑_(a, b) ∈A   r_a,b· x_a,b
       subject to
       ∑_b=1, b≠ a^n x_ab = 1,    a = 1, 2, …, n 
       ∑_a=1, a≠ b^n x_ab = 1,    b = 1, 2, …, n 
       ∑_(a,b) ∈ S  x_ab≤ |S| - 1,   for all  S ⊂{1, 2, …, n}, with  2 ≤ |S| ≤ n-1 
        x_a,b∈{0,1}  ∀  (a, b) ∈A


Let's assume r is the global optimal solution to the above problem. We can define the following:

    r_a,b/r = e^j ϕ_a,b
    
    where    j  = √(-1)

Let's write the binary decision variable as follows:

    x_a,b = e^j θ_a,b + e^-j θ_a,b/2

    θ_ab = 
     
    2k π   if (a, b) is in the cycle;
    2k-1/2π   otherwise.  ∀ k ∈I


Now let's translate the problem using the above-defined variables in the complex plane as follows:



    ∑_(a, b) ∈Ar [e^j (ϕ_a,b+θ_a,b)+ e^j (ϕ_a,b-θ_a,b)] = r e^2k π j
       ∑_b=1, b≠ a^nre^j θ_a,b + e^-j θ_a,b/2 = r e^2k π j,    a = 1, 2, …, n 
       ∑_a=1, a≠ b^nre^j θ_a,b + e^-j θ_a,b/2 = r e^2k π j,    b = 1, 2, …, n 
       ∑_(a,b) ∈ Sre^j θ_a,b + e^-j θ_a,b/2≤r n e^2k β j,   where β = 2m π-j ln|S|-1/n/2k  ∀ m ∈ I
∀ S ⊂ A, with  2 ≤ |S| ≤ n-1


The last three equations in the system (<ref>) determine the feasible set of θ_a,b values. The first equation (<ref>) encodes the information for finding the equilibrium between θ_a,b and ϕ_a,b for which the optimal values of the problem are reached.
Let 

    s_a,b = ϕ_a,b+θ_a,b/2π
    τ_a,b = ϕ_a,b - θ_a,b/2π


Using the above definitions, we can rewrite the equation (<ref>) as:

    ∑_(a, b) ∈Ar e^2 π s_a,b j + ∑_(a, b) ∈Ar e^2 πτ_a,bj  = r e^2k π j


We know that r_a,b/r>0 and therefore, both s_a,b and τ_a,b lie in the upper half of the complex plane, denoted by ℍ and defined as follows:

    ℍ = {z ∈ℂ : Im(z) > 0}

The transformed problem in the complex plane is valid for any real value of r. Let's assume r = 1 such that we |z| = |re^2 πω j|=1.
The holomorphic map can be defined from the upper half plane, ℍ to the punctured unit disc:

    ℍ↦𝔻^* = {z ∈ℂ : 0<Im(z) <1}

Let's define 

    f(ω) = e^2 πω j

Since the translation invariance is satisfied for f(ω)
    f(ω) =f(ω +1 )

Let's assume the inversion invariance for f(ω) for all admissible values of ω
    f(-1/ω) = ω^m f(ω)

Therefore, f can be written in terms of f, a meromorphic function on the punctured unit disc, 𝔻^* as follows:

    f(ω) =f(q_ω)


Using the q-expansion of each of the terms below:

    ∑_(a, b) ∈ A( ∑_n=0^∞(2 π s_a,b j)^n/[n]_q_ω!) + ∑_(a, b) ∈ A(∑_n=0^∞(2 πτ_a,b j)^n/[n]_q_ω!) = e^2k π j

where [n]_q! is the q-analog of n factorial and is defined as:

    [n]_q_ω! = n! ∏_i=1^n-1 (1 - q_ω^i)


As q_ω→ 1, we can rewrite the q analog as follows:

    [n]_q_ω! = n!


Collecting the common term and simplifying it, we get the following expression:

    ∑_(a, b) ∈ A∑_n=0^∞(2 π j)^n/n! (s_a,b^n + τ_a,b^n) = 1

We can simplify to the following:

    ∑_(a, b) ∈ A∑_n=1^∞(2 π j)^n/n! (s_a,b^n + τ_a,b^n) = 0

This equilibrium condition implies that for the optimal solution, the infinite series in equation (<ref>) must converge to zero. Please note that one could have arrived at the equilibrium condition in equation (<ref>) using the Taylor series expansion of exponential terms in equation (<ref>). Therefore, the equation is valid irrespective of the validity of the invariant inversion transformation assumption in equation (<ref>). This reinforces the encoding of equilibrium condition (<ref>) in the structure of the problem.

There is an infinite series, E_a,b corresponding to every feasible arc, (a,b) ∈ A. For the unconstrained optimal solution, the arcs are chosen such that the sum of the E-series for all the arcs adds up to zero.


    ∑_(a, b) ∈ A E_a,b = 0

where

    E_a,b =  ∑_h=1^∞(2 π j)^h/h! (s_a,b^h + τ_a,b^h)






Given the equation <ref>, the function f remains invariant under inversion transformation.

Let's assume that f(-1/ ω) ≠ f(ω). 

Under this assumption, both f(τ) and f(s) would be variant under the inversion transformation ω↦ -1/ω. If f(τ) and f(s) are variants under inversion, then the LHS of equation <ref>, which is a sum of terms involving these functions, would also be variant under inversion.

But the RHS of the equation, which is 1 (or more generally, r e^2k π j), is invariant under inversion transformation. This invariance means that the RHS does not change under the transformation ω↦ -1/ω. Since the LHS is variant under inversion (as per the assumption) but the RHS is invariant, this creates a contradiction if the equation is supposed to hold under all modular transformations, including inversion. 

 Therefore, under the premise that the equation must hold under modular transformations, and given that the RHS is invariant, the initial assumption that f(-1/ ω) ≠ f(ω) must be false. Hence, f(-1/ ω) = f(ω) must hold true.


§ UNCONSTRAINED OPTIMAL SOLUTION

Under invariance condition, we know that

    τ_a,b^2 = -1
       s_a,b^2 = -1

In terms of a and b, we can write:


    ϕ_a,b+θ_a,b = ± 2 π i
       ϕ_a,b-θ_a,b = ± 2 π i

solving the above equations, we get:


    (ϕ_a,b)    = ± 2 π i
    (ϕ_a,b)    = 
     
    2m π   if (ϕ_a,b) = ± 2 π i, θ_a,b = 2k π and (a, b) is in the cycle;
    
    2m π,    if (ϕ_a,b) ≠± 2 π i, θ_a,b = 2k-1/2 and 4m-2k-1/2∈ I
      ∀ m ∈ I


The inclusion of an arc in the unconstrained optimal path is governed by the phase angle, ϕ_a,b which relates the cost of individual arcs to the optimal cost of the trip. If the (ϕ_a,b) takes a value of ± 2 π i, the arc is included in the unconstrained optimal trip, otherwise not. 



§ FEASIBLE SPACE

The feasible space informs the optimal solution in constrained optimization by changing the phase angle, ϕ_a,b by θ_a,b. The Fourier coefficients in the q-expansion of the series obtained in the objective function are governed by the θ_a,b value. 

Let's analyze the admissible values of θ_a,b in the feasible space. Using Taylor series expansion, we can rewrite the constraints (<ref>) and (<ref>) as following:

    ∑_b=1, b≠ a^n G_a,b =0,    a = 1, 2, …, n 
       ∑_a=1, a≠ b^n G_a,b = 0,    b = 1, 2, …, n ,   where   G_a,b =∑_h=1^∞(-1)^h (θ_a,b)^2h/(2h)!

For each arc, the above two equations must be satisfied, i.e. the infinite series G_a,b must converge to zero. 

The subroutine constraints can be rewritten as follows:

    ∑_(a,b) ∈ Se^2πψ_a,b j  + e^-2πξ_a,b j /2≤ n, ∀ S ,   where  ψ_a,b = (θ_a,b-2k β)/2π,   ξ_a,b = (θ_a,b+2k β)/2π

The LHS of the equation (<ref>) is invariant under translation. By introducing a slack variable on the left-hand side to convert the inequality into equality, and using the same reasoning as applied to the transformed objective function, it can be demonstrated that this equation also maintains invariance under the inversion transformation.

We can write the corresponding infinite series for each arc in S as follows:

    ∑_(a, b) ∈ S L_a,b≤ 0

where

    L_a,b =  ∑_n=0^∞(2 π j)^n/n! (ψ_a,b^n + ξ_a,b^n)

The infinite series, L_a,b, therefore, must converge to at most n for all the arcs in S.
 
Under invariance condition, we know that

    ψ_a,b^2 = -1
       ξ_a,b^2 = -1

In terms of θ_a,b and β, we can write:


    θ_a,b-2k β = ± 2 π i
       θ_a,b+2k β = ± 2 π i

solving the above equations, we get:


    θ_a,b   = 
     
    2m π   if (±2k β± 2 π i) = 0, (a, b) is in the cycle;
    2m-1/2,    if (±2k β± 2 π i) ≠ 0, (a, b) is Not in the cycle  ∀ m ∈ I


The inclusion of an arc in the constrained optimal path is governed by the phase angle, β.



§ CONCLUSION

To conclude, this work presents a theoretical framework for studying the structure of combinatorial optimization problems such as the Asymmetric Traveling Salesman Problem (ATSP). By redefining cost and decision variables in terms of complex exponentials, we prove the inherent modular structure of the problem. By utilizing the properties of the modular forms, particularly under inversion invariance, we study the optimal solutions of the constrained and unconstrained problems. The equilibrium conditions derived for both constrained and unconstrained scenarios offer a deeper insight into optimal solution paths and the exploration of the feasible space under this framework. This approach provides a solid foundation for understanding the ATSP and will inform the development of more sophisticated algorithms in the future.



§ DATA AVAILABILITY AND CONFLICT OF INTEREST STATEMENT 

There is no data associated with the manuscript and no conflict of statement.
unsrt