The sharpest cut: the impact of Manfred Padberg and his work by Martin Grötschel

By Martin Grötschel

The Sharpest minimize is written in honor of Manfred Padberg, who has made primary contributions to either the theoretical and computational facets of integer programming and combinatorial optimization. This impressive assortment provides contemporary ends up in those components which are heavily hooked up to Padberg's examine. His deep dedication to the geometrical method of combinatorial optimization should be felt all through this quantity; his look for more and more greater and computationally effective slicing planes gave upward push to its name.

The peer-reviewed papers contained listed here are in response to invited lectures given at a workshop held in October 2001 to have fun Padberg's sixtieth birthday. Grouped by means of subject (packing, sturdy units, and ideal graphs; polyhedral combinatorics; basic polytopes; semidefinite programming; computation), the various papers got down to resolve demanding situations set forth in Padberg’s paintings. The e-book additionally exhibits how Padberg's rules on slicing planes have encouraged smooth advertisement optimization software program. furthermore, the quantity incorporates a brief curriculum vitae, a private account of Padberg’s paintings by way of Laurence Wolsey, and an appendix with reflections from Egon Balas, Claude Berge, and Harold Kuhn.

Show description

Read Online or Download The sharpest cut: the impact of Manfred Padberg and his work PDF

Similar linear programming books

Linear Programming and its Applications

Within the pages of this article readers will locate not anything below a unified therapy of linear programming. with out sacrificing mathematical rigor, the most emphasis of the publication is on types and purposes. an important periods of difficulties are surveyed and awarded via mathematical formulations, by way of answer tools and a dialogue of numerous "what-if" eventualities.

Methods of Mathematical Economics: Linear and Nonlinear Programming, Fixed-Point Theorems (Classics in Applied Mathematics, 37)

This article makes an attempt to survey the center matters in optimization and mathematical economics: linear and nonlinear programming, setting apart aircraft theorems, fixed-point theorems, and a few in their applications.

This textual content covers simply matters good: linear programming and fixed-point theorems. The sections on linear programming are founded round deriving tools according to the simplex set of rules in addition to a number of the usual LP difficulties, corresponding to community flows and transportation challenge. I by no means had time to learn the part at the fixed-point theorems, yet i believe it will probably turn out to be valuable to analyze economists who paintings in microeconomic idea. This part offers 4 diversified proofs of Brouwer fixed-point theorem, an explanation of Kakutani's Fixed-Point Theorem, and concludes with an explanation of Nash's Theorem for n-person video games.

Unfortunately, an important math instruments in use by way of economists at the present time, nonlinear programming and comparative statics, are slightly pointed out. this article has precisely one 15-page bankruptcy on nonlinear programming. This bankruptcy derives the Kuhn-Tucker stipulations yet says not anything concerning the moment order stipulations or comparative statics results.

Most most probably, the unusual choice and insurance of subject matters (linear programming takes greater than half the textual content) easily displays the truth that the unique variation got here out in 1980 and in addition that the writer is de facto an utilized mathematician, now not an economist. this article is worthy a glance if you'd like to appreciate fixed-point theorems or how the simplex set of rules works and its purposes. glance in other places for nonlinear programming or newer advancements in linear programming.

Planning and Scheduling in Manufacturing and Services

This booklet makes a speciality of making plans and scheduling functions. making plans and scheduling are varieties of decision-making that play a massive position in so much production and companies industries. The making plans and scheduling capabilities in an organization often use analytical ideas and heuristic how you can allocate its restricted assets to the actions that experience to be performed.

Optimization with PDE Constraints

This ebook provides a contemporary creation of pde restricted optimization. It offers an exact useful analytic therapy through optimality stipulations and a state of the art, non-smooth algorithmical framework. moreover, new structure-exploiting discrete options and big scale, virtually suitable functions are offered.

Extra resources for The sharpest cut: the impact of Manfred Padberg and his work

Example text

V$}, G — {1^2,^3} are connected, then G contains an odd hole. Proof. Let Q be a component of G — {v\, i>2, v$}. We may assume that Q is bipartite (else Q contains an odd hole and we are done); thus the set of nodes of Q splits into stable sets Si and S2. Since each G — {v,•, Vj} is connected, each of the three nodes vk must have a neighbor in Si US?. Hence two of the three nodes, say vi and i>2, must have a neighbor in the same S/. It follows that the subgraph of G induced by Q U {v\, v2} is not bipartite, and so it contains an odd hole.

Mathematical Programming, 52(2):315–357, 1991. S. Schulz. Polytopes and Scheduling. D. thesis. math. de/pub/Preprints/combi/. Technische Universitat Berlin, 1996. [41] Yasuki Sekiguchi. A note on node packing polytopes on hypergraphs. Operations Research Letters, 2(5):243-247, 1983. [42] M. Sol. Column Generation Techniques for Pickup and Delivery Problems. D. thesis, Technische Universitat Eindhoven, 1994. [43] B. Toft. Colouring, Stable Sets and Perfect Graphs. [19], chapter 4, pages 233-288.

Thus consider a block B' of B and an active edge with endnodes s, t in B' and let us prove first the following claim. Claim 1. One of the two nodes s, t is the root of B'. Proof. Assume the contrary and let W be the nodeset of a component of B — {s, t} that does not contain the root of B'. We can also assume that st is chosen among all possible candidates so that | W\ is minimum. 12, property 3. Our choice for s and t ensures that B — {s} and B — {t} are connected. Hence, B — (W U {s}) and B — (W U {t}) are also connected and eventually contain the root of B' if B' / B.

Download PDF sample

Rated 4.00 of 5 – based on 15 votes