linear programming

35 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

asset allocation, call centre, constrained optimization, correlation coefficient, diversification, finite state, fixed income, frictionless, frictionless market, index fund, linear programming, Long Term Capital Management, passive investing, Sharpe ratio, transaction costs, value at risk, Y2K

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

complexity theory, computer age, four colour theorem, index card, John von Neumann, linear programming, NP-complete, p-value, RAND corporation, Richard Feynman, Richard Feynman, traveling salesman, Turing machine

“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

barriers to entry, Brownian motion, call centre, correlation coefficient, inventory management, iterative process, linear programming, meta analysis, meta-analysis, P = NP, pattern recognition, random walk, traveling salesman, value at risk

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?

. ; options design/approach to analysis, data 129–47 dice-rolling examples, probability theory 21–3, 53–5 differentiation 251 discount factors adjusted discount rates 228–9 net present value (NPV) 220–1, 228–9, 231–2 discrete data bar charts 7–12, 13 concepts 7–12, 13, 44–5, 53–5, 72 discrete uniform distribution, concepts 53–5 displays see also presentational approaches data 1–5 Disraeli, Benjamin 1 division notation 280, 282 dynamic programming complex examples 184–7 concepts 179–87 costs 180–82 examples 180–87 principle of optimality 179–87 returns 179–80 schematic 179–80 ‘travelling salesman’ problem 185–7 e-mail surveys 50–1 economic order quantity see also stock control concepts 195–201 examples 196–9 empowerment, staff 189–90 error sum of the squares (SSE), concepts 122–5, 133–47 errors, data analysis 129–47 estimates mean 76–81 probability theory 22, 25–6, 31–5, 75–81 Euler, L. 131 288 Index events independent events 22–4, 35, 58, 60, 92–5 mutually exclusive events 22–4, 58 probability theory 21–35, 58–66, 92–5 scenario analysis 40, 193–4, 271–4 tree diagrams 30–5 Excel 68, 206–7 exclusive events see mutually exclusive events expected errors, sensitivity analysis 268–9 expected value, net present value (NPV) 231–2 expert systems 275 exponent notation 282–4 exponential distribution, concepts 65–6, 209–10, 252–5 external fraud 272–4 extrapolation 119 extreme value distributions, VaR 262–4 F distribution ANOVA (analysis of variance) 110–20, 127, 134–7 concepts 85–9, 110–20, 127, 134–7 examples 85–9, 110–20, 127, 137 tables 85–8 f notation 8–9, 13–20, 26, 38–9, 44–5, 65–6, 85 factorial notation 53–5, 283–4 failure probabilities see also reliability replacement of assets 215–18, 249–60 feasibility polygons 152–7, 163–4 finance selection, linear programming 164–6 fire extinguishers, ANOVA (analysis of variance) 123–7 focus groups 51 forward recursion 179–87 four by four tables 94–5 fraud 272–4, 276 Fréchet distribution 262 frequency concepts 8–9, 13–20, 37–45 cumulative frequency polygons 13–20, 39–40, 203 graphical presentational approaches 8–9, 13–20 frequentist approach, probability theory 22, 25–6 future cash flows 219–25, 227–34, 240–1 fuzzy logic 276 Garbage In, Garbage Out (GIGO) 261–2 general rules, linear programming 167–70 genetic algorithms 276 ghost costs, transport problems 172–7 goodness of fit test, chi-squared test 91–5 gradient (a notation), linear regression 103–4, 107–20 graphical method, linear programming 149–57, 163–4 graphical presentational approaches concepts 1–20, 149–57, 235–47 rules 8–9 greater-than notation 280–4 Greek alphabet 283 guesswork, modelling 191 histograms 2, 7, 13–20, 41, 73 class intervals 13–20, 44–5 comparative histograms 14–19 concepts 7, 13–20, 41, 73 continuous data 7, 13–14 examples 13–20, 73 skewness 41 uses 7, 13–20 holding costs 182–5, 197–201, 204–8 home insurance 10–12 Hopfield 275 horizontal axis bar charts 8–9 histograms 14–20 linear regression 103–4, 107–20 scatter plots 2–5, 103 hypothesis testing concepts 77–81, 85–95, 110–27 examples 78–80, 85 type I and type II errors 80–1 i notation 8–9, 13–20, 28–30, 37–8, 103–20 identification data 2–5, 261–5 trends 241–7 identity rule 282 impact assessments 21, 271–4 independent events, probability theory 22–4, 35, 58, 60, 92–5 independent variables, concepts 2–5, 70, 103–20, 235 infinity, normal distribution 67–72 information, quality needs 190–4 initial solution, linear programming 167–70 insurance industry 10–12, 29–30 integers 280–4 integration 65–6, 251 intercept (b notation), linear regression 103–4, 107–20 interest rates base rates 240 daily movements 40, 261 project evaluation 219–25, 228–9 internal rate of return (IRR) concepts 220–2, 223–5 examples 220–2 interpolation, IRR 221–2 interviews, uses 48, 51–2 inventory control see stock control Index investment strategies 149–57, 164–6, 262–5 IRR see internal rate of return iterative processes, linear programming 170 j notation 28–30, 37, 104–20, 121–2 JP Morgan 263 k notation 20, 121–7 ‘know your customer’ 272 Kohonen self-organising maps 275 Latin squares concepts 131–2, 143–7 examples 143–7 lead times, stock control 195–201 learning strategies, neural networks 275–6 less-than notation 281–4 lethargy pitfalls, decisions 189 likelihood considerations, scenario analysis 272–3 linear programming additional variables 167–70 concepts 149–70 concerns 170 constraining equations 159–70 costs 167–70, 171–7 critique 170 examples 149–57, 159–70 finance selection 164–6 general rules 167–70 graphical method 149–57, 163–4 initial solution 167–70 iterative processes 170 manual preparation 170 most profitable loans 159–66 optimal advertising allocation 154–7 optimal investment strategies 149–57, 164–6 returns 149–57, 164–6 simplex method 159–70, 171–2 standardisation 167–70 time constraints 167–70 transport problems 171–7 linear regression analysis 110–20 ANOVA (analysis of variance) 110–20 concepts 3, 103–20 equation 103–4 examples 107–20 gradient (a notation) 103–4, 107–20 intercept (b notation) 103–4, 107–20 interpretation 110–20 notation 103–4 residual sum of the squares 109–20 slope significance test 112–20 uncertainties 108–20 literature searches, surveys 48 289 loans finance selection 164–6 linear programming 159–66 risk assessments 159–60 log-normal distribution, concepts 257–8 logarithms (logs), types 20, 61 losses, banks 267–9, 271–4 lotteries 22 lower/upper quartiles, concepts 39–41 m notation 55–8 mail surveys 48, 50–1 management information, graphical presentational approaches 1–20 Mann–Whitney test see U test manual preparation, linear programming 170 margin of error, project evaluation 229–30 market prices, VaR 264–5 marketing brochures 184–7 mathematics 1, 7–8, 196–9, 219–20, 222–5, 234, 240–1, 251, 279–84 matrix plots, concepts 2, 4–5 matrix-based approach, transport problems 171–7 maximum and minimum, concepts 37–9, 40, 254–5 mean comparison of two sample means 79–81 comparisons 75–81 concepts 37–45, 59–60, 65–6, 67–74, 75–81, 97–8, 100–2, 104–27, 134–5 confidence intervals 71, 75–81, 105, 109, 116–20, 190, 262–5 continuous data 44–5, 65–6 estimates 76–81 hypothesis testing 77–81 linear regression 104–20 normal distribution 67–74, 75–81, 97–8 sampling 75–81 mean square causes (MSC), concepts 122–7, 134–47 mean square errors (MSE), ANOVA (analysis of variance) 110–20, 121–7, 134–7 median, concepts 37, 38–42, 83, 98–9 mid-points class intervals 44–5, 241–7 moving averages 241–7 minimax regret rule, concepts 192–4 minimum and maximum, concepts 37–9, 40 mode, concepts 37, 39, 41 modelling banks 75–81, 85, 97, 267–9, 271–4 concepts 75–81, 83, 91–2, 189–90, 195–201, 215–18, 261–5 decision-making pitfalls 189–91 economic order quantity 195–201 290 Index modelling (cont.) guesswork 191 neural networks 275–7 operational risk 75, 262–5, 267–9, 271–4 output reviews 191–2 replacement of assets 215–18, 249–60 VaR 261–5 moments, density functions 65–6, 83–4 money laundering 272–4 Monte Carlo simulation bank cashier problem 209–12 concepts 203–14, 234 examples 203–8 Monty Hall problem 212–13 queuing problems 208–10 random numbers 207–8 stock control 203–8 uses 203, 234 Monty Hall problem 34–5, 212–13 moving averages concepts 241–7 even numbers/observations 244–5 moving totals 245–7 MQMQM plot, concepts 40 MSC see mean square causes MSE see mean square errors multi-way tables, concepts 94–5 multiplication notation 279–80, 282 multiplication rule, probability theory 26–7 multistage sampling 50 mutually exclusive events, probability theory 22–4, 58 n notation 7, 20, 28–30, 37–45, 54–8, 103–20, 121–7, 132–47, 232–4 n!

