# linear programming

39 results back to index

pages: 130 words: 11,880

Optimization Methods in Finance by Gerard Cornuejols, Reha Tutuncu

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

Delayed data is available for free, so do not use the sites that charge fees for real-time data. Formulate the linear programming problem (33) (or, rather the 42 CHAPTER 3. LP MODELS AND TOOLS IN FINANCE version you developed for Problem 4 since market quotes will include bid and ask prices) to determine whether these prices contain any arbitrage opportunities. Solve this linear programming problem using an LP software. Here are some suggestions: • MATLAB has a linear programming solver that can be accessed with the command linprog. Type help linprog to find out details. • If you do not have access to any linear programming software, you can use the website http://www-neos.mcs.anl.gov/neos/ to access the Network Enable Optimization Server. Using this site, and their JAVA submission tool, you can submit a linear programming problem (in some standard format) and have a remote computer solve your problem using one of the several solver options.

Consider the following linear programming problem: max 4x1 + 3x2 3x1 + x2 ≤ 9 3x1 + 2x2 ≤ 10 x1 + x2 ≤ 4 x1 , x2 ≥ 0. First, transform this problem into the “standard form”. How many basic solutions does the standard form problem have? How many basic feasible solutions? What are the basic feasible solutions and what are the extreme points of the feasible region? 2. We say that two linear programming problems are equivalent if one can be obtained from the other by (i) multiplying the objective function by -1 and changing it from min to max, or max to min, and/or (ii) multiplying some or all constraints by -1. For example, {min cT x : s.t.Ax ≥ b} and {max −cT x : s.t. − Ax ≤ −b} are equivalent problems. Find a linear program which is equivalent to its own dual. 28 CHAPTER 2. LINEAR PROGRAMMING: THEORY AND ALGORITHMS Chapter 3 LP Models and Tools in Finance 3.1 Derivative Securities and The Fundamental Theorem of Asset Pricing One of the most widely studied problems in financial mathematics is the pricing of derivative securities, also known as contingent claims.

These two alternative approaches are not problem classes (as in LP, QP, etc.) but rather modeling techniques for addressing data uncertainty. 1.2.1 Stochastic Optimization The term stochastic optimization or stochastic programming refers to an optimization problem in which some problem data are random. The underlying optimization problem might be a linear program, an integer program, or a nonlinear program. An important case is that of stochastic linear programs. A stochastic program with recourse arises when some of the decisions (recourse actions) can be taken after the outcomes of some (or all) random events have become known. For example, a two-stage stochastic linear program with recourse can be written as follows: max (c1 )T x1 + E[max c2 (ω)T x2 (ω)] A1 x 1 = b1 (1.6) B 2 (ω)x1 + A2 (ω)x2 (ω) = b2 (ω) x1 ≥ 0, x2 (ω) ≥ 0, where the first-stage decisions are represented by vector x1 and the second-stage decisions by vector x2 (ω), which depend on the realization ω of a random event.

pages: 245 words: 12,162

In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation by William J. Cook

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

“The final test of a theory is its capacity to solve the problems which originated it.”10 This is a bold way to open a 600-page volume, but sixty years of experience has shown repeatedly that his theory of linear programming and the accompanying simplex algorithm pass the test beyond all expectations. The scope of the use of linear programming in industry is breathtaking, covering pretty much any sector you can name. Although it is difficult to quantify, it is clear that planning via linear programming saves enormous amounts of the world’s natural resources every day. It terms of money, a New York Times article by Gina Kolata states, “Solving linear programming problems for industry is a multibillion-dollar-a-year business.”11 Take that, Professor Hotelling. Readers interested in learning the art of capturing problems with linear constraints can find what they are looking for in Paul Williams’s excellent book Model Building in Mathematical Programming.12 Williams’s examples include food manufacturing, refinery optimization, farm planning, mining, airline pricing, power generation, and on and on.

Helsgaun is the current holder of the best-known tour in the World TSP challenge, he provided the optimal tour for the record 85,900-city TSP, and his name peppers the leader board for the VLSI Test Collection.25 Not to be outdone, Nagata’s implementation of a genetic algorithm for the TSP has produced the best-known tour in the Mona Lisa TSP challenge as well as record solutions for the two largest examples in the National TSP Collection.26 If you want a good solution to a large problem, these are the people to call. 93 5: Linear Programming The development of linear programming is—in my opinion—the most important contribution of the mathematics of the 20th century to the solution of practical problems arising in industry and commerce. —Martin Grötschel, 2006.1 electing the best tour through a set of points and knowing it is the best is the full challenge of the TSP. Users of a brute-force algorithm that sorts through all permutations can be certain they have met the challenge, but such an approach lacks both subtlety and, as we know, practical efficiency. What is needed is a means to guarantee the quality of a tour, short of inspecting each permutation individually. In this context, the tool of choice is linear programming, an amazingly effective method for combining a large number of simple rules, satisfied by all tours, to obtain a single rule of the form “no tour through this point set can be shorter than X.”

The number X gives an immediate quality measure: if we can also produce a tour of length X then we can be sure that it is optimal. Sounds like magic, but linear programming is indeed the method adopted in Concorde and in all of the most successful exact TSP approaches proposed to date. Moreover, its application to problems beyond the TSP has made it one of the great success stories of modern mathematics. S General-Purpose Model The tale of linear programming has a nice start, with a young George Dantzig arriving late for a class given by Jerzy Neyman at the University of California at Berkeley in 1939. The first-year graduate student hurriedly copied down two problems he found written on the board and turned in solutions several days later. “To make a long story short, the problems on Linear Programming the blackboard that I had solved thinking they were homework were in fact two famous unsolved problems in statistics.”2 Not a bad week’s work.

pages: 312 words: 35,664

The Mathematics of Banking and Finance by Dennis W. Cox, Michael A. A. Cox

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

Continuous Uniform Distribution Exponential Distribution 8 Normal Distribution 8.1 Introduction 8.2 Normal Distribution 8.2.1 A simple example of normal probabilities 8.2.2 A second example of normal probabilities 8.3 Addition of Normal Variables 8.4 Central Limit Theorem 8.4.1 An example of the Central Limit Theorem 8.5 Confidence Intervals for the Population Mean 8.5.1 An example of confidence intervals for the population mean 8.6 Normal Approximation to the Binomial Distribution 8.6.1 An example of the normal approximation to the binomial distribution 8.7 Normal Approximation to the Poisson Distribution 8.7.1 An example of fitting a normal curve to the Poisson distribution vii 56 57 58 59 60 60 62 64 66 67 67 67 69 69 70 70 70 71 71 72 72 72 73 9 Comparison of the Means, Sample Sizes and Hypothesis Testing 9.1 Introduction 9.2 Estimation of the Mean 9.2.1 An example of estimating a confidence interval for an experimental mean 9.3 Choice of the Sample Size 9.3.1 An example of selecting sample size 9.4 Hypothesis Testing 9.4.1 An example of hypothesis testing 9.5 Comparison of Two Sample Means 9.5.1 An example of a two-sample t test 9.6 Type I and Type II Errors 9.6.1 An example of type I and type II errors 75 75 75 10 Comparison of Variances 10.1 Introduction 10.2 Chi-Squared Test 10.2.1 An example of the chi-squared test 10.3 F Test 10.3.1 An example of the F test 10.3.2 An example considering the normal distribution 83 83 83 83 85 85 85 76 77 77 77 78 79 79 80 80 viii Contents 11 Chi-squared Goodness of Fit Test 11.1 Introduction 11.2 Contingency Tables 11.3 Multiway Tables 11.3.1 An example of a four by four table 91 91 92 94 94 12 Analysis of Paired Data 12.1 Introduction 12.2 t Test 12.3 Sign Test 12.4 The U Test 12.4.1 An example of the use of the U test 97 97 97 98 99 101 13 Linear Regression 13.1 Introduction 13.2 Linear Regression 13.3 Correlation Coefficient 13.3.1 An example of examining correlation 13.4 Estimation of the Uncertainties 13.5 Statistical Analysis and Interpretation of Linear Regression 13.6 ANOVA for Linear Regression 13.7 Equations for the Variance of a and b 13.8 Significance Test for the Slope 13.8.1 An example of slope analysis 13.8.2 A further example of correlation and linear regression 103 103 103 104 105 109 110 110 112 112 113 115 14 Analysis of Variance 14.1 Introduction 14.2 Formal Background to the ANOVA Table 14.3 Analysis of the ANOVA Table 14.4 Comparison of Two Causal Means 14.4.1 An example of extinguisher discharge times 14.4.2 An example of the lifetime of lamps 121 121 121 122 123 123 125 15 Design and Approach to the Analysis of Data 15.1 Introduction 15.2 Randomised Block Design 15.2.1 An example of outsourcing 15.3 Latin Squares 15.4 Analysis of a Randomised Block Design 15.5 Analysis of a Two-way Classification 15.5.1 An example of two-way analysis 15.5.2 An example of a randomised block 15.5.3 An example of the use of the Latin square 129 129 129 130 131 132 135 137 140 143 16 Linear Programming: Graphical Method 16.1 Introduction 149 149 Contents 16.2 Practical Examples 16.2.1 An example of an optimum investment strategy 16.2.2 An example of the optimal allocation of advertising ix 149 149 154 17 Linear Programming: Simplex Method 17.1 Introduction 17.2 Most Profitable Loans 17.2.1 An example of finance selection 17.3 General Rules 17.3.1 Standardisation 17.3.2 Introduction of additional variables 17.3.3 Initial solution 17.3.4 An example to demonstrate the application of the general rules for linear programming 17.4 The Concerns with the Approach 159 159 159 164 167 167 167 167 18 Transport Problems 18.1 Introduction 18.2 Transport Problem 171 171 171 19 Dynamic Programming 19.1 Introduction 19.2 Principle of Optimality 19.3 Examples of Dynamic Programming 19.3.1 An example of forward and backward recursion 19.3.2 A practical example of recursion in use 19.3.3 A more complex example of dynamic programming 19.3.4 The ‘Travelling Salesman’ problem 179 179 179 180 180 182 184 185 20 Decision Theory 20.1 Introduction 20.2 Project Analysis Guidelines 20.3 Minimax Regret Rule 189 189 190 192 21 Inventory and Stock Control 21.1 Introduction 21.2 The Economic Order Quantity Model 21.2.1 An example of the use of the economic order quantity model 21.3 Non-zero Lead Time 21.3.1 An example of Poisson and continuous approximation 195 195 195 196 199 200 22 Simulation: Monte Carlo Methods 22.1 Introduction 22.2 What is Monte Carlo Simulation?

