Booked my stay at Edinburgh for OP26. Will be arriving on Saturday (30th of May) for ample time to hike in the beautiful landscape. Maybe Ben Nevis, maybe something closer and slightly less challenging. As I travel alone, feel free to text me if you wanna join.
Henrik A. Friberg
@hafriberg.bsky.social
Mathematical optimization enthusiast and part of the R&D team at MOSEK ApS.
For a decade it was open whether Frank-Wolfe's O(1/√ε) rate on strongly convex sets is tight. We show it is: Ω(1/√ε), even for a simple quadratic on a unit ball.
I wonder whether something similar can be done in the field of NP-hard problems, to obtain polynomial complexity results by similar (algorithmically mild) assumptions on scaling, perturbations, etc. This would shed light on why we are able to solve knapsack and TSP problems to very high dimension.
The simplex algorithm is super efficient. 80 years of experience says it runs in linear time. Nobody can explain _why_ it is so fast. We invented a new algorithm analysis framework to find out.
Is this just one more than the shortest snake needed to visit the closed neighborhood of each node at least once? 🤔
Snake-in-the-Box Problem xkcd.com/3125/
Having a strong background in programming, I find that code generation is a great exercise for peer reviewing. It starts with the naive approach, and then you iteratively refine it by corner case handling, performance tuning and simplification. Not unlike how some educational books are written.
10 ± 1 is (a) the boolean expression "9 or 11", (b) the set {9, 11}, (c) the interval [9, 11], (d) an ambiguous operation that can't be used without context?
Consider the LP problem min{cᵀx : Ax=b, x≥0} with dual max{bᵀy : Aᵀy≤c}. Adding Gaussian noise with std σ to all of A and c, the problem can be solved by a dual simplex method in O( 1/sqrt(σ) n^2.75 log(m)^1.75 ) pivot steps following the shadow vertex pivot rule. See arxiv.org/abs/2504.041....
Optimal Smoothed Analysis of the Simplex Method
Smoothed analysis is a method for analyzing the performance of algorithms, used especially for those algorithms whose running time in practice is significantly better than what can be proven through w...
arxiv.org
In November 1979, the NYT (🤮) writes of the then-new ellipsoid method that "the discovery may be applicable in weather prediction" Does anyone know how LP would be used in weather prediction?
When you are so deep into OR you start thinking about injective functions as 'codomain packing'.. 😅 Let f: X → Y and consider the sets {f(x)} for each element x∈X. The function is injective/surjective/bijective if and only if these sets forms a packing/covering/partitioning of Y.
Our latest blogpost is a little weekend treat for everybody interested in conic reformulations! themosekblog.blogspot.com/2025/02/a-sm...
A small breakthrough in the modeling of polynomial denominators
The MOSEK ApS official blog: announcements, new releases, activities, optimization modeling hints and examples.
themosekblog.blogspot.com
Today's word: Neutrosophic Number. Used to represent performance indicators such as product quality, delivery time, and cost, in the form of survey answers. An example is a triple such as (satisfied, uncertain, unsatisfied) = (70%, 10%, 20%).
In physics, if you isolate a subsystem from interaction it allows for quantum mechanical behavior in that subsystem. But is that only from our perspective?
This talk adds a whole new level of depth to the diet problem, showing that operations research is not always the science of better. Worth watching!
I recorded my current talk for youtube! If you are interested in linear programming or theoretical computer science, this is for you
Why aren't we always solving the convex Lagrange dual problems and extracting primal solutions from the dual variables? I investigated the duality gap at or.stackexchange.com/questions/12....
If the Lagrangian dual function is always concave, why aren't we "just" solving dual problems optimally?
Let $\mathcal{P}$ be the following primal optimization problem \begin{align} \mathcal{P}: \text{minimize}_x \quad & f_0(x)\\ \text{subject to} \quad & f_i(x) \leq 0, \quad i = 1, ..., m \\ ...
or.stackexchange.com