Index a notation 103–4, 107–20, 135–47 linear regression 103–4, 107–20 slope significance test 112–20 variance 112 abscissa see horizontal axis absolute value, notation 282–4 accuracy and reliability, data 17, 47 adaptive resonance theory 275 addition, mathematical notation 279 addition of normal variables, normal distribution 70 addition rule, probability theory 24–5 additional variables, linear programming 167–70 adjusted cash flows, concepts 228–9 adjusted discount rates, concepts 228–9 Advanced Measurement Approach (AMA) 271 advertising allocation, linear programming 154–7 air-conditioning units 182–5 algorithms, neural networks 275–6 alternatives, decisions 191–4 AMA see Advanced Measurement Approach analysis data 47–52, 129–47, 271–4 Latin squares 131–2, 143–7 linear regression 110–20 projects 190–2, 219–25, 228–34 randomised block design 129–35 sampling 47–52, 129–47 scenario analysis 40, 193–4, 271–4 trends 235–47 two-way classification 135–47 variance 110–20, 121–7 anonimised databases, scenario analysis 273–4 ANOVA (analysis of variance) concepts 110–20, 121–7, 134–47 examples 110–11, 123–7, 134–40 formal background 121–2 linear regression 110–20 randomised block design 134–5, 141–3 tables 110–11, 121–3, 134–47 two-way classification 136–7 appendix 279–84 arithmetic mean, concepts 37–45, 59–60, 65–6, 67–74, 75–81 assets classes 149–57 reliability 17, 47, 215–18, 249–60 replacement of assets 215–18, 249–60 asymptotic distributions 262 ATMs 60 averages see also mean; median; mode concepts 37–9 b notation 103–4, 107–20, 132–5 linear regression 103–4, 107–20 variance 112 back propagation, neural networks 275–7 backwards recursion 179–87 balance sheets, stock 195 bank cashier problem, Monte Carlo simulation 209–12 Bank for International Settlements (BIS) 267–9, 271 banks Basel Accord 262, 267–9, 271 failures 58 loss data 267–9, 271–4 modelling 75–81, 85, 97, 267–9, 271–4 profitable loans 159–66 bar charts comparative data 10–12 concepts 7–12, 54, 56, 59, 205–6, 232–3 discrete data 7–12 examples 9–12, 205–6, 232–3 286 Index bar charts (cont.) narrative explanations 10 relative frequencies 8–12 rules 8–9 uses 7–12, 205–6, 232–3 base rates, trends 240 Basel Accord 262, 267–9, 271 bathtub curves, reliability concepts 249–51 Bayes’theorem, probability theory 27–30, 31 bell-shaped normal distribution see normal distribution bi-directional associative memory 275 bias 1, 17, 47–50, 51–2, 97, 129–35 randomised block design 129–35 sampling 17, 47–50, 51–2, 97, 129–35 skewness 41–5 binomial distribution concepts 55–8, 61–5, 71–2, 98–9, 231–2 examples 56–8, 61–5, 71–2, 98–9 net present value (NPV) 231–2 normal distribution 71–2 Pascal’s triangle 56–7 uses 55, 57, 61–5, 71–2, 98–9, 231–2 BIS see Bank for International Settlements boards of directors 240–1 break-even analysis, concepts 229–30 Brownian motion 22 see also random walks budgets 149–57 calculators, log functions 20, 61 capital Basel Accord 262, 267–9, 271 cost of capital 219–25, 229–30 cash flows adjusted cash flows 228–9 future cash flows 219–25, 227–34, 240–1 net present value (NPV) 219–22, 228–9, 231–2 standard deviation 232–4 central limit theorem concepts 70, 75 examples 70 chi-squared test concepts 83–4, 85, 89, 91–5 contingency tables 92–5 examples 83–4, 85, 89, 91–2 goodness of fit test 91–5 multi-way tables 94–5 tables 84, 91 Chu Shi-Chieh’s Ssu Yuan Y Chien 56 circles, tree diagrams 30–5 class intervals concepts 13–20, 44–5, 63–4, 241–7 histograms 13–20, 44–5 mean calculations 44–5 mid-points 44–5, 241–7 notation 13–14, 20 Sturges’s formula 20 variance calculations 44–5 classical approach, probability theory 22, 27 cluster sampling 50 coin-tossing examples, probability theory 21–3, 53–4 collection techniques, data 17, 47–52, 129–47 colours, graphical presentational approaches 9 combination, probability distribution (density) functions 54–8 common logarithm (base 10) 20 communications, decisions 189–90 comparative data, bar charts 10–12 comparative histograms see also histograms examples 14–19 completed goods 195 see also stock . . . conditional probability, concepts 25–7, 35 confidence intervals, concepts 71, 75–81, 105, 109, 116–20, 190, 262–5 constraining equations, linear programming 159–70 contingency tables, concepts 92–5 continuous approximation, stock control 200–1 continuous case, failures 251 continuous data concepts 7, 13–14, 44–5, 65–6, 251 histograms 7, 13–14 continuous uniform distribution, concepts 64–6 correlation coefficient concepts 104–20, 261–5, 268–9 critical value 105–6, 113–20 equations 104–5 examples 105–8, 115–20 costs capital 219–25, 229–30 dynamic programming 180–82 ghost costs 172–7 holding costs 182–5, 197–201, 204–8 linear programming 167–70, 171–7 sampling 47 stock control 182–5, 195–201 transport problems 171–7 trend analysis 236–47 types 167–8, 182 counting techniques, probability distribution (density) functions 54 covariance see also correlation coefficient concepts 104–20, 263–5 credit cards 159–66, 267–9 credit derivatives 97 see also derivatives Index credit risk, modelling 75, 149, 261–5 critical value, correlation coefficient 105–6, 113–20 cumulative frequency polygons concepts 13–20, 39–40, 203 examples 14–20 uses 13–14 current costs, linear programming 167–70 cyclical variations, trends 238–47 data analysis methods 47–52, 129–47, 271–4 collection techniques 17, 47–52, 129–47 continuous/discrete types 7–12, 13–14, 44–5, 53–5, 65–6, 72, 251 design/approach to analysis 129–47 errors 129–47 graphical presentational approaches 1–20, 149–57 identification 2–5, 261–5 Latin squares 131–2, 143–7 loss data 267–9, 271–4 neural networks 275–7 qualities 17, 47 randomised block design 129–35 reliability and accuracy 17, 47 sampling 17, 47–52 time series 235–47 trends 5, 10, 235–47 two-way classification analysis 135–47 data points, scatter plots 2–5 databases, loss databases 272–4 debentures 149–57 decisions alternatives 191–4 Bayes’theorem 27–30, 31 communications 189–90 concepts 21–35, 189–94, 215–25, 228–34, 249–60 courses of action 191–2 definition 21 delegation 189–90 empowerment 189–90 guesswork 191 lethargy pitfalls 189 minimax regret rule 192–4 modelling problems 189–91 Monty Hall problem 34–5, 212–13 pitfalls 189–94 probability theory 21–35, 53–66, 189–94, 215–18 problem definition 129, 190–2 project analysis guidelines 190–2, 219–25, 228–34 replacement of assets 215–18, 249–60 staff 189–90 287 steps 21 stock control 195–201, 203–8 theory 189–94 degrees of freedom 70–1, 75–89, 91–5, 110–20, 136–7 ANOVA (analysis of variance) 110–20, 121–7, 136–7 concepts 70–1, 75–89, 91–5, 110–20, 136–7 delegation, decisions 189–90 density functions see also probability distribution (density) functions concepts 65–6, 67, 83–4 dependent variables, concepts 2–5, 103–20, 235 derivatives 58, 97–8, 272 see also credit . . . ; options design/approach to analysis, data 129–47 dice-rolling examples, probability theory 21–3, 53–5 differentiation 251 discount factors adjusted discount rates 228–9 net present value (NPV) 220–1, 228–9, 231–2 discrete data bar charts 7–12, 13 concepts 7–12, 13, 44–5, 53–5, 72 discrete uniform distribution, concepts 53–5 displays see also presentational approaches data 1–5 Disraeli, Benjamin 1 division notation 280, 282 dynamic programming complex examples 184–7 concepts 179–87 costs 180–82 examples 180–87 principle of optimality 179–87 returns 179–80 schematic 179–80 ‘travelling salesman’ problem 185–7 e-mail surveys 50–1 economic order quantity see also stock control concepts 195–201 examples 196–9 empowerment, staff 189–90 error sum of the squares (SSE), concepts 122–5, 133–47 errors, data analysis 129–47 estimates mean 76–81 probability theory 22, 25–6, 31–5, 75–81 Euler, L. 131 288 Index events independent events 22–4, 35, 58, 60, 92–5 mutually exclusive events 22–4, 58 probability theory 21–35, 58–66, 92–5 scenario analysis 40, 193–4, 271–4 tree diagrams 30–5 Excel 68, 206–7 exclusive events see mutually exclusive events expected errors, sensitivity analysis 268–9 expected value, net present value (NPV) 231–2 expert systems 275 exponent notation 282–4 exponential distribution, concepts 65–6, 209–10, 252–5 external fraud 272–4 extrapolation 119 extreme value distributions, VaR 262–4 F distribution ANOVA (analysis of variance) 110–20, 127, 134–7 concepts 85–9, 110–20, 127, 134–7 examples 85–9, 110–20, 127, 137 tables 85–8 f notation 8–9, 13–20, 26, 38–9, 44–5, 65–6, 85 factorial notation 53–5, 283–4 failure probabilities see also reliability replacement of assets 215–18, 249–60 feasibility polygons 152–7, 163–4 finance selection, linear programming 164–6 fire extinguishers, ANOVA (analysis of variance) 123–7 focus groups 51 forward recursion 179–87 four by four tables 94–5 fraud 272–4, 276 Fréchet distribution 262 frequency concepts 8–9, 13–20, 37–45 cumulative frequency polygons 13–20, 39–40, 203 graphical presentational approaches 8–9, 13–20 frequentist approach, probability theory 22, 25–6 future cash flows 219–25, 227–34, 240–1 fuzzy logic 276 Garbage In, Garbage Out (GIGO) 261–2 general rules, linear programming 167–70 genetic algorithms 276 ghost costs, transport problems 172–7 goodness of fit test, chi-squared test 91–5 gradient (a notation), linear regression 103–4, 107–20 graphical method, linear programming 149–57, 163–4 graphical presentational approaches concepts 1–20, 149–57, 235–47 rules 8–9 greater-than notation 280–4 Greek alphabet 283 guesswork, modelling 191 histograms 2, 7, 13–20, 41, 73 class intervals 13–20, 44–5 comparative histograms 14–19 concepts 7, 13–20, 41, 73 continuous data 7, 13–14 examples 13–20, 73 skewness 41 uses 7, 13–20 holding costs 182–5, 197–201, 204–8 home insurance 10–12 Hopfield 275 horizontal axis bar charts 8–9 histograms 14–20 linear regression 103–4, 107–20 scatter plots 2–5, 103 hypothesis testing concepts 77–81, 85–95, 110–27 examples 78–80, 85 type I and type II errors 80–1 i notation 8–9, 13–20, 28–30, 37–8, 103–20 identification data 2–5, 261–5 trends 241–7 identity rule 282 impact assessments 21, 271–4 independent events, probability theory 22–4, 35, 58, 60, 92–5 independent variables, concepts 2–5, 70, 103–20, 235 infinity, normal distribution 67–72 information, quality needs 190–4 initial solution, linear programming 167–70 insurance industry 10–12, 29–30 integers 280–4 integration 65–6, 251 intercept (b notation), linear regression 103–4, 107–20 interest rates base rates 240 daily movements 40, 261 project evaluation 219–25, 228–9 internal rate of return (IRR) concepts 220–2, 223–5 examples 220–2 interpolation, IRR 221–2 interviews, uses 48, 51–2 inventory control see stock control Index investment strategies 149–57, 164–6, 262–5 IRR see internal rate of return iterative processes, linear programming 170 j notation 28–30, 37, 104–20, 121–2 JP Morgan 263 k notation 20, 121–7 ‘know your customer’ 272 Kohonen self-organising maps 275 Latin squares concepts 131–2, 143–7 examples 143–7 lead times, stock control 195–201 learning strategies, neural networks 275–6 less-than notation 281–4 lethargy pitfalls, decisions 189 likelihood considerations, scenario analysis 272–3 linear programming additional variables 167–70 concepts 149–70 concerns 170 constraining equations 159–70 costs 167–70, 171–7 critique 170 examples 149–57, 159–70 finance selection 164–6 general rules 167–70 graphical method 149–57, 163–4 initial solution 167–70 iterative processes 170 manual preparation 170 most profitable loans 159–66 optimal advertising allocation 154–7 optimal investment strategies 149–57, 164–6 returns 149–57, 164–6 simplex method 159–70, 171–2 standardisation 167–70 time constraints 167–70 transport problems 171–7 linear regression analysis 110–20 ANOVA (analysis of variance) 110–20 concepts 3, 103–20 equation 103–4 examples 107–20 gradient (a notation) 103–4, 107–20 intercept (b notation) 103–4, 107–20 interpretation 110–20 notation 103–4 residual sum of the squares 109–20 slope significance test 112–20 uncertainties 108–20 literature searches, surveys 48 289 loans finance selection 164–6 linear programming 159–66 risk assessments 159–60 log-normal distribution, concepts 257–8 logarithms (logs), types 20, 61 losses, banks 267–9, 271–4 lotteries 22 lower/upper quartiles, concepts 39–41 m notation 55–8 mail surveys 48, 50–1 management information, graphical presentational approaches 1–20 Mann–Whitney test see U test manual preparation, linear programming 170 margin of error, project evaluation 229–30 market prices, VaR 264–5 marketing brochures 184–7 mathematics 1, 7–8, 196–9, 219–20, 222–5, 234, 240–1, 251, 279–84 matrix plots, concepts 2, 4–5 matrix-based approach, transport problems 171–7 maximum and minimum, concepts 37–9, 40, 254–5 mean comparison of two sample means 79–81 comparisons 75–81 concepts 37–45, 59–60, 65–6, 67–74, 75–81, 97–8, 100–2, 104–27, 134–5 confidence intervals 71, 75–81, 105, 109, 116–20, 190, 262–5 continuous data 44–5, 65–6 estimates 76–81 hypothesis testing 77–81 linear regression 104–20 normal distribution 67–74, 75–81, 97–8 sampling 75–81 mean square causes (MSC), concepts 122–7, 134–47 mean square errors (MSE), ANOVA (analysis of variance) 110–20, 121–7, 134–7 median, concepts 37, 38–42, 83, 98–9 mid-points class intervals 44–5, 241–7 moving averages 241–7 minimax regret rule, concepts 192–4 minimum and maximum, concepts 37–9, 40 mode, concepts 37, 39, 41 modelling banks 75–81, 85, 97, 267–9, 271–4 concepts 75–81, 83, 91–2, 189–90, 195–201, 215–18, 261–5 decision-making pitfalls 189–91 economic order quantity 195–201 290 Index modelling (cont.) guesswork 191 neural networks 275–7 operational risk 75, 262–5, 267–9, 271–4 output reviews 191–2 replacement of assets 215–18, 249–60 VaR 261–5 moments, density functions 65–6, 83–4 money laundering 272–4 Monte Carlo simulation bank cashier problem 209–12 concepts 203–14, 234 examples 203–8 Monty Hall problem 212–13 queuing problems 208–10 random numbers 207–8 stock control 203–8 uses 203, 234 Monty Hall problem 34–5, 212–13 moving averages concepts 241–7 even numbers/observations 244–5 moving totals 245–7 MQMQM plot, concepts 40 MSC see mean square causes MSE see mean square errors multi-way tables, concepts 94–5 multiplication notation 279–80, 282 multiplication rule, probability theory 26–7 multistage sampling 50 mutually exclusive events, probability theory 22–4, 58 n notation 7, 20, 28–30, 37–45, 54–8, 103–20, 121–7, 132–47, 232–4 n!


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

Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Albert Einstein, Andrew Wiles, Claude Shannon: information theory, cloud computing, complexity theory, Erdős number, four colour theorem, Gerolamo Cardano, Isaac Newton, John von Neumann, linear programming, new economy, NP-complete, Occam's razor, P = NP, Paul Erdős, Richard Feynman, Richard Feynman, smart grid, Stephen Hawking, traveling salesman, Turing machine, Turing test, Watson beat the top human players on Jeopardy!, William of Occam

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

