Search Results

This chapter surveys further important techniques for designing fixed-parameter algorithms. These include color-coding, integer linear programming, iterative compression, greedy localization, and graph minor theory. The practical relevance of each technique is also evaluated. From a practical point of view, the two most important techniques are colour-coding and iterative compression.

This chapter examines the use of linear programming in cost minimization efforts in production processes. Most economics have turned to linear programming to explain the convexity of isoquants, explore substitution possibilities among large sets of inputs, and predict substitution possibilities involving new inputs. Simple linear programming problems can be solved by geometric reasoning while more complicated ones can be solved by algebraic methods.

It is well known that in the immediate postwar period game theory was closely associated with (and substantially dependent upon) military patronage from organizations like the RAND Corporation or the Office of Naval Research. In addition, the brand of game theory to emerge through this patronage was substantially different from that presented in von Neumann and Morgenstern’s 1944 book, being focused principally upon the mathematics of the two-person zero-sum game. This chapter seeks to interpret these developments in light of the transition from the “hot war” of World War II to the Cold War, especially the way that the professional and disciplinary concerns of military-funded applied mathematicians (and some mathematical economists) intersected with this new atmosphere of defense reconversion and budgetary consolidation. In this context, more than solving any particular problem, game theory (and the mathematics of the two-person zero-sum game in particular) proved capable of drawing together the heterogeneous activities the mathematicians had performed on behalf of the military – most notably “operations research,” “military worth” assessment, budget programming, and logistics research – under a theoretical framework with at least some academic credibility.

Cold War military needs for cost-effective readiness induced a mathematical construction of rationality while simultaneously binding that rationality with computational reality. In 1947 in an effort to mechanize their planning process, the USAF constituted the Project for the Scientific Computation of Optimum Programs. George Dantzig developed mathematical models and algorithmic solutions for digital computation of an efficient allocation of resources to different USAF activities. In 1948 the Berlin Airlift served as an important prove of concept for Dantzig’s linear programming, but a lack of computational capacity forced Project SCOOP to make do with a sub-optimizing mathematical model. Herbert Simon and colleagues at the Carnegie Institute of Technology, also doing optimizations under military contract, found that their mathematical reach for best decisions exceeded their computational grasp. This chapter narrates the path from this dilemma to Simon’s conceptualizations of bounded rationality and procedural rationality.

This chapter focuses on the relationships between decision problems and their optimisation versions. It shows that, for most problems, the optimal solution can be realised in polynomial time if and only if we can tell whether a solution with a given quality exists. It then explores approximation algorithms for the traveling salesman problem and considers some large families of optimisation problems that can be solved in polynomial time, including linear programming and semidefinite programming. It demonstrates that the duality between MAX FLOW and MIN CUT is no accident — that linear programming problems come in pairs. In addition, the chapter looks at integer linear programming, which can be solved in polynomial time before concluding with a discussion of optimisation problems from a practical point of view.

This chapter offers information on several approaches used for making the winner determination problem (WDP) solvable by putting restrictions on the bid prices. It begins with integer linear programming formulations of WDP in order to get a tractable case for the winner determination problem. The chapter then focuses on another approach that is used for making WDP a combinatorial optimization problem by using the intersection graph of bids. As reported, the latter approach leads to faster algorithms in comparison with the linear programming approach. The chapter further explains how other models such as restricting bid sets or bid values can become suitable methods for showing tractability. Limitations that can hamper the performance of these approaches including economic inefficiencies, incentive problems, and exposure problems.

This chapter considers the finite-dimensional case, which is the case when the marginal probability distributions are discrete with finite support. In this case, the Monge–Kantorovich problem becomes a finite-dimensional linear programming problem; the primal and the dual solutions are related by complementary slackness, which is interpreted in terms of stability. The solutions can be conveniently computed by linear programming solvers, and the chapter shows how this is done using some matrix algebra and Gurobi.