pages: 236 words: 50,763

The Golden Ticket: P, NP, and the Search for the Impossible by Lance Fortnow

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

Optimizing your choices given these kinds of requirements is a problem known as linear programming. The set of possible solutions forms what is known as a polytope in high-dimensional space. Back in 1947, Georg Dantzig created the simplex method, which solves the linear programming problem pretty quickly. The simplex algorithm takes a walk along the edges of the polytope until it finds the optimal solutions. Given the simplex algorithm, why do I put the linear programming problem in this category? Because the simplex algorithm may not solve linear programming quickly in some rare instances. In 1979, Leonid Khachiyan created the ellipsoid algorithm, which chops up the polytope into smaller and smaller pieces until it narrows it down to the optimal solution. Kahachiyan gives a proof of efficiency of the ellipsoid algorithm, putting linear programming in P. However, the ellipsoid algorithm takes much longer than simplex in practice.

The ellipsoid algorithm did inspire many other more complex algorithms in the decades to come, making the ellipsoid algorithm an extremely influential one. Figure 4-12. Polytope. So the linear programming problem has good algorithms in theory and practice—they just happen to be two very different algorithms. In 1984, Narendra Karmarkar developed the interior point algorithm. Karmarkar’s algorithm takes a walk like the simplex algorithm but through the polytope instead of around it. Like the ellipsoid algorithm, interior point is known to be in P, and after some optimization the algorithm performs favorably compared with simplex. That’s three very different algorithms for solving the linear programming problem. The first (simplex) works well in practice. The second (ellipsoid) works well in theory. The third (interior point) works well both in theory and practice.

If you see the numbers 84,578,657,802,148,566,360,817,045,728,307,604,764,590,139,606,051 and 97,823,979,291,139,750,018,446,800,724,120,182,692,777,022,032,973, you can multiply them together quickly and see that the product is 8,273,820,869,309,776,799,973,961,823,304,474,636,656,020,157,784,206,028,082,108,433,763,964,611,304,313,040,029,095,633,352,319,623. Computer scientists don’t believe that factoring is in P, nor do we believe that factoring is NP-complete. Factoring is a difficult problem, but maybe not as hard as satisfiability or map coloring. The importance of primes and factoring goes way beyond mathematicians loving their numbers. Much of modern cryptography uses numbers that seem hard to factor, the topic of chapter 8. Linear Programming Frenemy Fancy Franks sells four varieties of sausages: frankfurters, Italian, bratwurst, and chorizo. Each kind of sausage has various ingredients with different costs. Different sausages take different times to manufacture, and they sell at different prices. How much of each sausage should Frenemy Fancy Franks make in order to maximize profits? Finding the best allocation of sausages means maximizing revenue while fulfilling various requirements.

pages: 425 words: 122,223

Capital Ideas: The Improbable Origins of Modern Wall Street by Peter L. Bernstein

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

Koopmans developed an analytic method known as linear programming or activity analysis that falls under the general heading of operations research. Linear programming solves problems that involve combinations of inputs and outputs. Assume, for example, that an airline has a limited number of airplanes, hours of flying time, crew availabilities, and gates at airports along its routes. How many flights a day to how many locations can the airline make? If it aims to make, say, 200 flights a day, how can it minimize the necessary amount of flying time and crew time and number of airplanes? How would the answers to these questions differ if the airline wanted to make economizing on crew time its most important objective? Or if it wanted to make as many landings as possible in the New York City area? Linear programming identifies the combinations of inputs and outputs that are achievable, defines the combinations that minimize the inputs and maximize the outputs, and then identifies the trade-offs required if one element is increased or decreased relative to the others.

Markowitz recognized that error and developed a systematic means to avoid it. Markowitz’s reflections on diversification and risk led him to explore the subject more thoroughly in a linear programming course he was taking under Koopmans. Koopmans had asked the class to describe a resource allocation problem and state whether or not it was a linear programming problem. Markowitz took the occasion to analyze the choices facing an investor who must decide between seeking high returns and attempting to hold down risk at the same time. He concluded that the solution to this problem was even more complex than linear programming. Koopmans gave him an A on his paper and noted, “The problem does not seem that hard. Why don’t you solve it?”10 That assignment was a trial run for what later developed into “Portfolio Selection” and Markowitz’s doctoral dissertation.

Diversification may reduce risk, but it also tends to reduce the opportunity to earn the high rewards that an investor might achieve by following Keynes’s advice: Put all your eggs in the one basket that looks like the best basket of all. The tension between risk and return, between diversification and concentration, was just the beginning of Markowitz’s breakthrough. He then followed the idea down two separate tracks. The first track tells the investor how to apply the trade-off between risk and reward in selecting a portfolio; this is the subject matter of his 1952 article and is closely related to the techniques of linear programming that Markowitz learned from Koopmans. The second track tells how each investor should go about selecting the single portfolio that most closely conforms to the investor’s goals. A much fuller treatment of this aspect appears in Markowitz’s book, Portfolio Selection: Efficient Diversification of Investment, which was essentially completed in 1955 as his Ph.D. thesis but was not published until 1959.

pages: 406 words: 88,820

Television disrupted: the transition from network to networked TV by Shelly Palmer

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

Pay Per View • On-demand • Subscription • Ad-supported Distribution Traditional network television was developed to deliver linear programming using a fairly efficient one-to-many system. Alternatively, networked television systems offer one-to-one and optionally, non-linear distribution. Linear Distribution Methodology • Broadcast television – analog or DTT • Cable Television – basic or premium • Satellite television • Internet Protocol Television (IPTV) • IP Video • Public Internet Non-Linear Distribution Methodology • Video On Demand (VOD, SVOD, FVOD, Near-VOD) • Consumer-based time-shifted (personal video recorder, TiVo®, Media Center) Technically speaking, all of the linear methodologies could be used to distribute non-linear programming as well. But in common practice, only cable, IPTV and the Internet are used to do so.

