A Deterministic Annealing Neural Network Algorithm for the Minimum Concave Cost Transportation Problem

Area of Science:

• Operations Research
• Artificial Intelligence
• Computational Neuroscience

Background:

• The minimum concave cost transportation problem presents significant optimization challenges.
• Existing methods may struggle to guarantee global optimality for this NP-hard problem.

Purpose of the Study:

• To introduce a deterministic annealing neural network algorithm for solving the minimum concave cost transportation problem.
• To ensure the algorithm converges to global or near-global optimal solutions.

Main Methods:

• The algorithm integrates two neural network models with Lagrange-barrier functions.
• Lagrange functions manage linear equality constraints, while barrier functions guide towards optimal solutions.
• Two descent directions and Lyapunov functions are utilized to prove model stability and convergence.

Main Results:

• The proposed neural network models demonstrate complete stability and converge to a stable equilibrium state.
• Computer simulations confirm the algorithm's consistent generation of global or near-global optimal solutions across various test problems.

Conclusions:

• The deterministic annealing neural network algorithm provides a robust and effective method for the minimum concave cost transportation problem.
• The theoretical stability proofs and simulation results validate the algorithm's capability to find optimal or near-optimal solutions.