Albert Einstein, asset allocation, backtesting, Benoit Mandelbrot, Black-Scholes formula, Bonfire of the Vanities, Brownian motion, buy low sell high, capital asset pricing model, debt deflation, diversified portfolio, Eugene Fama: efficient market hypothesis, financial innovation, financial intermediation, fixed income, full employment, implied volatility, index arbitrage, index fund, interest rate swap, invisible hand, John von Neumann, Joseph Schumpeter, law of one price, linear programming, Louis Bachelier, mandelbrot fractal, martingale, means of production, new economy, New Journalism, profit maximization, Ralph Nader, RAND corporation, random walk, Richard Thaler, risk/return, Robert Shiller, Robert Shiller, Ronald Reagan, stochastic process, the market place, The Predators' Ball, the scientific method, The Wealth of Nations by Adam Smith, Thorstein Veblen, transaction costs, transfer pricing, zero-coupon bond

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

barriers to entry, call centre, disintermediation, en.wikipedia.org, hypertext link, interchangeable parts, invention of movable type, James Watt: steam engine, linear programming, market design, pattern recognition, recommendation engine, Saturday Night Live, shareholder value, Skype, spectrum auction, Steve Jobs, subscription business, Telecommunications Act of 1996, Vickrey auction, yield management

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.

• Nielsen DMAs roughly correspond to the broadcast coverage areas of television stations and there are approximately 1,400 commercial television stations in the United States. • Because cable systems and satellite systems offer similar services, they fiercely compete for subscribers. • Television content is packaged in one of these basic ways: free, hybrid subscription, pure subscription, pay-per-view, rental and purchase. • The major components of the television business are form factors, packaging and distribution. • Linear programming is scheduled for consumers, Non-linear programming is on-demand. • There are highly evolved business rules and negotiable currencies used in the traditional television business, and these must evolve for networked, non-linear or on-demand businesses Copyright © 2006, Shelly Palmer. All rights reserved. 1-Television.Chap One v3sp.qxd 3/20/06 7:19 AM Page 24 2-Television.Chap Two v3.qxd 3/20/06 7:34 AM Page 25 2 Disrupting Television Using Existing Network Technologies In this chapter, let’s use the term “disruptive technology” to describe a system or methodology that allows the viewer to take control away from the programmers or distributors.

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

Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Albert Einstein, Albert Michelson, anesthesia awareness, anthropic principle, brain emulation, cellular automata, Claude Shannon: information theory, cloud computing, computer age, Dean Kamen, discovery of DNA, double helix, en.wikipedia.org, epigenetics, George Gilder, Google Earth, Isaac Newton, iterative process, Jacquard loom, Jacquard loom, John von Neumann, Law of Accelerating Returns, linear programming, Loebner Prize, mandelbrot fractal, Norbert Wiener, optical character recognition, pattern recognition, Peter Thiel, Ralph Waldo Emerson, random walk, Ray Kurzweil, reversible computing, self-driving car, speech recognition, Steven Pinker, strong AI, the scientific method, theory of mind, Turing complete, Turing machine, Turing test, Wall-E, Watson beat the top human players on Jeopardy!, X Prize

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

