cleancoder0

But nothing in ML stays the same between instances. The reason why ML works is because there are redundancies in the training set. I am pretty sure that distribution wise, set of TSP instances still has a lot of redundancies.

You would want your model to learn to execute something like MST or to approximate alpha-nearness or to remap the instance into a relaxation that when solved by a simpler algorithm results in a solution that, when remapped back to original, is feasible and optimal.

In the basic TSP there is a lot of data.

For example, the reason why minimum spanning tree works is because the algorithm makes use of the relationship between vertices. Similar techniques use alpha-nearness, Steiner trees and direct modifications of distance matrix to create relaxations of the TSP and improve the performance of local search (I believe most are implemented in LKH).

I am obviously not expecting NNs to be capable of doing something like that currently but I'm hoping they might be able to discover interesting instance patterns for something more constrained.

I am pretty sure that gentlemen at the lumber yard do not have 300kg deadlift events and are not competing.

It is well known that diet has very little to do with progress for an amateur athlete. Consistency is the biggest factor in long term success. If you want to eek out the most out of your body, then you might want to optimize, but then you're already deviating to obsessive behavior.

Yeah, if you want to increase your squat by 20% short-term, you're going to have to eat more food and be obsessive about it, but if you're fine with consistent training over a span of 10-20 years, there's no reason to stress too much about diet.

When I hear people talking about diet and "optimal performance", I always wonder what the hell are they doing that they need to optimally perform. Like, what exactly is optimal performance of a sedentary programmer that maintains elasticsearch clusters? What, he feels tired sooner if he's on a vegan diet instead of something else?

There is small amount of fiber in tofu, seitan, tempeh or other soy derivatives.

The "protein concentration" was mentioned together with iron, as if it is a problem of deficiency, not in the context of obsessive compulsive dieting by tweaking your macros to achieve the best results.

I am not sure the fiber budget you mention is a reality. There is no threshold where your body will stop behaving if you consume too much fiber.

This review debunks the "bioavailability" and "quality" claims quite easily.

"bioavailability" (pdcaas diaas) is a contrived measure of protein source completeness made up to characterize protein issues of starving humans. It was also calibrated on rats and pigs, not humans. The "complete protein" misinformation is everywhere. Even on Wikipedia https://en.wikipedia.org/wiki/Complete_protein (edit: now I see that someone recently changed the statement to "adequate proportion" while previously it was just referencing that it contains all 9 essential amino acids).

All plants contain all essential amino acids, including green grass. Completeness in case of no starvation does not mean a thing. If you are eating 3000kcal of wheat every day, protein is no longer a worry, despite wheat having a 25% made-up bioavailability measure that was deduced by checking what happens to nitrogen in a live pig.

The protein "concentration" is just not true. Chicken breast does not have 90g of protein in 100g of chicken breast. 35g of protein in 100g of raw soybean. You will have to find a really rare steak of 100g to top that.

> Many ex-vegans have been consistently anemic, even while taking iron supplements, until they re-introduced meat.

This is not at all the conclusion of peer reviewed articles. Increased occurrence of nutrient deficiencies in vegan populations does not exist. Some people get deficiencies on any diet, and this is also the case for diets that have low-calorie high-volume foods like plants. Nothing special about that. People need to eat more volume but rarely do so. Similarly, they need to eat more calories. Talking about micronutrients in a world with no starvation is unnecessary. If you're eating a variety of plants, enough calories, it is certain you are consuming all of the necessary nutrients and protein. If you want to do powerlifting, marathon running, you will need to adjust your diet, whatever diet it is.

100g of raw beans, or 100g of raw lentils, has more grams of protein than a chicken breast. 100g of raw soybeans has more grams of protein than same amount of beef.

Of course, "raw" is the catch word, because when cooked, beans/lentils fill with water and then you might claim that concentration has been lowered but the amount of protein stays the same (nothing is lost by cooking).

