Math317Fa26 Lec17 StatErrors TSP Linearizing
Watch on YouTube →
Overview
Steven Miller connects practical data verification with operations research: AI-generated baseball playoff data contained factual and rule-based errors, so he recommends supplying source files, checking outputs, and stating tool details clearly. He then formulates a traveling salesman problem with time-indexed binary variables and explains how binary expansions and auxiliary indicators can convert integer-valued polynomial objectives into linear expressions, at the cost of many additional constraints.
Key takeaways
- AI-generated factual datasets can contain errors in both remembered results and historical rule changes; Miller’s baseball example required authoritative game files and spot checks to establish reliability.
- When using AI for research, provide source data directly, ask it to flag missing information rather than guess, and document the model and subscription tier used.
- A time-indexed TSP model uses X(i,j,s) binary variables to represent moves, with city-entry, city-departure, self-loop, and step-to-step continuity constraints.
- Fixing city 0 as both start and destination reduces the route choices, while linking each arrival at step s to a departure at step s+1 helps prevent disconnected cycles.
- Integer polynomial objectives can be represented using binary expansions and auxiliary variables for products, converting nonlinear terms into linear expressions within a mixed-integer model.
- Linearization can make more objective functions accessible to optimization solvers, but the added indicator variables and if-then constraints may make computation costly.
Chapters
- Steven Miller found multiple errors when AI reconstructed baseball data for a paper, including incorrect home teams and playoff series results.
- Some mistakes came from applying current playoff structures or league assignments to earlier seasons, when the rules differed.
- AI also presented uncertain or incorrect results confidently, making verification essential, especially for consequential data such as medical evidence.
- Miller recommends downloading authoritative game-by-game files, providing those source files to AI, and spot-checking computed results rather than relying on memory.
- For 50-minute challenges, prepare reusable prompt instructions in advance and run multiple tasks or AI systems in parallel where possible.
- Reports should identify the AI system and subscription tier, and prompts should ask about secondary effects such as demand shifting or traffic congestion.
- The traveling salesman problem seeks a route that visits every city while minimizing a measure such as distance, travel time, or cost.
- A closed tour returns to its starting city; allowing arbitrary start and end cities adds choices and makes the model more general.
- Routes depend on available connections, not just geographic distance: Miller compares flight access from Albany to Chicago and Dallas.
- Miller labels cities 0 through C, assumes every city is connected to every other for the basic model, and fixes city 0 as the start and end.
- A graph with limited connections may not permit a route that visits each city exactly once; degree structure can make such a path impossible.
- The route takes C+1 moves when it visits C other cities and then returns to city 0.
- The decision variable X(i,j,s) equals 1 when the route moves from city i to city j at step s, and 0 otherwise.
- The objective sums travel costs T(i,j) for the selected moves; cost can represent time or another measure.
- Constraints require each nonzero city to be entered exactly once and require exactly one departure from each city.
- The entry and departure constraints alone can permit invalid self-moves or disconnected cycles, so the model must rule out moves from a city to itself.
- Miller proposes linking time steps: entering city j at step s requires leaving city j at step s+1.
- The model fixes a departure from city 0 at the initial step and a return to city 0 at the final step, making the route a continuous tour.
- The time-linked constraints ensure that each move continues the same route and, across C+1 steps, visits every other city once before returning to 0.
- The traveling salesman problem can be difficult to solve optimally, but a solver can run for a limited time and return a near-optimal answer.
- Miller connects time-limited optimization to his movie project, where the team had two hours to prepare results, and cites 3D printing and circuit construction as routing applications.
- Miller turns to nonlinear objective terms such as n squared or n cubed, which can arise when material cost scales with surface area and value with volume.
- For an integer n between 0 and N, write n as a sum of binary indicators beta_i multiplied by powers of two.
- Because each beta_i is either 0 or 1, beta_i squared equals beta_i, allowing some polynomial terms to simplify.
- For products of distinct binary variables, introduce an auxiliary indicator gamma_ij that equals 1 when both beta_i and beta_j equal 1.
- Express n squared as a weighted sum of these binary products, then replace each product with its gamma variable to obtain a linear expression.
- If-then constraints enforce the auxiliary indicators, but higher-degree polynomials can require many new variables and constraints, making the approach theoretically useful but potentially expensive.
Transcript excerpt
0:00 To math 317 operations research. This is lecture I think 17. 17. And so what I want to do is before going into new material, I want to talk a little bit about some of the baseball data. And so I had mentioned yesterday that I was working on a project with some William students and the journal wanted us to you know, reproduce some of the tables and data we used and we didn't have everything saved unfortunately. So I used the AI to generate it. And then I tested AI and found out that AI had made multiple mistakes. And so these will all be in the slides so you can read it closely. Your mistake number one it was generating factual data from memory. And so just some of the results were just wrong as to which team was the home
0:48 team, which team won the playoff series. It was just easily provably wrong. Now, this is just a baseball paper. Nothing really matters. But if this was medical data and we're making inferences from this and so to me it was absolutely terrifying that it would reproduce what it said was true data without giving a flag. And so I strongly urge you to just look at the slides later. All the details you know, the six different mistakes. Uh a lot of them once I told it what it was doing wrong, it was able to fix it. But you can't just trust the data that's coming out. And this is at least a moderately paid version of it. And it goes through incorrectly um is using wrong rules for applying
1:36 things. So sometimes rules change. So baseball they keep changing what the playoff structure is. They sometimes even change which league a team is in.
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
In this course
Related notes
Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Steven Miller.