This chapter defines and formulates a combinatorial optimization problem, called the winner determination problem, and examines its complexity properties. A range of alternative mathematical programming models including integer linear programming, weighted stable set in graphs, knapsack, and matching that covers variants of the problem related to particular bidding languages is also discussed. The chapter further highlights inapproximability results, and reviews the approximation algorithm, which is a polynomial time algorithm. It concludes that the problem, which is represented as an integer program, is NP-complete and can be tackled by applying three fundamentally different approaches, which it discusses.

In this chapter, the connection between efficient auctions for multiple, indivisible items and the duality theory of linear programming is investigated. Vickrey auctions are the focus of this investigation as they are efficient auctions well known for their incentive properties. The chapter begins with a description of the basic results for the assignment model that concerns allocations with indivisibilities and defines the combinatorial auction model and pricing equilibria, which is an extension of Walrasian equilibrium. It further discusses an equivalence between the sealed-bid Vickrey auction and pricing equilibrium. The chapter emphasizes that various combinatorial ascending price auctions are incentive compatible if an MP pricing equilibrium is implemented by them. It also discusses the implementation of dual algorithms, the subgradient algorithm, and the primal dual algorithm for solving linear programming problems.

This chapter looks at some of the hardest problems in NP. Most of the NP problems that people considered in the mid-1970s either turned out to be NP-complete or people found efficient algorithms putting them in P. However, some NP problems refused to be so nicely and quickly characterized. Some would be settled years later, and others are still not known. These NP problems include the graph isomorphism, one of the few problems whose difficulty seems somewhat harder than P but not as hard as NP-complete problems like Hamiltonian paths and max-cut. Other NP problems include prime numbers and factoring, and linear programming. The linear programming problem has good algorithms in theory and practice—they just happen to be two very different algorithms.

This chapter focuses on the computation of mixed saddle-point equilibrium policies. In view of the Minimax Theorem, the mixed saddle-point equilibria can be determined by computing the mixed security policies for both players. For 2 x 2 games, the mixed security policy can be computed in closed form using the “graphical method.” After providing an overview of the graphical method, the chapter considers a systematic numerical procedure to find the linear program solution for mixed saddle-point equilibria and the use of MATLAB's Optimization Toolbox to numerically solve linear programs. It then describes a strictly dominating policy and a “weakly” dominating policy before concluding with practice exercises and their corresponding solutions, along with an additional exercise.

This chapter considers the optimal network flow problem, which is a generalization of the optimal assignment problem considered in Chapter 3. In optimal flow problems, one considers a network of cities, or edges, to move a distribution of mass on supply nodes to a distribution of mass on demand nodes. The difference from a standard optimal assignment problem is that the matching surplus associated with moving from a supply location to a demand location is not necessarily directly defined; instead, there are several paths from the supply location to the demand location, among these some yield maximal surplus. Therefore, both the optimal assignment problem and the shortest path problem are instances of the optimal flow problem; these instances are representative in the sense that any optimal flow problem may be decomposed into an assignment problem and a number of shortest path problems. The chapter shows how to easily compute these problems using linear programming.

This chapter examines the emergence of economic cybernetics in the late 1950s and early 1960s as a field closely allied to mathematical economics and econometrics yet peculiar to the Soviet sphere. It also outlines and describes the basics behind the command economy and the coordination problems that the Soviet state and competing schools of orthodox, liberal, and cybernetic economists alike all agreed needed to be addressed and reformed in the early 1960s. A few sources of the organizational dissonance, including heterarchical networks of institutional interests, blat, vertical bargaining, underlying the Soviet command economy and its state administration are also introduced

The only way through the wartime Leningrad siege was a winter ice road across a lake, monitored by a brilliant young Soviet mathematician. Leonid Kantorovich had been brought up in the chaos of post-Czarist Russia, and during his pioneering career invented linear programming to help Soviet industry become more efficient, then worked out mathematical ways to improve the planning of the whole Soviet economy. But this was dangerous work, as Stalin disapproved of economists and cybernetics, had sent many to the gulags, and was trying to run the economy himself, despite all the practical problems of wartime central planning without prices.