If you look at the roots of discrete optimization, all of the approaches used in a solver like Concorde (developed in the open), there's no where near the amount of development and paradigm shifts happening in ant colonies, genetic algorithms, genetic programming, tabu search, annealing and similar.

E.g., finding an efficient representation of time-windows+pickup-and-delivery+breaks+flexible-start-time that allows you to efficiently update the solution and get an answer if the solution is feasible after the change and what the new cost is, is more progress than changing some recombination patterns in your genetic algorithm that will result in improvement on the instance set you are optimizing for (basically overfitting to data).

Here's an example of a paper that lists various update/feasibility/cost diff algorithms and their time complexity for a bunch of subproblems on a list-of-location-ids representation. Any genetic algorithm that wants to be fast will need to deal with that too.

https://www.researchgate.net/profile/Thibaut-Vidal/publicati...

That's why I think that graph NNs might allow us to find a way to remap our simple representation to something more efficient that is easier to work with and that can apply local changes without much effort.

For example, what if you can apply a transformation to TSP problem with time windows by adding new vertices or changing the distance matrix to eliminate time windows completely but still keep applying very efficient local changes that bring you close to optimum fast (do the same for pickup-and-delivery, flexible start time, etc.). Similar thing, an integer linear programming solver is used but the way the constraints of your instance are defined is hard to work with, there is a local pattern you are not seeing that allows simplification.

There have been attempts to learn exploration strategies of ILP solvers with ML but none made leaps forward (unlike AlphaFold, AlphaZero, AlphaGo, or even AlphaCode - competitive programming code generation). The biggest reason for that is that the current principled algorithms (60-30 years old) are insanely good on fundamental problems.

I remember reading about a new set of constraints, nurse rostering (nurse scheduling), and once researchers applied the principled methods, all of the instances of interest got solved to proved optimality. The amount of genetic algorithms, ant colonies and who knows what that was applied to these instances in the meanwhile was ridiculous and unnecessary.

There's a lot of companies that want to provide an Uber/Lyft-like service of their own product. So you have a bunch of smaller problems that you want to solve as best as possible in ~1 second.

A lot of small companies with their delivery fleets want to optimize (pest control, christmas tree delivery, cleaning, technical service, construction (coordinating teams that construct multiple things at multiple locations at the same time) etc.).

On the other hand, not related to TSP, the whole energy market in the US is very LP/ILP optimizable and has a lot of customers (charging home batteries, car batteries, discharging when price is high, etc.).

I would admit that the scientific field of discrete optimization is littered with genetic algorithms, ant colonies and other "no free lunch" optimization algorithms that make very little sense from progress perspective, so it does feel like the golden era was from the 70s to early 90s. I do not have a PhD but somehow ended up doing machine learning and discrete optimization most of my career.

When TSP is mentioned today, unlike 50 years ago when LK heuristic got published, I assume all of the popular & practical variants, like time window constraints, pickup and delivery, capacity constraints, max drop time requirement after pickup, flexible route start, adding location independent breaks (break can happen anytime in the sequence or in a particular time window of day) etc. Some of the subproblems are so constrained that you cannot even move around that effectively as you can with raw TSP.

Some of the subproblems have O(n) or O(n log n) evaluations of best local moves, generic solvers are even worse at handling that (Concorde LP optimizations cannot cover that efficiently). When no moves are possible, you have to see what moves brings you back to a feasible solution and how many local changes you need to do to accomplish this.

For example, just adding time windows complicates or makes most well known TSP heuristics useless. Now imagine if we add a requirement between pairs of locations that they need to be at most X time apart (picking up and then delivering perishable goods), that the route can start at an arbitrary moment etc.

I personally spent quite a lot of time working on these algorithms and I'd say the biggest issue is instance representation (is it enough to have a sequence of location ids ?). For example, one of my recent experiments was using zero suppressed binary decision diagrams to easily traverse some of these constrained neighborhoods and maintain the invariants after doing local changes. Still too slow for some instances I handle (real world is 5000 locations, 100 salesmen and an insane amount of location/salesmen constraints).

