# linear programming Published articles for linear programming. This is one page of public article previews, not the complete archive. Follow Next page to continue. Summaries are not the original full articles. ## Earthmover Distance DevFeed: [Earthmover Distance]() Original publisher: [Read original article]() Published: 2018-03-05T08:00:15Z Content type: tutorial Language: en Sources: [Jeremy Kun]() Topics: [Code](), [Python](), [Library]() Tags: [code](), [earthmover-distance](), [gerrymandering](), [library](), [linear-programming](), [mathematics](), [optimal-transport](), [optimization](), [probability-theory](), [python](), [wasserstein-metric]() ### AI overview This tutorial explains how to measure distance between point sets with uncertain locations by treating each sample set as a discrete probability distribution. It formulates Earthmover distance as a linear program that minimizes the cost of moving probability mass between points. ### Source excerpt Problem: Compute distance between points with uncertain locations (given by samples, or differing observations, or clusters). For example, if I have the following three "points" in the plane, as indicated by their colors, which is closer, blue to green, or blue to red? It's not obvious, and there are multiple factors at work: the red points have fewer samples, but we can be more certain about the position; the blue points are less certain, but the closest non-blue point to a blue point is green; and the green points are equally plausibly "close to red" and "close to blue. ## Linear Programming and Healthy Diets -- Part 2 DevFeed: [Linear Programming and Healthy Diets -- Part 2]() Original publisher: [Read original article]() Published: 2017-09-24T08:00:46Z Content type: tutorial Language: en Sources: [Jeremy Kun]() Topics: [Programming](), [Data Science](), [Python](), [Code]() Tags: [linear-programming](), [math](), [optimize](), [programming](), [python](), [tutorial]() ### AI overview This tutorial presents a diet-planning problem as a linear program: minimizing daily calories while meeting minimum nutrient requirements. It introduces a Python solution using Google's open-source operations research tools and frames the example as a practical use case for linear programming. ### Source excerpt Previously in this series: Linear programming and healthy diets -- Part 1 Linear programing and the simplex algorithm Foods of the Father My dad's an interesting guy. Every so often he picks up a health trend and/or weight loss goal that would make many people's jaw drop. For example, we once went on a 5-day, 50-mile backpacking trip in the Grand Tetons, and my dad brought one packet of Lipton's Side Dishes noodle soup per day for dinner, and had vitamin tablets for the rest of his sustenance. ## Duality for the SVM DevFeed: [Duality for the SVM]() Original publisher: [Read original article]() Published: 2017-06-12T08:00:50Z Content type: tutorial Language: en Sources: [Jeremy Kun]() Topics: [Optimization](), [Programming](), [Algorithm]() Tags: [algorithm](), [lagrange-multipliers](), [linear-programming](), [optimization](), [programming](), [simplex-algorithm]() ### AI overview This tutorial explains how the Karush-Kuhn-Tucker theorem applies to the support vector machine optimization problem. It introduces the structure of convex quadratic optimization and states the conditions involving gradients, primal and dual constraints, and complementary slackness. ### Source excerpt This post is a sequel to Formulating the Support Vector Machine Optimization Problem. The Karush-Kuhn-Tucker theorem Generic optimization problems are hard to solve efficiently. However, optimization problems whose objective and constraints have special structure often succumb to analytic simplifications. For example, if you want to optimize a linear function subject to linear equality constraints, one can compute the Lagrangian of the system and find the zeros of its gradient. More generally, optimizing a linear function subject to linear equality and inequality constraints can be solved using various so-called "linear programming" techniques, such as the simplex algorithm. ## The Reasonable Effectiveness of the Multiplicative Weights Update Algorithm DevFeed: [The Reasonable Effectiveness of the Multiplicative Weights Update Algorithm]() Original publisher: [Read original article]() Published: 2017-02-27T08:00:42Z Content type: tutorial Language: en Sources: [Jeremy Kun]() Topics: [Algorithms](), [Programming](), [Machine learning](), [Optimization]() Tags: [algorithm](), [game-theory](), [javascript](), [linear-programming](), [machine-learning](), [mathematics](), [multiplicative-weights-update-algorithm](), [mwua](), [optimization](), [programming](), [python]() ### AI overview This tutorial explains the Multiplicative Weights Update Algorithm (MWUA), including its weight-update rule, an investment-expert example, and the algorithm's theoretical guarantee for identifying a strong expert over repeated rounds. It also introduces an interactive demonstration. ### Source excerpt papad Hard to believe Sanjeev Arora and his coauthors consider it "a basic tool [that should be] taught to all algorithms students together with divide-and-conquer, dynamic programming, and random sampling." Christos Papadimitriou calls it "so hard to believe that it has been discovered five times and forgotten." It has formed the basis of algorithms in machine learning, optimization, game theory, economics, biology, and more. What mystical algorithm has such broad applications? ## Linear Programming and the Simplex Algorithm DevFeed: [Linear Programming and the Simplex Algorithm]() Original publisher: [Read original article]() Published: 2014-12-01T10:00:59Z Content type: tutorial Language: en Sources: [Jeremy Kun]() Topics: [Algorithm](), [Programming]() Tags: [algorithm](), [code](), [exponential-time-algorithms](), [integer-programming](), [linear-algebra](), [linear-programming](), [lp-relaxation](), [optimization](), [programming](), [row-reduction](), [simplex-algorithm]() ### AI overview This tutorial explains how to implement the simplex algorithm for solving linear programs. It introduces standard form and shows how slack variables convert inequality constraints into equality constraints. ### Source excerpt In the last post in this series we saw some simple examples of linear programs, derived the concept of a dual linear program, and saw the duality theorem and the complementary slackness conditions which give a rough sketch of the stopping criterion for an algorithm. This time we'll go ahead and write this algorithm for solving linear programs, and next time we'll apply the algorithm to an industry-strength version of the nutrition problem we saw last time. ## Linear Programming and Healthy Diets -- Part 1 DevFeed: [Linear Programming and Healthy Diets -- Part 1]() Original publisher: [Read original article]() Published: 2014-06-02T09:00:27Z Content type: tutorial Language: en Sources: [Jeremy Kun]() Topics: [Optimization](), [Combinatorial optimization](), [Mathematics](), [Programming](), [Computer science]() Tags: [combinatorial-optimization](), [duality](), [linear-programming](), [mathematics](), [nutrition](), [operations-research](), [optimization](), [primal](), [programming](), [real-world]() ### AI overview This introductory tutorial explains linear programming as a central problem in combinatorial optimization. It models choosing quantities of oranges, milk, and broccoli to minimize food costs while meeting nutritional constraints, including recommended levels of water, calcium, and vitamin C. ### Source excerpt Optimization is by far one of the richest ways to apply computer science and mathematics to the real world. Everybody is looking to optimize something: companies want to maximize profits, factories want to maximize efficiency, investors want to minimize risk, the list just goes on and on. The mathematical tools for optimization are also some of the richest mathematical techniques. They form the cornerstone of an entire industry known as operations research, and advances in this field literally change the world.