affirmative action, anti-communist, Anton Chekhov, asset allocation, Buckminster Fuller, clean water, cognitive dissonance, computer age, double helix, Fellow of the Royal Society, John von Neumann, linear programming, market clearing, New Journalism, oil shock, Plutocrats, plutocrats, profit motive, RAND corporation, Simon Kuznets, the scientific method

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

Albert Einstein, Andrei Shleifer, Benoit Mandelbrot, bitcoin, Brownian motion, Claude Shannon: information theory, cloud computing, cognitive dissonance, computer age, conceptual framework, crony capitalism, crowdsourcing, cuban missile crisis, Daniel Kahneman / Amos Tversky, David Graeber, Dissolution of the Soviet Union, double helix, Drosophila, Francis Fukuyama: the end of history, From Mathematics to the Technologies of Life and Death, hive mind, index card, informal economy, invisible hand, Jacquard loom, Jacquard loom, John von Neumann, Kevin Kelly, knowledge economy, knowledge worker, linear programming, mandelbrot fractal, Marshall McLuhan, means of production, Menlo Park, Mikhail Gorbachev, mutually assured destruction, Network effects, Norbert Wiener, packet switching, pattern recognition, Paul Erdős, Peter Thiel, RAND corporation, rent-seeking, road to serfdom, Ronald Coase, scientific mainstream, Steve Jobs, Stewart Brand, stochastic process, technoutopianism, The Structural Transformation of the Public Sphere, transaction costs, Turing machine

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