All rights reserved. 1-Television.Chap One v3sp.qxd 3/20/06 7:19 AM Page 21 Linear Video – Good “Old-Fashioned” TV 21 Linear Video – Good “Old-Fashioned” TV Linear video for television (analog broadcast or DTT) and cable (basic or premium) is what most people think of as “good old-fashioned TV.” Linear channels and networks can be found on all broadcast television stations, cable, satellite and IPTV systems. The unique attribute of linear television is that it is scheduled for you by the network or station programmers. Marketers sometimes refer to linear programming as “destination television” because you are supposed to watch the program when it is presented. (Of course, consumers don’t always do what they’re supposed to do.) When distributed over traditional networks, linear television is still the most efficient way to distribute emerging news stories, evolving stories that need continuous coverage, sports and other live events. Since almost the beginning of the commercial television business, the industry has relied on two kinds of distribution licenses for linear video, “exclusive” and “non-exclu-sive.”

pages: 372 words: 101,174

How to Create a Mind: The Secret of Human Thought Revealed by Ray Kurzweil

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

Grötschel, an expert in optimization, observes that a benchmark production planning model solved using linear programming would have taken 82 years to solve in 1988, using the computers and the linear programming algorithms of the day. Fifteen years later—in 2003—this same model could be solved in roughly 1 minute, an improvement by a factor of roughly 43 million. Of this, a factor of roughly 1,000 was due to increased processor speed, whereas a factor of roughly 43,000 was due to improvements in algorithms! Grötschel also cites an algorithmic improvement of roughly 30,000 for mixed integer programming between 1991 and 2008. The design and analysis of algorithms, and the study of the inherent computational complexity of problems, are fundamental subfields of computer science. Note that the linear programming that Grötschel cites above as having benefited from an improvement in performance of 43 million to 1 is the mathematical technique that is used to optimally assign resources in a hierarchical memory system such as HHMM that I discussed earlier.

It is a simple pattern of sound frequencies and it undoubtedly enjoys significant redundancy in our neocortex. We could fill up our entire neocortex with repeated patterns of the [E] phoneme. There is a limit, however, to useful redundancy, and a common pattern such as this clearly has reached it. There is a mathematical solution to this optimization problem called linear programming, which solves for the best possible allocation of limited resources (in this case, a limited number of pattern recognizers) that would represent all of the cases on which the system has trained. Linear programming is designed for systems with one-dimensional inputs, which is another reason why it is optimal to represent the input to each pattern recognition module as a linear string of inputs. We can use this mathematical approach in a software system, and though an actual brain is further constrained by the physical connections it has available that it can adapt between pattern recognizers, the method is nonetheless similar.

Our systems from the 1980s and 1990s automatically pruned connections with connection weights below a certain level and also allowed for making new connections to better model the training data and to learn on the fly. A key requirement, I believe, is to allow for the system to flexibly create its own topologies based on the patterns it is exposed to while learning. We can use the mathematical technique of linear programming to optimally assign connections to new pattern recognizers. Our digital brain will also accommodate substantial redundancy of each pattern, especially ones that occur frequently. This allows for robust recognition of common patterns and is also one of the key methods to achieving invariant recognition of different forms of a pattern. We will, however, need rules for how much redundancy to permit, as we don’t want to use up excessive amounts of memory on very common low-level patterns.

pages: 544 words: 168,076

Red Plenty by Francis Spufford

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

Kantorovich’s first step was to realise that he had a criterion for choosing between the infinite solutions, in the knowledge that a + b + c + d, the total amount of work done by the machines, was to be minimised for the production of the target output of plywood in the Plywood Trust’s plan. Or you could turn the problem around, and see yourself as maximising the output target. For a textbook explanation of linear programming, adapted to American business-school students, see Saul I. Gass, Linear Programming: Methods and Applications (NewYork: McGraw-Hill, 4th edn, 1975). 7 Skyscrapers in Manhattan, and the promise of more in Moscow: for the promise of the Stalinist future, see Lev Kopelev, The Education of a True Believer (New York, 1980), quoted in Fitzpatrick, Everyday Stalinism, p. 18; for specifically architectural visions of the future, see the website Unrealised Moscow, www.muar.ru/ve/2003/moscow/index_e. htm, a gathering of the kind of images whose hypnagogic power, taken collectively, is horribly well realised in Jack Womack, Let’s Put the Future Behind Us (New York: Atlantic Monthly Press, 1996). 8 An extra 3% year after year, compounded: in an economy that consumed all the goods it produced, the 3% of extra output Kantorovich anticipates here would only have contributed a simple boost to production, not a compounding addition to the growth rate.

‘Naturally,’ Boyarskii continued with awkward politeness, ‘I don’t say a word against the strictly mathematical part of your work. I’m sure we’re all aware that a greater degree of quantitative analysis is essential to the refinement of our planning; and you have provided tools which, in limited areas, can clearly be of great assistance. In the same way, it’s a matter of pride for all of us, I’m sure, that you should have independently originated the principles of, of –’ ‘– linear programming –’ ‘Thank you, linear programming, here in the Soviet Union, before it was discovered by scientists in the imperialist countries. Yet economics is not a science of quantity alone, is it? It is pre-eminently a science of quality, the science of quality, in which the meaning of economic phenomena, not just their magnitude, is revealed; and revealed how? Of course, by the rigorous application of Marxism–Leninism.

Kantorovich’s first step was to realise that he had a criterion for choosing between the infinite solutions, in the knowledge that a + b + c + d, the total amount of work done by the machines, was to be minimised for the production of the target output of plywood in the Plywood Trust’s plan. Or you could turn the problem around, and see yourself as maximising the output target. For a textbook explanation of linear programming, adapted to American business-school students, see Saul I. Gass, Linear Programming: Methods and Applications (NewYork: McGraw-Hill, 4th edn, 1975). 7 Skyscrapers in Manhattan, and the promise of more in Moscow: for the promise of the Stalinist future, see Lev Kopelev, The Education of a True Believer (New York, 1980), quoted in Fitzpatrick, Everyday Stalinism, p. 18; for specifically architectural visions of the future, see the website Unrealised Moscow, www.muar.ru/ve/2003/moscow/index_e. htm, a gathering of the kind of images whose hypnagogic power, taken collectively, is horribly well realised in Jack Womack, Let’s Put tuture Behind Us (New York: Atlantic Monthly Press, 1996). 8 An extra 3% year after year, compounded: in an economy that consumed all the goods it produced, the 3% of extra output Kantorovich anticipates here would only have contributed a simple boost to production, not a compounding addition to the growth rate.

pages: 518 words: 107,836

How Not to Network a Nation: The Uneasy History of the Soviet Internet (Information Policy) by Benjamin Peters

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

Adopted by Aleksei Kosygin and implemented incrementally and partially by a hesitant new general secretary, Leonid Brezhnev, the Liberman reforms nonetheless correlated with increased national production during the next five-year plan (1965–1970), even though they also met fierce resistance from bureaucrats and economic planners, especially in Ministry of Finance, who were set on disrupting the raw materials supply chain and decrying the wage-differentiating reforms as a form of class warfare.24 By the early 1970s, Brezhnev continued to resist the orthodox economic planners but also abandoned the Liberman reforms. During the early 1960s, a third camp of thought about national economic reform began to coalesce. The economic cyberneticists championed what might be called planometrics, or a combination and application of econometric mathematical tools that included input-output models (not dissimilar from planned supply and demand), linear programming, and sophisticated statistics to the problem of economic planning. Like the liberal reforms, the economic mathematicians, cyberneticists, and econometrists comprising this loose camp conceived of the command economy as a vast information-coordination problem. Unlike the liberal economists, however, the cyberneticists were less concerned with reducing the complexity of the economy understood as an information system to a single golden index.

Suppose that farmers—or after Stalin in the 1930s, the managers of a collectivized farm—distribute crops across their fields and that the farmers know the cost of fertilizer and pesticide, the cost of planting, and the selling price of wheat and barley. A linear programmer can determine how much land they should devote to each to optimize their annual yield. Linear modeling—now evolved into the field of linear programming—allows the farm managers to calculate in matrix form the maximum revenue, or profit, that they can expect from their available resources and to know how best to distribute their crops (for example, how much barley and how much wheat to plant).28 Figure 2.1 Leonid Kantorovich Economists worldwide recognized the promise of this profit-by-planning model, especially after Kantorovich in 1939 and George Dantzig in 1947 separately took pains to propose methods that could scale to much larger problem sets.

To this day, the label of economic cybernetics lies exclusively within the former Soviet Union and its area of influence. The scaling successes of economic cybernetics in the late 1950s suggested to Anatoly Kitov, Vasily Nemchinov, Viktor Glushkov, and others that economic planning methods should be applied nationally—perhaps even, as Kitov advised, in a real-time network of computers. The promise of the scalability of the linear programming and computational methods bolstered the political appeal of the supposedly apolitical planometric calculation. The next step with a scalable computational tool is to scale it all the way up, and that would require a communication infrastructure—computer networks—for processing the nation’s economic coordination problems. Because computational methods do scale, the economic cyberneticists enthused that maybe the principal question for economic reform (who should control the command economy and how?)

