Research
Embedded Components from Concept-To-Manufacturing
Copper Foil Elements Affecting Transmission Loss with High Speed Circuits
pH neutral Cleaning Agents - Market Expectation & Field Performance
Reducing Dust Deposition on Electronic Equipment
New Requirements for Sir Measurement
Effects of Mixing Solder Sphere Alloys with Bismuth-Based Pastes
The Development of a 0.3 mm Pitch CSP Assembly Process
Generalizations About Component Flatness at Elevated Temperature
MORE RESEARCH
Latest Industry News
iPhone 12 Production Could Be Delayed
Acer sees PC component shortages
Bio-Ink for 3-D Printing Inside the Body
Covid Seen Driving the Security Sector
U.S. Eases Restrictions on Private Remote-Sensing Satellites
EMS Manufacturing quote complexity drives OEMs to look behind EMS curtain
U.S. Manufacturing Rebounds to 14-Month High
IBM's New AI Tool Parses A Tidal Wave of Coronavirus Research
MORE INDUSTRY NEWS

Special Purpose Integrated Circuits



Special Purpose Integrated Circuits
Scientists are exploring the use of integrated circuits to solve the traveling salesman problem, searching for the most efficient of routes.
Technology Briefing

Transcript


How would you go about returning books to the correct shelves in a large library with the least amount of walking? How would you determine the shortest route for a truck that has to deliver many packages to multiple cities? These are some examples of the “traveling salesman problem,” a type of “combinatorial optimization” problem, which frequently arises in everyday situations. Solving the traveling salesman problem involves searching for the most efficient of all possible routes. As everyone who has ever taken a business school “operations management” class knows, this quickly becomes an overwhelming challenge for humans or conventional computers.

To solve this conundrum, scientists are actively exploring the use of special-purpose integrated circuits. With this method, each state in a traveling salesman problem (for example, each possible route of the delivery truck) is represented by “spin cells,” each having one of two states. Here a circuit that can store the strength of one spin cell state over another represents the distance between two cities for the delivery truck. Using a large system containing the same number of spin cells and circuits as the cities and routes for the delivery truck, we can identify the state requiring the least energy, or the route covering the least distance, thus solving the traveling salesman problem or any other type of combinatorial optimization problem.

However, a major drawback of the conventional way of using integrated circuits to do this is that it requires pre-processing, and the number of components and the time required to input the data increase as the scale of the problem increases. For that reason, this technology has only been able to solve a traveling salesman problem involving a maximum of 16 cities.

However, a group of Japanese researchers aimed to overcome this constraint. They observed that the interactions between each spin cell are linear, which ensured that the spin cells could only interact with the cells near them, prolonging the processing time. So, they decided to arrange the cells differently to ensure that all spin cells could be connected to each other.

To do this, they first arranged the circuits in a two-dimensional array, and the spin cells were arranged separately in a one-dimensional arrangement. The circuits could then read the data and an aggregate of this data was used to switch the states of the spin cells. This means that the number of spin cells required, and the time needed for processing were both drastically reduced.

The researchers presented their findings at the IEEE’s 18th World Symposium on Applied Machine Intelligence and Informatics. The new technique constitutes a fully coupled method and has the potential to solve a traveling salesman problem involving up to 22 cities. The team is hopeful that this technology will have future applications as a high-performance system with low power requirements that will enable office equipment and tablet terminals to easily find optimal solutions for a wide range of combinatorial business problems.

Comments

No comments have been submitted to date.

Submit A Comment


Comments are reviewed prior to posting. You must include your full name to have your comments posted. We will not post your email address.

Your Name


Your Company
Your E-mail


Your Country
Your Comments



Board Talk
Solder Paste Beyond The Shelf Life?
Issues With Fillets on Via Holes?
Can Tape Residue Contaminate a Clean Tank?
Suggested Stencil Wipe Frequency?
Reflow Oven Zone Separation Challenges
When To Use Adhesive To Bond SMT Components
How To Clean a Vintage Circuit Board Assembly?
PCBA Inspection Concerns
MORE BOARD TALK
Ask the Experts
Lifted Lead on SOT Component
Allowable Bow and Twist on Round PC Fab
Mixed MSL Baking
Step Stencil Squeegee Angle
Solder Balling Splash After Reflow
Application Using No-Clean and Water Soluble Fluxes
IPC SOIC Defect Question
Mixed Process Solder Joint Appearance, Smooth or Grainy?
MORE ASK THE EXPERTS