4chan, Ada Lovelace, Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Albert Einstein, algorithmic trading, anthropic principle, asset allocation, autonomous vehicles, Berlin Wall, Bill Duvall, bitcoin, Community Supported Agriculture, complexity theory, constrained optimization, cosmological principle, cryptocurrency, Danny Hillis, delayed gratification, dematerialisation, diversification, double helix, Elon Musk, fault tolerance, Fellow of the Royal Society, Firefox, first-price auction, Flash crash, Frederick Winslow Taylor, George Akerlof, global supply chain, Google Chrome, Henri Poincaré, information retrieval, Internet Archive, Jeff Bezos, John Nash: game theory, John von Neumann, knapsack problem, Lao Tzu, linear programming, martingale, Nash equilibrium, natural language processing, NP-complete, P = NP, packet switching, prediction markets, race to the bottom, RAND corporation, RFC: Request For Comment, Robert X Cringely, sealed-bid auction, second-price auction, self-driving car, Silicon Valley, Skype, sorting algorithm, spectrum auction, Steve Jobs, stochastic process, Thomas Malthus, traveling salesman, Turing machine, urban planning, Vickrey auction, Walter Mischel, Y Combinator

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: 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

Albert Einstein, Andrei Shleifer, asset allocation, asset-backed security, bank run, Benoit Mandelbrot, Black-Scholes formula, Bretton Woods, Brownian motion, capital asset pricing model, card file, Cass Sunstein, collateralized debt obligation, complexity theory, corporate governance, Credit Default Swap, credit default swaps / collateralized debt obligations, Daniel Kahneman / Amos Tversky, David Ricardo: comparative advantage, discovery of the americas, diversification, diversified portfolio, Edward Glaeser, endowment effect, Eugene Fama: efficient market hypothesis, experimental economics, financial innovation, Financial Instability Hypothesis, floating exchange rates, George Akerlof, Henri Poincaré, Hyman Minsky, implied volatility, impulse control, index arbitrage, index card, index fund, invisible hand, Isaac Newton, John Nash: game theory, John von Neumann, joint-stock company, Joseph Schumpeter, libertarian paternalism, linear programming, Long Term Capital Management, Louis Bachelier, mandelbrot fractal, market bubble, market design, New Journalism, Nikolai Kondratiev, Paul Lévy, pension reform, performance metric, Ponzi scheme, prediction markets, pushing on a string, quantitative trading / quantitative finance, Ralph Nader, RAND corporation, random walk, Richard Thaler, risk/return, road to serfdom, Robert Shiller, Robert Shiller, rolodex, Ronald Reagan, shareholder value, Sharpe ratio, short selling, side project, Silicon Valley, South Sea Bubble, statistical model, The Chicago School, The Myth of the Rational Market, The Predators' Ball, the scientific method, The Wealth of Nations by Adam Smith, The Wisdom of Crowds, Thomas Kuhn: the structure of scientific revolutions, Thomas L Friedman, Thorstein Veblen, Tobin tax, transaction costs, tulip mania, value at risk, Vanguard fund, volatility smile, Yogi Berra

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 a better mousetrap, knowledge worker, linear programming, nuclear winter, Sand Hill Road, Silicon Valley, sorting algorithm, Superbowl ad, the scientific method, type inference, unpaid internship

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

Albert Einstein, Andrew Wiles, Antoine Gombaud: Chevalier de Méré, Big bang: deregulation of the City of London, Bretton Woods, buttonwood tree, capital asset pricing model, cognitive dissonance, Daniel Kahneman / Amos Tversky, diversified portfolio, double entry bookkeeping, Edmond Halley, Edward Lloyd's coffeehouse, endowment effect, experimental economics, fear of failure, Fellow of the Royal Society, Fermat's Last Theorem, financial deregulation, financial innovation, full employment, index fund, invention of movable type, Isaac Newton, John Nash: game theory, John von Neumann, linear programming, loss aversion, Louis Bachelier, mental accounting, moral hazard, Nash equilibrium, probability theory / Blaise Pascal / Pierre de Fermat, random walk, Richard Thaler, Robert Shiller, Robert Shiller, spectrum auction, statistical model, The Bell Curve by Richard Herrnstein and Charles Murray, The Wealth of Nations by Adam Smith, trade route, transaction costs, tulip mania, Vanguard fund

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

Asian financial crisis, asset allocation, backtesting, capital asset pricing model, collateralized debt obligation, commodity trading advisor, compound rate of return, constrained optimization, corporate governance, correlation coefficient, Credit Default Swap, credit default swaps / collateralized debt obligations, discrete time, distributed generation, diversification, diversified portfolio, dividend-yielding stocks, fixed income, high net worth, implied volatility, index arbitrage, index fund, interest rate swap, iterative process, linear programming, London Interbank Offered Rate, Long Term Capital Management, market fundamentalism, merger arbitrage, Mexican peso crisis / tequila crisis, p-value, Ponzi scheme, quantitative trading / quantitative finance, random walk, risk-adjusted returns, risk/return, Sharpe ratio, short selling, stochastic process, systematic trading, technology bubble, transaction costs, value at risk

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

Apple II, Apple's 1984 Super Bowl advert, barriers to entry, Bill Gates: Altair 8800, business process, card file, computer age, computer vision, continuous integration, deskilling, Grace Hopper, inventory management, John von Neumann, linear programming, Menlo Park, Network effects, popular electronics, RAND corporation, Robert X Cringely, Ronald Reagan, Silicon Valley, software patent, Steve Jobs, Steve Wozniak, Steven Levy, Thomas Kuhn: the structure of scientific revolutions

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

American Society of Civil Engineers: Report Card, Andrei Shleifer, Cass Sunstein, clean water, computer vision, delayed gratification, double entry bookkeeping, Exxon Valdez, fault tolerance, happiness index / gross national happiness, impulse control, indoor plumbing, inventory management, knowledge worker, late fees, linear programming, mental accounting, microcredit, p-value, payday loans, purchasing power parity, randomized controlled trial, Report Card for America’s Infrastructure, Richard Thaler, Saturday Night Live, Walter Mischel, Yogi Berra

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: 544 words: 96,029

Practical C Programming, 3rd Edition by Steve Oualline

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

Grace Hopper, index card, linear programming

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.