pages: 523 words: 143,139

Algorithms to Live By: The Computer Science of Human Decisions by Brian Christian, Tom Griffiths

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

It’s a kind of cousin to the set cover problem, where instead of seeking the smallest number of fire stations whose coverage includes everyone, the goal is to find the smallest number of people who are connected to everyone else. solving the continuous versions of these problems: There are certain kinds of continuous optimization problems that can be solved in polynomial time; the most prominent example is linear programming problems, in which both the metric to be optimized and the constraints on the solution can be expressed as a linear function of the variables involved. See Khachiyan, “Polynomial Algorithms in Linear Programming,” and Karmarkar, “A New Polynomial-Time Algorithm for Linear Programming.” However, continuous optimization is no panacea: there are also classes of continuous optimization problems that are intractable. For example, see Pardalos and Schnitger, “Checking Local Optimality in Constrained Quadratic Programming is NP-hard.” at most twice as many invitations: Khot and Regev, “Vertex Cover Might Be Hard to Approximate to Within 2-ε.”

The idea itself is considered to have emerged in the work of Michael Held (of IBM) and Richard Karp (of UC Berkeley) on the traveling salesman problem in 1970—see Held and Karp, “The Traveling-Salesman Problem and Minimum Spanning Trees,” and Held and Karp, “The Traveling-Salesman Problem and Minimum Spanning Trees: Part II.” Earlier precursors, however, also exist—for instance, Lorie and Savage, “Three Problems in Rationing Capital”; Everett III, “Generalized Lagrange Multiplier Method”; and Gilmore and Gomory, “A Linear Programming Approach to the Cutting Stock Problem, Part II.” For an overview and reflections see Fisher, “The Lagrangian Relaxation Method for Solving Integer Programming Problems,” as well as Geoffrion, “Lagrangian Relaxation for Integer Programming.” “If you end up with fractional games”: Michael Trick, personal interview, November 26, 2013. “make-believe can never be reconciled”: Christopher Booker, “What Happens When the Great Fantasies, Like Wind Power or European Union, Collide with Reality?

Journal of the American Statistical Association 61 (1966): 35–75. Gilboa, Itzhak, and Eitan Zemel. “Nash and Correlated Equilibria: Some Complexity Considerations.” Games and Economic Behavior 1, no. 1 (1989): 80–93. Gillispie, Charles Coulston. Pierre-Simon Laplace, 1749–1827: A Life in Exact Science. Princeton, NJ: Princeton University Press, 2000. Gilmore, Paul C., and Ralph E. Gomory. “A Linear Programming Approach to the Cutting Stock Problem, Part II.” Operations Research 11, no. 6 (1963): 863–888. Gilovich, Thomas. How We Know What Isn’t So. New York: Simon & Schuster, 2008. Ginsberg, Allen. Howl and Other Poems. San Francisco: City Lights Books, 1956. Gittins, John C. “Bandit Processes and Dynamic Allocation Indices.” Journal of the Royal Statistical Society, Series B (Methodological) 41 (1979): 148–177.

pages: 719 words: 181,090

Site Reliability Engineering by Betsy Beyer, Chris Jones, Jennifer Petoff, Niall Richard Murphy

Auxon collects this information either via a user configuration language or via a programmatic API, thus translating human intent into machine-parseable constraints. Requirements can be prioritized, a feature that’s useful if resources are insufficient to meet all requirements, and therefore trade-offs must be made. These requirements—the intent—are ultimately represented internally as a giant mixed-integer or linear program. Auxon solves the linear program, and uses the resultant bin packing solution to formulate an allocation plan for resources. Figure 18-1 and the explanations that follow it outline Auxon’s major components. Figure 18-1. The major components of Auxon Performance Data describes how a service scales: for every unit of demand X in cluster Y, how many units of dependency Z are used? This scaling data may be derived in a number of ways depending on the maturity of the service in question.

Resource Supply provides data about the availability of base-level, fundamental resources: for example, the number of machines expected to be available for use at a particular point in the future. In linear program terminology, the resource supply acts as an upper bound that limits how services can grow and where services can be placed. Ultimately, we want to make the best use of this resource supply as the intent-based description of the combined group of services allows. Resource Pricing provides data about how much base-level, fundamental resources cost. For instance, the cost of machines may vary globally based upon the space/power charges of a given facility. In linear program terminology, the prices inform the overall calculated costs, which act as the objective that we want to minimize. Intent Config is the key to how intent-based information is fed to Auxon.

It applies light sanity checking to the configuration, and is designed to act as the gateway between the human-configurable intent definition and the machine-parseable optimization request. Auxon Solver is the brain of the tool. It formulates the giant mixed-integer or linear program based upon the optimization request received from the Configuration Language Engine. It is designed to be very scalable, which allows the solver to run in parallel upon hundreds or even thousands of machines running within Google’s clusters. In addition to mixed-integer linear programming toolkits, there are also components within the Auxon Solver that handle tasks such as scheduling, managing a pool of workers, and descending decision trees. Allocation Plan is the output of the Auxon Solver. It prescribes which resources should be allocated to which services in what locations.

pages: 461 words: 128,421

The Myth of the Rational Market: A History of Risk, Reward, and Delusion on Wall Street by Justin Fox

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

His statistics professor at Chicago was Leonard “Jimmie” Savage, a veteran of the wartime Statistical Research Group at Columbia, who was described by his sometime collaborator Milton Friedman as “one of the few people I have met whom I would unhesitatingly call a genius.”11 He studied the mathematics of tradeoffs with Tjalling Koopmans, a Dutch physicist-turned-economist and future Nobelist. During the war, Koopmans had developed the technique later dubbed “linear programming” to determine the most efficient use of merchant ships crisscrossing the Atlantic.12 Markowitz’s adviser, macroeconomics professor, and guide to the ideas of von Neumann and Morgenstern was Jacob Marschak. “When I first read the von Neumann axioms, I was not convinced,” Markowitz recalled. “Somebody at Cowles said, ‘Well, you ought to read Marschak’s version of the von Neumann axioms.’ I read Marschak’s version, and I was convinced.”

Markowitz’s translation: “It said that the riskiness of the portfolio had to do not only with the riskiness of the individual securities therein, but also to the extent that they moved up and down together.” From there, Markowitz was a few equations away from separating an “efficient” portfolio—one that delivered the maximum potential reward for a given amount of risk—from an inefficient one. The terminology, and the math, came straight from his linear programming class with Tjalling Koopmans.16 Markowitz had not only a dissertation topic but an idea that would transform investing. Before he could get his degree, though, he had to put up with an unexpected razzing from Friedman at his dissertation defense. “Two minutes into the defense, Friedman says, ‘Well, I don’t find any mistake in the mathematics, but this isn’t a dissertation in economics and we can’t give you a Ph.D. in economics.’”

Markowitz got his doctorate, and Friedman subsequently told him he was never in any danger of not getting it. But half a century later, Friedman stood by what he had said. “Every statement there is correct. It’s not economics; it’s not mathematics; it’s not business. It is something different. It’s finance.” THERE WASN’T A BIG MARKET for this new, quantitative version of finance in 1952. After finishing up at Chicago, Markowitz took a job doing linear programming at RAND—a think tank set up by the air force after the war that threw together mathematicians (von Neumann was a regular), physicists, economists, political scientists, and computer programmers to study the big questions of war and diplomacy. His portfolio theory article attracted the attention, though, of the same Merrill Foundation that had bankrolled Holbrook Working’s research. Together with what was now called the Cowles Foundation—which Alfred Cowles had moved to Yale in the summer of 1955—the Merrill Foundation paid Markowitz to spend the 1955–56 academic year at Yale expanding his dissertation into a book.

pages: 194 words: 36,223

Smart and Gets Things Done: Joel Spolsky's Concise Guide to Finding the Best Technical Talent by Joel Spolsky

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

