• Home
  • Request Information
  • Customer Portal
  • Guided Troubleshooting Demo
  • Automatic Diagnosis Demo
  • Home
  • Solutions
    • Overview
    • Guided Troubleshooting
    • Remote Diagnosis
    • Diagnose Before Dispatch
    • Technology
    • FAQ – Why and How
    • Plain and Simple Promo
  • Products
    • TEAMS-Designer
    • TEAMS-RDS
    • TEAMATE
    • TEAMS-RT
    • PackNGo
  • Industries
    • Medical
    • Aerospace
    • Defense
    • Other Industries
  • Support
    • Documentation
    • FAQ
    • Product Releases
    • Publications
    • Training
    • Request Information
    • Customer Portal
    • Guided Troubleshooting Demo
  • Blogs
    • Health Management
    • Service Practices
    • TEAMS Modeling
    • TEAMS Products
  • About Us
    • Company Background
    • News
    • Careers
    • Contact

Solving Hard Optimization Problems by Passing Messages

November 19, 2026
by Krishna Pattipati
Comments are off

Imagine a row of tables at a wedding. At each table you have several seating plans. A guest at the end of one table will spend the evening beside the guest at the end of the next. How do you choose a plan for each table without trying every seating chart for the room?

Start at the last table. For each seating plan at the table before it, work out the best arrangement at the last table and record its cost. Pass that list back one table. The next person can now include the consequences for both tables in a new list. By the time the list reaches the first table, it accounts for the whole row. Choose the best plan there, then follow the recorded choices down the row.

That list is a message. It answers a conditional question: “If you make this choice, what is the best we can do on our side?” This is dynamic programming on a chain. Our paper, dedicated to the memory of Dimitri P. Bertsekas, asks what to put in a message when each decision can take any value in an interval.

Which Possibilities Should a Message Keep?

Think of a cost curve with several valleys. A quadratic approximation describes the shape near one point. Combining such approximations can compute a Newton step, an efficient way to refine a solution already in a promising valley. Choosing among distant valleys calls for a message that remembers several possibilities.

We tested this distinction on a 15 × 15 grid. Each of its 225 variables has a cost curve of its own, and neighboring variables pay a penalty for choosing different values. A whole region can settle in the wrong valley while every variable agrees with its immediate neighbors. Changing one value can make the solution worse even when moving the region together would improve it.

With a few sampled candidates at each site, the median cost was 42% above the best value found for its instance. Adding the bottoms of the individual cost curves’ valleys to the candidate lists cut that gap to 0.4%. Once those choices were available, omitting the repeated local optimization at each site gave a 0.3% gap and reduced median runtime from 129 to 40 seconds. The final refinement was the same in both runs.

When is the Search Worth Its Time?

On a chain, dynamic programming can choose the best combination from a list of valleys at every site. For a quadratic penalty between neighbors, we showed how a nearest-neighbor search computes each message exactly. The same calculation arises in wireless detection, where a receiver must untangle several users’ signals. On the tested asynchronous 12-user system, it cut the time for one stage of exact Viterbi decoding from 0.28 to 0.024 seconds.

Sometimes it pays to find a good guess before an exact search. For 32 synchronous users, the exact sphere decoder finished in 1.4–2.8 milliseconds at the median, before our collection of quick detectors could supply its guess. At 64 users, that guess narrowed the search enough to cut total median decoding time by a factor of 3.0–5.7 across the three signal-to-noise settings. Both routes returned an exact answer.

How Do You Know When to Stop?

Consider sensors scattered across a field. Each measures its distance to a few neighbors. To build a map, we minimize the sum of squared differences between measured distances and distances on the map. With noiseless measurements, a map that fits every distance has zero cost. Since squared errors cannot be negative, that gives us a stopping rule—even if two different maps fit equally well.

We tried an inexpensive relaxation and refinement first. It met the tolerance on 21 of 38 noiseless networks. A geometric search solved the remaining 17, so none required the expensive final solver. With noisy measurements, even the true map can have positive cost. A smaller distance error can help choose between maps, but it does not guarantee more accurate sensor positions.

The grid experiment illustrates a different stopping rule. A feasible solution on one 6 × 6 grid cost 15.50. By grouping each neighbor penalty with a share of both variables’ individual costs, we obtained a lower bound of 8.78 in about 20 seconds. Every feasible cost lies at or above that bound, so the optimum is between 8.78 and 15.50. The remaining interval tells us exactly what we have yet to establish.

Why This Matters to QSI

In diagnosis, two faults may explain the same failed test but predict different outcomes on the next one. A diagnostic message that carries both explanations preserves the value of running that test. This connects the paper to QSI’s work on multiple-fault diagnosis and test sequencing. The design question is concrete: which alternatives must a subsystem pass along so that the next test can tell them apart?

Research Paper: Krishna R. Pattipati, Message-Passing Dynamic Programming for Nonlinear Programming.

Please also see Supplement to Message-Passing Dynamic Programming for Nonlinear Programming.

In Memory of Dimitri P. Bertsekas

Prof. Bertsekas (1942-2026) was a brilliant applied mathematician, electrical engineer, and computer scientist. His research and mentoring positively influenced the fields of optimization, control, large-scale computation, reinforcement learning, and artificial intelligence. A prolific writer, he authored and co-authored over 20 books, monographs, and textbooks, edited several scientific journals, and founded the publishing company Athena Scientific. Prof. Bertsekas worked as a professor at Stanford University, the University of Illinois at Urbana-Champaign, MIT, and Arizona State University at Tempe. Students and colleagues will remember Dimitri P. Bertsekas as a dedicated educator and passionate researcher and author.

About the Author
Dr. Krishna Pattipati is co-founder, CEO and Chairman of the Board of Qualtech Systems. Dr. Pattipati provides strategic direction to QSI’s business and technology roadmap.
Social Share

Support

  • Support
    • Documentation
    • FAQ
    • Product Releases
    • Publications
    • Training
    • Request Information
    • Customer Portal
Privacy Policy | Trademarks | ISO9001 Certified | QSI Master Agreement | Cookie Policy
© 2026 Qualtech Systems, Inc