#define, #define vs. const continue statement, continue Statement, switch, break, and continue control flow, Decision and Control Statements control statements, How C Works control variables, for Statement conversion routines, Conversion Routines cpp program, #define Statement cprint printer, Electronic Archaeology CR (carriage return), The End-of-Line Puzzle cross-reference programs, Electronic Archaeology ctype.h, Rest of Program curly braces, if Statement and arrays, Initializing Variables D data declarations, How C Works, Elements of a Program data types enumerated, enum Type dbx debugger, Interactive Debuggers commands, Interactive Debuggers debug statement, Conditional Compilation debugging, How to Learn C, Style, Programming Process, Testing, Answers binary search, Debugging a Binary Search breakpoints, Debugging a Binary Search command-line switch, Debug Command-Line Switch conditional compilation, Debug-Only Code with cdb, Interactive Debuggers with dbx, Interactive Debuggers with sdb, Interactive Debuggers debugging, divide and conquer method, Divide and Conquer debugging, going through output, Going Through the Output debugging, interactive, Interactive Debuggers debugging, save file, Debugging decision statements, How This Book is Organized declarations, Style, Elements of a Program pointer, Simple Pointers declarations, array, How C Works declarations, data, How C Works declarations, integer, Integers declarations, structures, How C Works declarations, variable, Variables and Storage, Variable Declarations default statement, switch Statement, switch Statement defining bit values, Setting, Clearing, and Testing Bits dereference operator (*), Simple Pointers derrived class, Line Counter Submodule (lc) diagnostic printf, Debugging dimensions, array, Arrays directories, Setting Up divide by error, Runtime Errors divide operator (/), Simple Expressions, Floating Point Versus Integer Divide division, floating point, Division do/while statement, do/while documents, government, How Programming Works DOS Makefile, The Makefile for Multiple Files double, Determining Accuracy, Precision and Speed linked list, Double-Linked Lists double quotes, Characters, Strings dynamic data structures, Advanced Pointers E elements, Arrays, Structures else statement, else Statement English language, How Programming Works enum, enum Type enumerated data types, enum Type EOF, File Input/Output escape character, Characters Evaluation order problems, Side Effects EVEN macro, The and Operator (&) exclusive or (^), Bit Operators, The Bitwise Exclusive or (^) executable statements, Basic Program Structure exercises, How to Learn C extern, The extern Modifier F factorial (program), Recursion far pointers, Simple Pointers fclose, File Input/Output fflush, Buffering Problems, Runtime Errors fgetc, File Input/Output fgets, File Input/Output standard function, Reading Strings fgets, newline problem, Reading Strings Fibonacci (program), while Statement fields, Structures bit, Bit Fields or Packed Structures file, source, How C Works files, File Input/Output, Answers binary, Byte Order Problem closing, File Input/Output FILE, File Input/Output formats, Style, Designing File Formats header, Headers naming, File Input/Output, Filename Problems opening, File Input/Output types, File Types variables, File Input/Output files, ASCII, Binary and ASCII Files files, binary, Binary and ASCII Files float, Precision and Speed float.h include file, Determining Accuracy floating point, Floating Point floating point accuracy, Accuracy, Determining Accuracy floating point addition, Floating Addition/Subtraction floating point division, Division floating point multiplication, Multiplication floating point overflow, Overflow and Underflow floating point precision, Precision and Speed floating point speed, Precision and Speed floating point subtraction, Floating Addition/Subtraction floating point underflow, Overflow and Underflow floating point, float.h, Determining Accuracy floating point, guard digit, Floating-Point Format floating point, roundoff error, Roundoff Error, Minimizing Roundoff Error floating-point, Types of Floats declaration, Floating Point division, Floating Point Versus Integer Divide exception, Runtime Errors numbers, Characters floating-point underflow, Overflow and Underflow fopen, File Input/Output for statement, for Statement FORTRAN, How Programming Works, for Statement fprintf, Conversion Routines fputc, File Input/Output fputs, File Input/Output fread, Binary I/O free, free Function fscanf, Conversion Routines FTP, obtaining exercises via, FTP FTPMAIL, FTPMAIL FTPMAIL, obtaining exercises via, FTPMAIL functions, How This Book is Organized, Functions library, Basic Program Structure functions, standard, How C Works fwrite, Binary I/O G generic pointer, Pointers and Structures global variables, Variable Scope and Functions, Scope and Class government documents, How Programming Works graphics, bitmapped, Bitmapped Graphics grind printer, Electronic Archaeology guard digit, floating point, Floating-Point Format H header files, Headers heading comments, Style, Basic Program Structure hello (program), Style helmet law, How Programming Works help, Getting Help on UNIX hexadecimal, Bit Operations numbers, Hexadecimal and Octal Constants high level languages, How Programming Works histogram program, Using the Infinite Array I if statement, if Statement include file, float.h, Determining Accuracy include files, include Files indent program, Electronic Archaeology indentation, Indentation and Code Format tools, Electronic Archaeology indexes (and arrays), Arrays infinite arrays, Modules, A Program to Use Infinite Arrays, Using the Infinite Array initializing strings, Initializing Variables structures, Structures variables, Initializing Variables initializing, multiple-dimensional arrays, Initializing Variables instructions, How C Works int, long, Types of Integers int, unsigned, Types of Integers integer declarations, Integers division, Floating Point Versus Integer Divide overflow, Answers types, Types of Integers integer, very short (char), Types of Integers interactive debugging, Interactive Debuggers isalpha, Rest of Program K Kernigham, Brian, Brief History of C L labels, goto, goto language, assembly, How Programming Works language, assembly, translation, How Programming Works language, C, Brief History of C language, C++, Brief History of C language, COBOL, How Programming Works language, English, How Programming Works language, FORTRAN, How Programming Works language, machine, How Programming Works language, PASCAL, How Programming Works languages, high level, How Programming Works law, helmet, How Programming Works learning C++, How to Learn C left shift (), Bit Operators, The Left- and Right-Shift Operators (<<, >>) lex utility, Compiler lexical analysis, Compiler LF (line feed), The End-of-Line Puzzle libraries, How C Works library functions, Basic Program Structure limit error, Answers line feed, The End-of-Line Puzzle linear~programs, Decision and Control Statements lines, in coding, Basic Program Structure linked lists, Linked List, A Program to Use Infinite Arrays linked lists, add element, Linked List linked lists, locate element, Linked List list command (dbx), Interactive Debuggers local header files, Headers include files, include Files variables, Variable Scope and Functions, Scope and Class long double integers, Types of Floats long int, Types of Integers and portability, Word Size looping statements, How C Works, Decision and Control Statements, Looping Statements M machine language, How Programming Works macros definitions, Summary replacement, #define Statement macros, and parameters, Parameterized Macros magic numbers, Designing File Formats main, Basic Program Structure maintaining code, Style maintaining programs, Programming Process make, Makefile, The Makefile for Multiple Files targets, The Makefile for Multiple Files with multiple files, The Makefile for Multiple Files Makefile, Makefile, The Makefile for Multiple Files DOS, The Makefile for Multiple Files malloc, Pointers and Structures man pages (UNIX), Getting Help on UNIX math operators, Simple Expressions mechanics of programming, How This Book is Organized memory, How C Works memset, The Power of Powers of 2, Using the Infinite Array min macro, The ?


pages: 287 words: 86,919

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

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

Ada Lovelace, airport security, Berlin Wall, bioinformatics, Bretton Woods, computer age, Craig Reynolds: boids flock, discovery of DNA, double helix, Douglas Engelbart, easy for humans, difficult for computers, Fall of the Berlin Wall, Grace Hopper, Hacker Ethic, informal economy, John Conway, Kevin Kelly, late capitalism, linear programming, Marshall McLuhan, means of production, Menlo Park, mutually assured destruction, Norbert Wiener, packet switching, phenotype, post-industrial society, profit motive, QWERTY keyboard, RAND corporation, Ray Kurzweil, RFC: Request For Comment, Richard Stallman, semantic web, SETI@home, stem cell, Steve Crocker, Steven Levy, Stewart Brand, Ted Nelson, telerobotics, the market place, theory of mind, urban planning, Vannevar Bush, Whole Earth Review, working poor

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-specific and fluid.”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 fields of physics and statistics, is also proto-protocological (pp. 12, 8). 88. The coinage “robot” is attributed to the writer Karel Č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