Build your own community* “Build your own community” comes with a little asterisk that means “hard,” like the famous math problem that George Dantzig solved because he came into class too late to hear that it was supposed to be unsolvable.1 You can probably come up with your own ideas, too. I’m just going to talk about three that worked for me. To the Mountain, Jeeves! Think about where the people you want to hire are hanging out. What conferences do they go to? Where do they live? What organizations do they belong to? What websites do they read? 1. Donald J. Albers and Constance Reid, “An Interview of George B. Dantzig: The Father of Linear Programming,” College Mathematics Journal 17, no. 4 (1986), pp. 293–314. 23 24 Smart and Gets Things Done Instead of casting a wide net with a job search on Monster.com, use the Joel on Software job board (jobs.joelonsoftware.com) and limit your search to the smart developers who read my website. Go to the really interesting tech conferences. Great Mac developers will be at Apple’s WWDC. Great Windows programmers will be at Microsoft’s PDC.

See also developers; Mac developers; open-source programmers; Windows programmers attitude of people they meet at interview, 52–53 avoiding preconceived notions about, 101–102 benefits of quiet working space for, 163–165 bottom line in hiring, 120 different types of contributors, 127–128 effect of firing underperformers on morale, 129–130 handling underperformers, 130–131 hiring cheap vs. quality, 3–4 hiring right ones for the job, 93–97 Index 179 importance of identifying with company to, 60–63 interviewing about recent project, 102–103 measuring productivity of, 5–10 more are not always better, 11 motivating to identify with company goals, 147–150 putting yourself into the candidate’s head, 47–48 questioning a candidate on code writing, 111–113 screening for diversity in thinking about projects, 75–76 screening for experience in difficult technologies, 74–75 some don’t pull their weight, 128–129 things they don’t care about, 63–64 toys as great recruiting tools for, 50 treating them like Samurai, 118–119 treatment of inside the organization, 51–52 typical plan for interviewing, 100–101 understanding of basic programming concepts, 107–108 using cool new technologies unnecessarily, 59–60 programming-intensive course (CS323), taught at Yale, 5 projects, letting top recruits pick their own, 58–59 Q Quiz Show Interviewer, 99 R recruiting identifying idealistic aspects of company for, 60–63 importance of interesting projects to, 57–58 importance of people applicants meet at interview, 52–53 180 Index recursion and pointers, programmers understanding of, 108–111 importance of understanding, see recursion Reid, Constance and Donald J. Albers, An Interview of George B. Dantzig: The Father of Linear Programming by, 23 resumes additional screening for, 77–78 criteria for sorting, 68–76 evaluating for technology experience, 78–81 extracurricular activities as clue to intelligence, 72–73 Fog Creek rules for screening, 67–68 importance of custom cover letters to, 70–71 passion as important criteria for programmers, 69–70 scoring by English skills, 71–72 selectivity as criteria for programmers, 73 Reselman, Bob, blog post about Microsoft interview, 119 rubber rooms, use of to neutralize bad employees, 130–131 Ruby on Rails, use of by 37signals for applications, 61 S Santa Teresa Laboratory (IBM), 44 schedules, importance of having up-to-date, 160–161 selectivity, as part of criteria for programmers, 73 Seven Samurai, Akira Kurosawa movie, 118 shipping build, 154–155 software companies, bible on how to run, 42 software company, creation of Fog Creek Software, 2 Index 181 software developers importance of interesting projects to, 57–58 social life of, 51–57 software developers.

pages: 415 words: 125,089

Against the Gods: The Remarkable Story of Risk by Peter L. Bernstein

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

A self-styled "nerd" as a student, he was working in what was then the relatively young field of linear programming. Linear programming, which happened to be an innovation to which John von Neumann had made significant contributions, is a means of developing mathematical models for minimizing costs while holding outputs constant, or for maximizing outputs while holding costs constant. The technique is essential for dealing with problems like those faced by an airline that aims to keep a limited number of aircraft as busy as possible while flying to as many destinations as possible. One day, while waiting to see his professor to discuss a topic for his doctoral dissertation, Markowitz struck up a conversation with a stock broker sharing the waiting room who urged him to apply linear programming to the problems investors face in the stock market.

Markowitz reserved the term "efficient" for portfolios that combine the best holdings at the price with the least of the variance"optimization" is the technical word. The approach combines two cliches that investors learn early in the game: nothing ventured, nothing gained, but don't put all your eggs in one basket. It is important to recognize that there is no one efficient portfolio that is more efficient than all others. Thanks to linear programing, Markowitz's method produces a menu of efficient portfolios. Like any menu, this one has two sides: what you want is on one side and the cost of what you want is on the other. The higher the expected return, the greater the risks involved. But each efficient portfolio on the menu will have the highest expected return for any given level of risk or the lowest level of risk for any expected return.

Commodity Trading Advisors: Risk, Performance Analysis, and Selection by Greg N. Gregoriou, Vassilios Karavas, François-Serge Lhabitant, Fabrice Douglas Rouah

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

The second orientation yields an input-oriented measure for the maximum proportional reduction in inputs that can be achieved for the given level of outputs of the DMU. Following Banker, Charnes, and Cooper (BCC) (1984) we can measure the output-oriented efficiency of the ith DMU by solving this linear programming problem:17 Max fi Subject to N ∑ λ j yrj j =1 N ∑ λ j xsj j =1 N ∑ λj ≥ φi yri r = 1, 2, . . . , m ≤ x si s = 1, 2, . . . , n (5.1) =1 j =1 λj ≥ 0 j = 1, 2, . . . , N For an efficient DMU fi = 1, whereas for an inefficient DMU fi > 1. On the other hand, an input-oriented measure of efficiency can be obtained for the ith DMU by solving the linear programming problem: 16The concept of efficiency used here is that of technical efficiency. It is used in the context of an expanded efficient frontier with n variables across n dimensions, rather than just the two familiar mean and variance dimensions. 17While the Charnes, Cooper, and Rhodes, (1978) model assumes constant returns to scale, the model proposed by Banker, Charnes, and Cooper (1984) allows for variable returns to scale.

A best-performance frontier charts the maximum or minimum level of output (input) produced for any assumed level of input (output), where outputs represent the degree to which the CTA’s goal has been achieved. How the inputs and outputs are used in the efficiency analysis are essential because they establish the grounds on which the efficiency of the fund is calculated. The most extensively used DEA technique to measure efficiency takes the weighted sum of outputs and divides it by the weighted sum of inputs (Golany and Roll, 1994). In its simplest form, DEA calculates weights from a linear program that maximizes relative efficiency with a set 2Pareto optimality means the best that can be attained without putting any group at a disadvantage. In other words, a group of funds becomes better off if an individual fund becomes better off and none becomes worse off. Simple and Cross-Efficiency of CTAs Using Data Envelopment Analysis 133 of minimal weight constraints.3 Charnes, Cooper, and Rhodes (1978) proposed reducing the multiple-input, multiple-output model to a ratio with a single virtual input and a single virtual output.

Therefore, since CTAs vary their leverage at different times to magnify returns, we employ the BCC model (varying returns to scale). Cross-Efficiency The cross-evaluation, or cross-efficiency, model was first seen in Sexton, Silkman, and Hogan (1986) and later in Oral, Ketani, and Lang (1991), Doyle and Green (1994), and Thanassoulis, Boussofiane, and Dyson (1995). It establishes the ranking procedure and computes the efficiency score of each CTA n times using optimal weights measured by the linear programs. A cross-evaluation matrix is a square matrix of dimension equal to the number of CTAs in the analysis. The efficiency of CTA j is computed with the optimal weights for CTA k. The higher the values in column k, the more likely that CTA k is efficient using superior operating techniques. Therefore, calculating the mean of each column will provide the peer appraisal score of each CTA. The cross-efficiency method is superior to the simple efficiency method because the former uses internally generated weights as opposed to forcing predetermined weights.

From Airline Reservations to Sonic the Hedgehog: A History of the Software Industry by Martin Campbell-Kelly

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

Nonetheless, Kubie recognized that the market for technical applications was somewhat limited, so he began to broaden the firm’s base by tendering for business applications and systems software. The portfolio of its early projects was impressively diverse: “Among these were oil reservoir simulation, nuclear reactor design, structural design, space technology, chemical engineering, supersonic air flow, circuit and logical design of complex electronic equipment, linear programming, inventory control, sales analysis, cost analysis, payroll, trust accounting, statistical analysis, information storage and retrieval, cataloguing, traffic analysis, production planning, insurance accounting, computer simulation, computer operating systems, and development of interpretive, compiler, and assembly programming languages.”71 Kubie estimated that “About 50–60 percent of our development work is in the business application area, 20–30 percent in [systems] software, and the remainder in scientific applications.”72 By 1959, CUC had a staff of 59 and had opened a branch office in Washington.