Optimization is also data, given a local state, can you identify the sequence of transformations that will get you to a better state. The reward is instantly measurable and the goal is minimizing the total cost.

Eventually it was extended to work with an external data source that it queries. This is not a new thing, for example, image style transfer and some other image tasks that were attempted before the domination of NNs did the same thing (linear models would query the db for help and guided feature extraction).

The greatest effect in transformers is the attention mechanism combined with self-supervised learning. Investigations in self-supervised learning tasks (article illustrates one word gap, but there are others) can result in superior models that are sometimes even easier to train.

As for SAT, optimization, graph neural networks might end up being more effective (due to high structure of the inputs). I'm definitely awaiting for traveling salesman solver or similar, guided by NN, solving things faster and reaching optimality more frequently that optimized heuristic algos.

There is nothing one can do to avoid disease eventually.

Some people start getting sick in their 80s, some die healthy & peacefully in their sleep in their 90s and some get cancer being <10 years old.

The fact that layers themselves are narrower means that training and evaluation of the NN is also much faster.

Similarly, Ukranian army is not targeting Russian civilians in these regions and is not banishing them to Russia. There is no displacement of millions of Russians in Ukraine.

If you are trying to say "NATO bombing of Serbia is justified", therefore "Russia war against Ukraine should be too", therefore hypocrites, it does not really work.

I mean, it's probably going to hit moist areas first. So India should be one of the first countries to experience lethal wet-bulb temperatures.

I guess they might be affected once Russia starts borrowing the cash from citizens to fund the war.

Crimea for some reason was annexed, despite leadership in Crimea wanting the same status given to two countries mentioned above.

You mentioned that this cannot be said for a lot of EU countries. Turks born in EU do not have to learn German. Immigration within EU is free from language requirement too.

I do not even understand why do you think minorities not learning Serbian is impressive? Croatia and Kosovo both have schools that can use Serbian in their curriculum and no one is forcing Croatian on them. Similar things exist for Czech and Hungarian. No one is forcing these minorities to go to schools to learn Croatian.

> Didn't those two breakaway republics declare independence?

And were immediately annexed by Russia? How independent is that? Who's the new cultural head of these independent republics?

Yeah, I guess he stopped existing in 2000 and had nothing to do with the peaceful referendum.

> Because it is the same, a territory within a country decided it wanted to be independent and it is supported by an outside imperial force.

How can you believe this? Which part of Ukraine declared independence? What country was supposed to be created out of this independence? Which leaders decided they wanted to create a new independent territory?

> I am not sure the same can be said for a lot of EU countries.

Well, if your country is in EU, the citizens of EU are not forced to learn any language, even if they live outside of their country of origin. Language requirements for non-EU exist due to EU being an extremely lucrative place to live. Moving to Serbia and trying to hop on social benefits will not be as lucrative, so language requirement for citizenship might be unnecessary.

> It guarantees us a seat in the parliament, you just have to pass a laughably low percentage of the general vote.

In Croatia and Kosovo, there is no low percentage threshold. You are automatically in. There's no reason to believe the threshold is achievable, given that people in general do not vote.

https://en.wikipedia.org/wiki/Ten-Day_War

NATO bombing was not out of the blue. The head of Yugoslavia was a similar mad man (to Putin), just warring out of desperation. The best proof one has of his lunacy is the fact that Montenegro split from Serbia without any deaths. How did this happen? Due to the mad man dying in 2000. I'm pretty sure he would have enacted order by butchering civilians again, inside "his" borders.

Serbia is also the only country out of these conflicts that does not guarantee seat in the parliament for the exYugoslav minorities. Even though the leadership displayed aggression that was successfully deflected, the defenders made a deal to guarantee inclusion of the Serbian minority in the parliament (Croatia, Kosovo etc.)