bioinformatics, Black-Scholes formula, Brownian motion, continuous integration, discrete time, implied volatility, incomplete markets, interest rate swap, linear programming, London Interbank Offered Rate, mandelbrot fractal, martingale, random walk, stochastic process, stochastic volatility, transaction costs, value at risk, volatility smile, Wiener process, zero-coupon bond

Kloeden, J. Ombach: From Elementary Probability to Stochastic Differential Equations with MAPLE. Springer (2001). M. Dai: A closed-form solution for perpetual American floating 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

Albert Einstein, algorithmic trading, Andrew Wiles, Antoine Gombaud: Chevalier de Méré, asset allocation, asset-backed security, backtesting, bank run, banking crisis, Black-Scholes formula, Bonfire of the Vanities, Bretton Woods, Brownian motion, business process, buy low sell high, capital asset pricing model, centre right, collateralized debt obligation, corporate governance, correlation coefficient, Credit Default Swap, credit default swaps / collateralized debt obligations, currency manipulation / currency intervention, discounted cash flows, disintermediation, diversification, Emanuel Derman, en.wikipedia.org, Eugene Fama: efficient market hypothesis, financial innovation, fixed income, full employment, George Akerlof, Gordon Gekko, hiring and firing, implied volatility, index fund, interest rate derivative, interest rate swap, John von Neumann, linear programming, Loma Prieta earthquake, Long Term Capital Management, margin call, market friction, market microstructure, martingale, merger arbitrage, Nick Leeson, P = NP, pattern recognition, pensions crisis, performance metric, prediction markets, profit maximization, purchasing power parity, quantitative trading / quantitative finance, QWERTY keyboard, RAND corporation, random walk, Ray Kurzweil, Richard Feynman, Richard Feynman, Richard Stallman, risk-adjusted returns, risk/return, shareholder value, Sharpe ratio, short selling, Silicon Valley, six sigma, sorting algorithm, statistical arbitrage, statistical model, stem cell, Steven Levy, stochastic process, systematic trading, technology bubble, The Great Moderation, the scientific method, too big to fail, trade route, transaction costs, transfer pricing, value at risk, volatility smile, Wiener process, yield curve, young professional

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: 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

Airbnb, airport security, Al Roth, Andrei Shleifer, attribution theory, autonomous vehicles, barriers to entry, Brownian motion, centralized clearinghouse, clean water, conceptual framework, constrained optimization, continuous double auction, deferred acceptance, Donald Trump, Edward Glaeser, experimental subject, first-price auction, framing effect, frictionless, fundamental attribution error, George Akerlof, Goldman Sachs: Vampire Squid, helicopter parent, Internet of things, invisible hand, Isaac Newton, iterative process, Jean Tirole, Jeff Bezos, Johann Wolfgang von Goethe, John Nash: game theory, John von Neumann, Joseph Schumpeter, late fees, linear programming, Lyft, market clearing, market design, market friction, medical residency, multi-sided market, mutually assured destruction, Nash equilibrium, Occupy movement, Peter Thiel, pets.com, pez dispenser, pre–internet, price mechanism, price stability, prisoner's dilemma, profit motive, proxy bid, RAND corporation, ride hailing / ride sharing, Robert Shiller, Robert Shiller, Ronald Coase, school choice, school vouchers, sealed-bid auction, second-price auction, second-price sealed-bid, sharing economy, Silicon Valley, spectrum auction, Steve Jobs, Tacoma Narrows Bridge, technoutopianism, telemarketer, The Market for Lemons, The Wisdom of Crowds, Thomas Malthus, Thorstein Veblen, trade route, transaction costs, two-sided market, uranium enrichment, Vickrey auction, winner-take-all economy

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

The World's First Railway System: Enterprise, Competition, and Regulation on the Railway Network in Victorian Britain by Mark Casson

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

banking crisis, barriers to entry, Beeching cuts, British Empire, combinatorial explosion, Corn Laws, corporate social responsibility, David Ricardo: comparative advantage, intermodal, iterative process, joint-stock company, joint-stock limited liability company, knowledge economy, linear programming, Network effects, New Urbanism, performance metric, railway mania, rent-seeking, strikebreaker, the market place, transaction costs

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

A Pattern Language, active transport: walking or cycling, big-box store, Buckminster Fuller, car-free, carbon footprint, clean water, congestion charging, delayed gratification, distributed generation, drive until you qualify, East Village, food miles, garden city movement, hydrogen economy, invisible hand, Jane Jacobs, linear programming, McMansion, Murano, Venice glass, Negawatt, New Urbanism, oil shale / tar sands, peak oil, placebo effect, Stewart Brand, The Death and Life of Great American Cities, Thomas L Friedman, unemployed young men, urban planning, urban sprawl, walkable city

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

A Declaration of the Independence of Cyberspace, Anne Wojcicki, book scanning, borderless world, Buckminster Fuller, citizen journalism, correlation does not imply causation, crowdsourcing, death of newspapers, Edward Lloyd's coffeehouse, Firefox, future of journalism, Googley, Hacker Ethic, informal economy, Jaron Lanier, Julian Assange, Kevin Kelly, linear programming, offshore financial centre, pets.com, publish or perish, race to the bottom, Saturday Night Live, Silicon Valley, Silicon Valley startup, Skype, spectrum auction, Steve Jobs, Steven Levy, Stewart Brand, subscription business, Telecommunications Act of 1996, Whole Earth Catalog, WikiLeaks

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

Any sufficiently advanced technology is indistinguishable from magic, Beeching cuts, British Empire, cognitive dissonance, complexity theory, congestion charging, dumpster diving, finite state, Firefox, HyperCard, invisible hand, land reform, linear programming, peak oil, security theater, sensible shoes, side project, telemarketer, Turing machine

"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."


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

Albert Einstein, asset allocation, Atul Gawande, backtesting, Bernie Madoff, Black Swan, buy low sell high, capital asset pricing model, Clayton Christensen, commodity trading advisor, correlation coefficient, Daniel Kahneman / Amos Tversky, delayed gratification, deliberate practice, diversification, diversified portfolio, Elliott wave, Emanuel Derman, Eugene Fama: efficient market hypothesis, fiat currency, fixed income, game design, hindsight bias, housing crisis, index fund, Isaac Newton, John Nash: game theory, linear programming, Long Term Capital Management, mandelbrot fractal, margin call, market bubble, market fundamentalism, market microstructure, mental accounting, Nash equilibrium, new economy, Nick Leeson, Ponzi scheme, prediction markets, random walk, Renaissance Technologies, Richard Feynman, Richard Feynman, risk tolerance, risk-adjusted returns, risk/return, Robert Shiller, Robert Shiller, shareholder value, Sharpe ratio, short selling, South Sea Bubble, Stephen Hawking, systematic trading, the scientific method, Thomas L Friedman, too big to fail, transaction costs, upwardly mobile, value at risk, Vanguard fund, volatility arbitrage, William of Occam

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

The Theory That Would Not Die: How Bayes' Rule Cracked the Enigma Code, Hunted Down Russian Submarines, and Emerged Triumphant From Two Centuries of Controversy by Sharon Bertsch McGrayne

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

bioinformatics, British Empire, Claude Shannon: information theory, Daniel Kahneman / Amos Tversky, double helix, Edmond Halley, Fellow of the Royal Society, full text search, Henri Poincaré, Isaac Newton, John Nash: game theory, John von Neumann, linear programming, meta analysis, meta-analysis, Nate Silver, p-value, placebo effect, prediction markets, RAND corporation, recommendation engine, Renaissance Technologies, Richard Feynman, Richard Feynman, Richard Feynman: Challenger O-ring, Ronald Reagan, speech recognition, statistical model, stochastic process, Thomas Kuhn: the structure of scientific revolutions, traveling salesman, Turing machine, Turing test, uranium enrichment, Yom Kippur War

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