This had a further benefit for IBM: It would make it much harder for independent software firms to compete, because they generally did not have access to leasing funds. The situation with regard to Type II application programs was much more complex, mainly because of the hazy distinction between a software package and a software product. Some application packages—especially the more scientific and mathematical ones, such as linear programming and project-management packages—presented little difficulty. These were already self-contained packages that required negligible support and were therefore easy to unbundle. However, most of the industry-specific programs had long been supplied as illustrative examples rather than finished products, and they usually required extensive customization by IBM’s systems engineers. (For example, IBM’s PARS airline reservation system, though described as a package, was more exactly a framework for application development that cost about \$5 million to customize.46) Another complication was that some bundled application programs were legitimately being supplied as turnkey products—products with which a complete package of software and hardware was supplied for a dedicated task.

The Shaping of the Software Products Industry 131 Time-Sharing Services A recurring issue in the software industry has been the charging model— for example, whether software should be supplied as a product that the user owns absolutely, whether the user should be granted a license, or whether the user should be charged on a per-use basis. Most often the middle course of a perpetual but revocable license was favored by software vendors because it represented the best compromise between recovery of development costs and control of the product’s use. Time-sharing services offered a per-use charging mechanism. Time-sharing services were mostly used by engineers and scientists as “super calculators” for stress analysis, linear programming, matrix analysis, and other mathematical applications. Financial workers also made use of time-sharing services—particularly financial analysis packages, which were the real forerunners of spreadsheet programs for personal computers.17 The program catalogs of the major time-sharing companies contained hundreds of programs. Though some of these were developed by their salespeople for customers, most were developed by third parties.

pages: 305 words: 89,103

Scarcity: The True Cost of Not Having Enough by Sendhil Mullainathan

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

In the last two decades, research has shown that people’s psychological biases affect decisions as consequential as their retirement or their health and mortality. needing to navigate a world that is computationally more complex: The notion of computational complexity here can be understood by contrasting linear programming to integer programming. In linear programming, items can be infinitely subdivided—the logical extension of granularity. In integer programming, items must be packed in fixed units—the logical extension of bulkiness. Computer scientists have shown in a precise mathematical sense that integer programming is inherently harder than linear programming. A detailed introduction to these ideas can be found in Alexander Schrijver, Theory of Linear and Integer Programming (West Sussex, England: John Wiley & Sons, 1998). As Henry David Thoreau observed: Thoreau himself took a different lesson from this observation.

pages: 88 words: 25,047

The Mathematics of Love: Patterns, Proofs, and the Search for the Ultimate Equation by Hannah Fry

And let’s face it, we’ve all got lives to be getting on with. 13. Although using a Monte Carlo computer simulation would be much more sensible. Monte Carlo methods offer a way of sampling without having to check every possible combination. 14. Examples include the simulated annealing algorithm and the Nelder-Mead simplex procedure, which both provide efficient ways to search for optimal solutions. 15. The CPLEX solver employs an algorithm from linear programming and uses the happiness scores to create a feasible region in solution space. It skips over anything on the inside of this convex polytope by assuming the optimal result will lie on the surface of the simplex. 16. Known as the Specific Affect Coding System, or ‘SPAFF’ for short. 17. A full overview of the scoring system can be found in Coan and Gottman, ‘The Specific Affect Coding System (SPAFF)’ (1995). 18.

pages: 544 words: 96,029

Practical C Programming, 3rd Edition by Steve Oualline

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

Exercise 5-6: Write a program that takes an integer as the number of minutes, and outputs the total hours and minutes (90 minutes = 1 hour 30 minutes). Chapter 6. Decision and Control Statements Once a decision was made, I did not worry about it afterward. —Harry Truman Calculations and expressions are only a small part of computer programming. Decision and control statements are needed. They specify the order in which statements are to be executed. So far, we have constructed linear programs, that is, programs that execute in a straight line, one statement after another. In this chapter, we will see how to change the control flow of a program with branching statements and looping statements. Branching statements cause one section of code to be executed or not executed, depending on a conditional clause. Looping statements are used to repeat a section of code a number of times or until some condition occurs.

pages: 287 words: 86,919

Protocol: how control exists after decentralization by Alexander R. Galloway

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

Chapter 1 32 bureaucracies and vertical hierarchies toward a broad network of autonomous social actors. As Branden Hookway writes: “The shift is occurring across the spectrum of information technologies as we move from models of the global application of intelligence, with their universality and frictionless dispersal, to one of local applications, where intelligence is site-speciﬁc and ﬂuid.”5 Computer scientists reference this historical shift when they describe the change from linear programming to object-oriented programming, the latter a less centralized and more modular way of writing code. This shift toward distribution has also been documented in such diverse texts as those of sociologist Manuel Castells, American Deleuzian Hakim Bey, and the Italian “autonomist” political movement of the 1970s. Even harsh critics of this shift, such as Nick Dyer-Witheford, surely admit that the shift is taking place.

Wiener’s interest in “possibility” and “distribution,” inspired by Gibbs’s work connecting the ﬁelds of physics and statistics, is also proto-protocological (pp. 12, 8). 88. The coinage “robot” is attributed to the writer Karel Čapek and derives from a Czech word meaning “serf.” For more on robots and other automata, see Julien Offray de la Mettrie, Power 107 from being primarily linear calculation machines to being clusters of parallel, distributed submachines. In computer science, this shift is characterized by the change from “procedural” (or linear) programming to so-called object-oriented programming. In procedural programming, one inputs data and then operates on that data in a linear manner. Loops may occur, but in general a series of commands are read, interpreted, and executed as a consecutive chain of events. Object-oriented programming, on the other hand, treats all code as a series of simultaneously generated entities, with each entity possessing its own qualities and actions.

pages: 313 words: 34,042

Tools for Computational Finance by Rüdiger Seydel

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

Kloeden, J. Ombach: From Elementary Probability to Stochastic Diﬀerential Equations with MAPLE. Springer (2001). M. Dai: A closed-form solution for perpetual American ﬂoating strike lookback options. J. Computational Finance 4,2 (2000) 63-68. R.-A. Dana, M. Jeanblanc: Financial Markets in Continuous Time. Springer, Berlin (2003). M.A.H. Dempster, J.P. Hutton: Pricing American stock options by linear programming. Mathematical Finance 9 (1999) 229–254. M.A.H. Dempster, J.P. Hutton, D.G. Richards: LP valuation of exotic American options exploiting structure. J. Computational Finance 2,1 (1998) 61-84. H.-P. Deutsch: Derivatives and Internal Models. Palgrave, Houndmills (2002). L. Devroye: Non–Uniform Random Variate Generation. Springer, New York (1986). R. Dieci, G.-I. Bischi, L. Gardini: From bi-stability to chaotic oscillations in a macroeconomic model.

.: A Course in Credibility Theory and its Applications Aoki, M.: State Space Modeling of Time Series Carleson, L.; Gamelin, T. W.: Complex Dynamics Arnold, V. I.: Lectures on Partial Differential Equations Cecil, T. E.: Lie Sphere Geometry: With Applications of Submanifolds Audin, M.: Geometry Chae, S. B.: Lebesgue Integration Aupetit, B.: A Primer on Spectral Theory Chandrasekharan, K.: Classical Fourier Transform Bachem, A.; Kern, W.: Linear Programming Duality Bachmann, G.; Narici, L.; Beckenstein, E.: Fourier and Wavelet Analysis Borkar, V. S.: Probability Theory Charlap, L. S.: Bieberbach Groups and Flat Manifolds Badescu, L.: Algebraic Surfaces Chern, S.: Complex Manifolds without Potential Theory Balakrishnan, R.; Ranganathan, K.: A Textbook of Graph Theory Chorin, A. J.; Marsden, J. E.: Mathematical Introduction to Fluid Mechanics Balser, W.: Formal Power Series and Linear Systems of Meromorphic Ordinary Differential Equations Cohn, H.: A Classical Invitation to Algebraic Numbers and Class Fields Bapat, R.B.: Linear Algebra and Linear Models Curtis, M.

How I Became a Quant: Insights From 25 of Wall Street's Elite by Richard R. Lindsey, Barry Schachter

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