Still, we have a country like Germany, that self-flagellates for decades and the sentiment of the majority is quite clear. While the general sentiment of people/press in Serbia is that NATO bombing is equivalent to Putin bombing Ukraine. and yeah, every now and then, the most popular Serbian (Monacoan) tennis player will say things like "Kosovo is Serbia" with complete indifference and still be the Jesus like figure his father makes him out to be.

I'm always humbled when I try to solve something, need 50-100 lines of code, and then there's a solution that really gets what the inputs/outputs/intermediate data structures are and it turns out to be just 10 lines of code (written during live competition, I'm amazed by the truly simple thinking of these authors). The best problems that demonstrate that are most often just algorithms with arrays (no specific algorithm, only required knowledge is working with arrays). True display of thinking things through before coding.

I guess example that come to mind (a mindblowingly simple algorith, try to find it yourself): https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_v...

It gives me similar feeling (but less pronounced) to looking at tinycc, or looking at some tree enumeration algorithm in TAOCP, or the modification of it done by Knuth to support enumerating arithmetic expressions without redundant parentheses (also just an array algorithm, figure out how to modify an array that represents existing expression into an array that represents next expression, literally just a bunch of loops).

I had to handle time series data at work. There already exists 1000s of lines of code that deal with time series, sorted timestamp arrays, {up,down}sampling, timezone handling etc. All of that can be replaced by a simple 5 line function that works faster (supports tz, sampling, appends etc.). Only possible to write if you really focus on the problem you're solving and realize that the sub-problem you envisioned (the "efficient" time series data structure) does not really help you.

Reaching high performance means knowing the solution before coding it up.

Witnessing high level competitive programmers scribble stuff on paper for 5-10 minutes, and then just a pure stream of thought into a 100 line C++ program that was compiled once, run through examples, submitted and accepted, is out of this world.

Another example is when solution is unclear (mostly for number theoretic stuff that needs to be efficient), scribble on paper, code up pattern generating code, generate patterns, look at them, stop, scribble on paper, code the O(1) solution, submitted and accepted (an easy example is to efficiently calculate the sum of first N Fibonacci numbers).

If you ate 500 grams of raw beans (cooked), having 1.5kg of excrement going through your bowels will leave you quite satiated.

On my plant-only days, whenever I eat that much volume of food to get to 3500kcal (I weigh 220lbs and eat 4000kcal+ on regular days), I am basically satiated after first 2000kcal for the whole day and have to force myself to eat more. This is whole plants, no oils.

Of course, the massive poop next morning makes it worth the trouble :D

You said it yourself that you were always starving as a vegan. Given that you were a "good" vegan, living on low calorie foods, I cannot see how you think you ate more calories, but were starving.

If you told me you had a 150kg squat, 200kg deadlift and did 6+ hours of hiking every week, but still had issues with weight and always felt hungry, I would be quite surprised, because there's no way you could maintain maximal force production with low calories. All of that muscle would also not be there with low calories.

Vegan food is rich in carbs, so saying you cannot metabolize short chain fatty acids is irrelevant when most of your calories came from carbs. Your body can turn these carbs to fatty acids that your genes can deal with (to create hormones, if you had enough protein too). If we think about essential fatty acids, then your hypothesis is testable, either by taking a long essential fatty acid supplement (EPA + DHA), or by measuring your EPA/DHA plasma levels after consuming ALA rich plant oils like flexseed (not olive oil, and most definitely not sunflower oil). Still, no way deficiency of ALA metabolites is going to put you in a weird starvation mode. It's the starvation that is causing your metabolism to shutdown. Of course you will have trouble metabolising ALA if you are starving.

Yes, it's not about food, it's about calories. Individuals that want to function well need to eat enough. If your issue was short fatty acids, then it's quite impressive that your diet fixed it. Long fatty acids are not essential, and to function you need to be able to create metabolites from short fatty acids, because not all long fatty acids required for human hormones and metabolism are present in your food.