algorithmic trading, asset allocation, automated trading system, backtesting, Black-Scholes formula, Brownian motion, business process, continuous integration, corporate governance, discrete time, distributed generation, fixed income, Flash crash, housing crisis, implied volatility, incomplete markets, linear programming, mandelbrot fractal, market friction, market microstructure, martingale, Menlo Park, p-value, pattern recognition, performance metric, principal–agent problem, random walk, risk tolerance, risk/return, short selling, statistical model, stochastic process, stochastic volatility, transaction costs, value at risk, volatility smile, Wiener process

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 specific 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 profits; these authors compared order flow 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

Albert Einstein, algorithmic trading, banking crisis, barriers to entry, Basel III, battle of ideas, Bernie Madoff, Big bang: deregulation of the City of London, Black Swan, Branko Milanovic, Bretton Woods, BRICs, business climate, call centre, carried interest, Cass Sunstein, Clayton Christensen, collapse of Lehman Brothers, conceptual framework, corporate governance, credit crunch, Credit Default Swap, crony capitalism, Deng Xiaoping, don't be evil, double helix, energy security, estate planning, experimental subject, financial deregulation, financial innovation, Flash crash, Frank Gehry, Gini coefficient, global village, Goldman Sachs: Vampire Squid, Gordon Gekko, Guggenheim Bilbao, haute couture, high net worth, income inequality, invention of the steam engine, job automation, joint-stock company, Joseph Schumpeter, knowledge economy, knowledge worker, linear programming, London Whale, low skilled workers, manufacturing employment, Mark Zuckerberg, Martin Wolf, Mikhail Gorbachev, Moneyball by Michael Lewis explains big data, NetJets, new economy, Occupy movement, open economy, Peter Thiel, place-making, Plutocrats, plutocrats, Plutonomy: Buying Luxury, Explaining Global Imbalances, postindustrial economy, Potemkin village, profit motive, purchasing power parity, race to the bottom, rent-seeking, Rod Stewart played at Stephen Schwarzman birthday party, Ronald Reagan, self-driving car, short selling, Silicon Valley, Silicon Valley startup, Simon Kuznets, Solar eclipse in 1919, sovereign wealth fund, stem cell, Steve Jobs, The Spirit Level, The Wealth of Nations by Adam Smith, Tony Hsieh, too big to fail, trade route, trickle-down economics, Tyler Cowen: Great Stagnation, wage slave, Washington Consensus, winner-take-all economy

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

Understanding Sponsored Search: Core Elements of Keyword Advertising by Jim Jansen

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

AltaVista, barriers to entry, Black Swan, bounce rate, business intelligence, butterfly effect, call centre, Claude Shannon: information theory, complexity theory, correlation does not imply causation, en.wikipedia.org, first-price auction, information retrieval, inventory management, life extension, linear programming, megacity, Nash equilibrium, Network effects, PageRank, place-making, price mechanism, psychological pricing, random walk, Schrödinger's Cat, sealed-bid auction, search engine result page, second-price auction, second-price sealed-bid, sentiment analysis, social web, software as a service, stochastic process, telemarketer, the market place, The Present Situation in Quantum Mechanics, the scientific method, The Wisdom of Crowds, Vickrey auction, yield management

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

accounting loophole / creative accounting, agricultural Revolution, barriers to entry, cognitive bias, David Ricardo: comparative advantage, Dean Kamen, Donald Trump, double entry bookkeeping, en.wikipedia.org, Ernest Rutherford, experimental economics, financial innovation, informal economy, interchangeable parts, invention of radio, invention of the printing press, invisible hand, James Watt: steam engine, Jean Tirole, John Harrison: Longitude, Joseph Schumpeter, linear programming, market bubble, market design, mutually assured destruction, Nash equilibrium, new economy, open economy, pirate software, placebo effect, price discrimination, profit maximization, rent-seeking, Richard Stallman, Silicon Valley, Skype, slashdot, software patent, the market place, total factor productivity, trade liberalization, transaction costs, Y2K

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

business intelligence, business process, cellular automata, cloud computing, complexity theory, conceptual framework, continuous integration, data acquisition, domain-specific language, Douglas Hofstadter, Fellow of the Royal Society, finite state, Firefox, follow your passion, Frank Gehry, general-purpose programming language, HyperCard, information retrieval, iterative process, John von Neumann, linear programming, loose coupling, Mars Rover, millennium bug, NP-complete, Paul Graham, performance metric, QWERTY keyboard, RAND corporation, randomized controlled trial, Renaissance Technologies, Silicon Valley, slashdot, software as a service, software patent, sorting algorithm, Steve Jobs, traveling salesman, Turing complete, type inference, Valgrind, Von Neumann architecture, web application

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

Al Roth, Albert Einstein, Andrew Wiles, Brownian motion, cognitive dissonance, Columbine, experimental economics, fear of failure, Henri Poincaré, invisible hand, Isaac Newton, John Conway, John Nash: game theory, John von Neumann, Kenneth Rogoff, linear programming, lone genius, market design, medical residency, Nash equilibrium, Norbert Wiener, Paul Erdős, prisoner's dilemma, RAND corporation, Ronald Coase, second-price auction, Silicon Valley, Simon Singh, spectrum auction, The Wealth of Nations by Adam Smith, Thorstein Veblen, upwardly mobile

“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

3D printing, additive manufacturing, affirmative action, Airbnb, AltaVista, Amazon Web Services, autonomous vehicles, Ayatollah Khomeini, barriers to entry, Berlin Wall, Bernie Sanders, bitcoin, blockchain, business process, call centre, centre right, Clayton Christensen, clean water, cloud computing, corporate social responsibility, crowdsourcing, David Brooks, demand response, demographic dividend, demographic transition, Deng Xiaoping, Donald Trump, Erik Brynjolfsson, failed state, Fall of the Berlin Wall, Ferguson, Missouri, first square of the chessboard / second half of the chessboard, Flash crash, game design, gig economy, global supply chain, illegal immigration, immigration reform, income inequality, indoor plumbing, Internet of things, invention of the steam engine, inventory management, Jeff Bezos, job automation, John von Neumann, Khan Academy, Kickstarter, knowledge economy, knowledge worker, land tenure, linear programming, low skilled workers, Lyft, Mark Zuckerberg, Maui Hawaii, Menlo Park, Mikhail Gorbachev, mutually assured destruction, pattern recognition, planetary scale, pull request, Ralph Waldo Emerson, ransomware, Ray Kurzweil, Richard Florida, ride hailing / ride sharing, Robert Gordon, Ronald Reagan, Second Machine Age, self-driving car, shareholder value, sharing economy, Silicon Valley, Skype, smart cities, South China Sea, Steve Jobs, TaskRabbit, Thomas L Friedman, transaction costs, Transnistria, urban decay, urban planning, Watson beat the top human players on Jeopardy!, WikiLeaks, women in the workforce, Y2K, Yogi Berra

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

discrete time, distributed generation, fear of failure, Fermat's Last Theorem, Isaac Newton, Jacquard loom, Jacquard loom, John von Neumann, linear programming, linked data, Menlo Park, probability theory / Blaise Pascal / Pierre de Fermat, Richard Feynman, sorting algorithm, stochastic process, Turing machine

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.