The regulatory authorities laid down a lattice of investment restrictions in an attempt to ensure that financial firms, such as the trust company, would be solvent and able to redeem their paper in a timely manner. The trust company met these restrictions with a set of manual heuristics, ensuring compliance by adding cushions to most, if not all, such restrictions. Could a computer allocate the funds in a more efficient manner? This seemed to be an ideal opportunity for a linear programming application: Maximize expected return while meeting all regulatory restrictions. The results demonstrated that manual adherence to each restriction with cushions was expensive in terms of opportunity costs. The appropriate matching of liabilities with asset classes was also a process worth exploring. The trust company had an airline pension fund as a client. A significant investment in that portfolio was real estate in Florida.

Things ended badly at Gordon Capital due to deals it was my privilege to unravel. The essence of these deals (as is the case with so many supposed arbitrages) was the sale of insurance. Gordon Capital didn’t realize it at the time, but it was short billions of dollars of Government of Canada bonds and long a portfolio of high-quality bank paper that had been carefully constructed by an advisor who used a linear program JWPR007-Lindsey May 7, 2007 17:9 Julian Shaw 231 to match the coupon flows. (The advisor has since been indicted on unrelated charges.) To use an Australian expression, this was “a nice little earner” until bank credit spreads deteriorated and Gordon Capital wanted to reduce its exposure. To the firm’s surprise, it could not do so without sustaining a huge mark-to-market loss, and the whole scheme was blown open.

pages: 409 words: 118,448

An Extraordinary Time: The End of the Postwar Boom and the Return of the Ordinary Economy by Marc Levinson

In most countries, with the notable exception of West Germany during the 1950s, economic planning was very much in vogue in the postwar era. To some extent, planning was unavoidable: where foreign currency to buy imports was scarce at the war’s end, someone had to decide whether importing fuel or food was more essential. But the planning bureaucracies that developed in the late 1940s were meant to be anything but temporary. Skilled in new quantitative tools such as linear programming and equipped with the techniques perfected by operations researchers to plot bombing runs, the planners claimed to know which industries, if properly fostered, could do the most for economic growth. Following the advice of economists, France’s government laid out grands plans for new auto plants and steel mills. In Japan, the Ministry of International Trade and Industry, the awesome bureaucracy known as MITI, wielded life-and-death power by controlling individual companies’ imports and exports, their investments in new factories, and their licensing of foreign patents.17 If planners could figure out how to manage key industries, why not entire economies?

Schiller offered an alternative perspective. The economy, he insisted, was “a rational whole.” The government’s job was not to run it, but to use its tax and spending powers to fine-tune it for optimal performance. This would be accomplished with techniques such as input-output analysis, which showed how a million marks of government spending on highways would trickle through the economy, and linear programming, which could reveal which type of tax cut might create the most jobs. Highly trained experts conversant with new methods of statistical analysis would evaluate the data and make the critical decisions. In 1956, Schiller put forth his ideas in legislation requiring the government to maintain full employment and steady economic growth while keeping prices stable. He called this wondrous combination the “magic triangle.”

pages: 252 words: 73,131

The Inner Lives of Markets: How People Shape Them—And They Shape Us by Tim Sullivan

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

Shi had been a devoted attendee of the public meetings to discuss school assignment reform, chatting with parents and activists to better understand the sources of dissatisfaction with the current system and what sorts of changes would be palatable to them. Shi’s initial proposal involved an attempt to, in his words, “define equality of access rigorously.” Based on his rigorous definition, he devised a solution that involved linear programming methods (a branch of mathematical optimization) to minimize the distance traveled by Boston students subject to an equitable access constraint. If this is incomprehensible to you, the committee shared your reaction. One school committee member pulled Shi aside later and explained that, if you want something to actually get implemented, you had better be able to explain it to a fifth grader.

pages: 556 words: 46,885

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

Solving a network optimization problem for a system as large as a national railway is a challenging task. Introduction and Summary 11 The computational problems involved in the construction of counterfactual networks have never been fully addressed. While Fogel refers to the use of linear programming in network optimization, he acknowledges that he has not actually implemented the technique (Fogel 1964, p. 26). The method by which his counterfactual canal system was derived is not fully explained in the Appendix, and his estimate of its performance is based on guesswork (p. 38). Network optimization cannot be eVected by linear programming, as Fogel mistakenly suggests. Making a connection between two locations involves a binary decision: the two locations are either connected or they are not. Network optimization is therefore an integer programming problem, and problems of this kind encounter combinatorial explosion: the number of possible network structures increases at an accelerating rate as the number of locations to be served rises.

pages: 313 words: 92,907

Green Metropolis: Why Living Smaller, Living Closer, and Driving Less Are Thekeys to Sustainability by David Owen

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

Individual heating and air-conditioning units would be unnecessary because the city itself would be climate-controlled. The domed roof would be made of triangular glass panels and would owe a design debt to R. Buckminster Fuller. “Most houses in Compact City would have two floors in order to conserve base area,” the authors wrote, with the self-assurance of professionally logical men who are certain they have thought of everything (Dantzig was an inventor of linear programming). “Design of both the interior and exterior of these houses would vary according to the preferences of the residents. The ringway would provide access to the rear of the upper floor of a house. To facilitate home deliveries by electric-battery-powered trucks from the ringway, it would probably be convenient to have the upper floor of a house built to open directly onto the ringway. The lower floor, however, could be offset 10 feet from the ringway 30 feet below, creating an appearance of openness and spaciousness there.

pages: 465 words: 109,653

Free Ride by Robert Levine

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

In December 2009, the House Judiciary Committee held a hearing on online sports piracy with testimony from executives from the Ultimate Fighting Championship and Major League Baseball, which has built a thriving business streaming games over the Internet itself. “Whatever features may have in the past distinguished live sports from other forms of content in terms of its susceptibility to online infringement are being rendered increasingly irrelevant by new technological means for misappropriating linear programming,” said ESPN’s executive vice president Ed Durso. “And the quality of these sites is improving to the point that programming can be streamed in a form that is almost on par with that accessed through legitimate distribution channels.”24 Live sports piracy isn’t a big problem on computers, since it’s not much fun to watch the big game on a small screen. But ESPN is already concerned. “This could become a bigger issue as technology advances and a better viewing environment emerges, which is what we’re going to see with widgets on TV and more robust Internet connectivity to big screens,” Durso says.

pages: 366 words: 107,145

Fuller Memorandum by Stross, Charles

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

"You must understand, previous models all seem to have looked at how possession spreads through a sparse network, like classical epidemiological studies of smallpox transmission, for example. But that's flawed: if you posit an uncontrolled outbreak, then people can see their neighbors, random strangers, being possessed. And that in turn weakens the observer-mediated grid ultrastructure, making it easier for the preta to tunnel into our reality. It's a feedback loop: the more people succumb, the weaker everyone else's resistance becomes. I modeled it using linear programming and the results are, well, they speak for themselves." "And the closer we come to the Transient Weak Anomaly the more outbreaks we're going to see, and the--it contributes to the strength of the TWA?" She looks at him sharply. "Substantially, yes." Dr. Mike shuffles uncomfortably in his chair. "Well, shit." She folds the paper neatly and slides it into her handbag. "And here I was hoping Andy had gotten the wrong end of the stick."

The New Rules of Lifting: Six Basic Moves for Maximum Muscle by Lou Schuler, Alwyn Cosgrove

In fact, some T H E B E S T M U S C L E - B U I L D I N G S YS T E M F O R A L M O S T E V E RY B O DY new research shows that undulating programs develop strength and size faster than linear systems. Consider this study in the May 2002 issue of the Journal of Strength and Conditioning Research: The researchers took a group of college-age lifters with an average of ﬁve years’ training experience. Half did a linear program—three sets of eight reps one month, three sets of six the next, three sets of four the last. The other group did something called “daily undulating periodization” (or DUP, surely among the most unfortunate acronyms in the entire language). They did three sets of eight on Monday, three sets of six on Wednesday, and three sets of four on Friday. So they did the same program for three months, but they never did the same protocol twice in a week.

pages: 467 words: 154,960

Trend Following: How Great Traders Make Millions in Up or Down Markets by Michael W. Covel

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

Donahue III, author of An Introduction to Chaos Theory and Fractal Geometry, addressed a chaotic, nonlinear world: “The world of mathematics has been confined to the linear world for centuries. That is to say, mathematicians and physicists have overlooked dynamical systems as random and unpredictable. The only systems that could be understood in the past were those that were believed to be linear, that is to say, systems that follow predictable patterns and arrangements. Linear equations, linear functions, linear algebra, linear programming, and linear accelerators are all areas that have been understood and mastered by the human race. However, the problem arises that we humans do not live in an even remotely linear world; in fact, our world must indeed be categorized as nonlinear; hence, proportion and linearity is scarce. How may one go about pursuing and understanding a nonlinear system in a world that is confined to the easy, logical linearity of everything?

