convex optimization

lagrangian relaxation

• aka alien trick, IOI 2016 task

visual explanation

• https://www.youtube.com/watch?v=AM6BY4btj-M
• https://www.youtube.com/watch?v=d0CF3d5aEGc
• https://www.youtube.com/watch?v=uh1Dk68cfWs

cvxpy

• Disciplined Convex Programming

cvxopt

picos

tsp polytope is convex and solution is on integer points

• no polynomial size LP for extended formulation of TSP, https://dl.acm.org/doi/10.1145/2716307