pages: 561 words: 120,899

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

So how did Tukey resolve his paradoxical use of Bayes’ rule without admitting it? He called it something else. While Brillinger and Wallace called their NBC polling Bayesian, Tukey said it was “borrowing strength.”23 “Anything he did, he’d call something else,” Wallace said, even if it already had a straightforward, well-established name. New names drew attention to ideas, and a colleague counted 50 terms coined by Tukey. Among those that stuck are linear programming, ANOVA, and data analysis. In one article, Mosteller had difficulty talking him out of using musical notation—sharps, flats, and naturals. Another colleague threatened to call him J. W. Cutie for terms such as “saphe cracking,” “quefrency,” and “alanysis.” As Wallace said, “It was not always the best way to win friends and influence people. . . . But when I talked to Tukey, I essentially tried to use his terminology.”

pages: 443 words: 51,804

Handbook of Modeling High-Frequency Data in Finance by Frederi G. Viens, Maria C. Mariani, Ionut Florescu

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

Lo et al. (2000), who used nonparametric kernel regression for technical pattern recognition of a large number of stocks for the period 1962–1996, found that 3.4 Earnings Prediction and Algorithmic Trading 65 technical indicators provide incremental information for investors comparing the unconditional empirical distribution of daily stock returns to the conditional distribution on speciﬁc technical indicators such as head and shoulders. Moody and Saffell (2001) found that a trading system using direct reinforcement learning outperforms a Q-trader for the asset allocation problem between the S&P500 and T-bill. Dempster and Romahi (2002) compared four methods for foreign exchange trading (reinforcement learning, genetic algorithms, Markov chain linear programming, and simple heuristic) and concluded that a combination of technical indicators leads to better performance than using only individual indicators. Dempster and Leemans (2006) reached a similar conclusion using adaptive reinforcement learning. Bates et al. (2003) used Watkin’s Q-learning algorithm to maximize proﬁts; these authors compared order ﬂow and order book data and compared with technical trading rules.

pages: 481 words: 120,693

Plutocrats: The Rise of the New Global Super-Rich and the Fall of Everyone Else by Chrystia Freeland

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

In their incarnation as engineers, they overwhelmingly populate the Communist Party leadership in China, where political nous is a surer path to wealth than filing patents. The Russian oligarchs are a textbook example of crony capitalism, yet six of the original seven earned degrees in math, physics, or finance before becoming natural resource tycoons. Carlos Slim, who studied engineering in college and taught algebra and linear programming as an undergraduate, attributes his fortune to his facility with numbers. So does Steve Schwarzman, who told me he owed his success to his “ability to see patterns that other people don’t see” in large collections of numbers. People inside the super-elite think the rise of the data geeks is just beginning. Elliot Schrage is a member of the tech aristocracy—he was the communications director for Google when it was the hottest company in the Valley and jumped to the same role at Facebook just as it was becoming a behemoth.

pages: 298 words: 43,745

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

In comparison, maximization means trying to attain the highest or maximum result or outcome without regard to cost or expense. Practice of optimization is restricted by the lack of full information and the lack of time to evaluate what information is available (see bounded reality for details). In computer simulation (modeling) of business problems, optimization is achieved usually by using linear programming techniques of operations research (Source: modified from Advertising.com and BusinessDictionary) (see Chapter 7 analytics). Opt-in: refers to an individual giving a company permission to use data collected from or about the individual for a particular reason, such as to market the company’s products and services. See permission marketing (Source: IAB) (see Chapter 6 BAM!). Opt-out: when a company states that it plans to market its products and services to an individual unless the individual asks to be removed from the company’s mailing list (Source: IAB) (see Chapter 6 BAM!).

pages: 607 words: 133,452

Against Intellectual Monopoly by Michele Boldrin, David K. Levine

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

Indeed, in the case of many patentable ideas, the cost of redistribution may well be increasing over time. Certainly the idea of how to build a wheel is much easier to communicate than the idea of how to build an atomic bomb. Basically, inventions range from the trivial, such as the idea of a using a single click to buy an item on the Internet, to the complex, such as Karmarkar’s algorithm for solving linear programming problems. Trivial ideas are cheap to communicate, but, of course, they are also cheap to create. Complex ideas are expensive to create, but they are also difficult to communicate, so they are scarce and will command a substantial premium for a long period of time. In both cases, the cost of producing the ideas and the competitive rents are commensurate, and some ideas will be produced without intellectual monopoly, while perhaps others will not.

pages: 496 words: 174,084

Masterminds of Programming: Conversations With the Creators of Major Programming Languages by Federico Biancuzzi, Shane Warden

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

Peter: Yes and no. Unfortunately to learn some things, you not only have to think about them but you have to sort of practice, so there’s some stuff—you can go to the Internet and you read it and you say, “Oh, yeah, that works.” And then there’s some stuff where there’s just no substitute for years of hard work. So here you are in the middle of some project and you decide you need to understand linear programming to solve your problem; probably what you’ll get from the Internet will not be helpful, and if you have to solve this problem within a week, you’re unlikely to choose a method that requires a lot of work to learn unless you already know about that—even if it were much better. And that happens. What is the role of math in computer science and programming in particular? Peter: My degree is in math, so I’d like to believe that math is fundamental.

pages: 998 words: 211,235

A Beautiful Mind by Sylvia Nasar

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

“So we had to invent or perfect the tools.”15 Mostly, according to Duncan Luce, a psychologist who was a consultant at RAND, “RAND capitalized on ideas that surfaced during the war.”16 These were scientific, or at least systematic, approaches to problems that had been previously considered the exclusive province of men of “experience.” They included such topics as logistics, submarine research, and air defense. Operations research, linear programming, dynamic programming, and systems analysis were all techniques that RAND brought to bear on the problem of “thinking the unthinkable.” Of all the new tools, game theory was far and away the most sophisticated. The spirit of quantification, however, was contagious, and it was at RAND, more than anywhere else, that game theory in particular and mathematical modeling in general entered the mainstream of postwar thinking in economics.

pages: 602 words: 177,874

Thank You for Being Late: An Optimist's Guide to Thriving in the Age of Accelerations by Thomas L. Friedman

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

That was always the job of people. “Technology creates possibilities for new behaviors and experiences and connection,” he added, “but it takes human beings to make the behaviors principled, the experiences meaningful and connections deeper and rooted in shared values and aspirations. Unfortunately, there is no Moore’s law for human progress and moral development. That work is messy and there is no linear program for it. It goes up and down and zigs and zags. It is hard—but there is no other way.” This is especially challenging as cyberspace enters the home. Recall the November 2015 story from Cañon City, Colorado, where more than one hundred students in the local high school were caught trading nude photos and hiding them in secret photo-vault smartphone applications. After taking nude pictures of themselves and sharing them, the students used “ghost apps” on their cell phones to store and hide them.

The Art of Computer Programming: Fundamental Algorithms by Donald E. Knuth

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

As a typical example of a nontrivial algorithm dealing with sparse matrices in this form, we will consider the pivot step operation, which is an important part of algorithms for solving linear equations, for inverting matrices, and for ( 50 10 0 V-30 0 0 0 0 0 20 0 -60 0> 0 0 2.2.6 ARRAYS AND ORTHOGONAL LISTS 303 -1 -f- 1 1 50 2 1 10 -1 -f -1 L '.:!*>.' -1 2 3 20 4 1 -30 4 3 -60 4 4 5 Fig. 14. Representation of matrix A2), with nodes in the format List heads appear at the left and at the top. LEFT UP ROW COL VAL solving linear programming problems by the simplex method. A pivot step is the following matrix transformation: / Pivot row Any other row • • Before pivot step After Any Pivot other Pivot column column column : : \ / : a • ¦ • b • • • c ¦ ¦ ¦ d ••• I/a • ¦ • —c/a pivot step Any other column • b/a • ¦ • d — be/a \ It is assumed that the pivot element, a, is nonzero. For example, a pivot step applied to matrix A2), with the element 10 in row 2 column 1 as pivot, leads to /-5 0 -100 0\ 0.1 0 2 0 0 0 0 0 V 3 0 0 5/ 304 INFORMATION STRUCTURES 2.2.6 Our goal is to design an algorithm that performs this pivot operation on sparse matrices that are represented as in Fig. 14.