Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben

2016 | Buch

Preliminaries Kapitel lesen Erstes Kapitel lesen

Linear and Integer Programming Made Easy

verfasst von: T. C. Hu, Andrew B. Kahng

Verlag: Springer International Publishing

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

This textbook provides concise coverage of the basics of linear and integer programming which, with megatrends toward optimization, machine learning, big data, etc., are becoming fundamental toolkits for data and information science and technology. The authors’ approach is accessible to students from almost all fields of engineering, including operations research, statistics, machine learning, control system design, scheduling, formal verification and computer vision. The presentations enables the basis for numerous approaches to solving hard combinatorial optimization problems through randomization and approximation. Readers will learn to cast various problems that may arise in their research as optimization problems, understand the cases where the optimization problem will be linear, choose appropriate solution methods and interpret results appropriately.

Inhaltsverzeichnis

Frontmatter
1. Preliminaries
Abstract
This chapter provides a brief linear algebra “refresher” and covers notation and some matrix properties that will be used throughout this book.
T. C. Hu, Andrew B. Kahng
2. Introduction
Abstract
We will now explore the basics of linear programming. In this chapter, we will go through several basic definitions and examples to build our intuition about linear programs. We will also learn the ratio method, which we will find useful in solving certain linear programs.
T. C. Hu, Andrew B. Kahng
3. Dimension of the Solution Space
Abstract
In this chapter, we will discuss solution spaces, convex sets and convex functions, the geometry of linear programs, and the theorem of separating hyperplanes. We will apply what we cover in this chapter to build our understanding of the Simplex Method, duality theory, and other concepts in subsequent chapters.
T. C. Hu, Andrew B. Kahng
4. Introduction to the Simplex Method
Abstract
In this chapter, we will learn the Simplex Method, which is a widely used technique for solving linear programs. Even though the notation can be a bit daunting, the technique is actually quite simple. Just keep in mind that the Simplex Method essentially involves iterative application of the ratio test (which you already know) and the pivot operation (which we are about to cover).
T. C. Hu, Andrew B. Kahng
5. Duality and Complementary Slackness
Abstract
In this chapter, we will develop the concept of duality, as well as the related theorem of complementary slackness which not only tells us when we have optimal solutions, but also leads us to the Dual Simplex Method.
T. C. Hu, Andrew B. Kahng
6. Revised Simplex Method
Abstract
In this chapter, we will learn about a method that is mathematically equivalent to the Simplex Method but which can exploit sparsity of the constraint matrix A to run with greater computational efficiency.
T. C. Hu, Andrew B. Kahng
7. Column Generating Technique
Abstract
In this chapter, we shall discuss the most important computational technique of solving a large linear program. If a linear program has a very large number of columns (variables), perhaps too many to write down, we can use the column generating technique to obtain the optimum solution. The point is that entries of the constraint matrix are not random numbers. For every linear program, there is a special structure which is implicitly given in the matrix. By exploring this special structure, we can solve a large linear program with infinitely many columns.
T. C. Hu, Andrew B. Kahng
8. The Knapsack Problem
Abstract
We now turn to the subject of integer linear programming, or integer programming for short. integer programming, which permits non-integer values of the solution variables, is known to be “easy” in the sense of having known algorithms with worst-case runtime that is polynomial in the size of the problem instance. By contrast, integer programming (as well as the hybrid known as mixed integer linear programming) requires that at least some solution variables have their values restricted to be integers. The problem then becomes “hard”: there is no known algorithm that guarantees a worst-case runtime that is polynomial in the instance size.
T. C. Hu, Andrew B. Kahng
9. Asymptotic Algorithms
Abstract
Consider an integer program
$$ \begin{array}{ll}\kern2em \min \hfill & z={x}_1+{x}_2+{x}_3+{x}_4\hfill \\ {}\mathrm{subject}\;\mathrm{t}\mathrm{o}\hfill & \left[\begin{array}{c}\hfill 3\hfill \\ {}\hfill 1\hfill \end{array}\right]{x}_1 + \left[\begin{array}{c}\hfill 1\hfill \\ {}\hfill 3\hfill \end{array}\right]{x}_2 + \left[\begin{array}{c}\hfill 2\hfill \\ {}\hfill 1\hfill \end{array}\right]{x}_3 + \left[\begin{array}{c}\hfill 1\hfill \\ {}\hfill 2\hfill \end{array}\right]{x}_4 = \left[\begin{array}{c}\hfill 11\hfill \\ {}\hfill 11\hfill \end{array}\right],\hfill \\ {}\hfill & {x}_j\ge 0,\kern0.5em \mathrm{integers}.\hfill \end{array} $$
T. C. Hu, Andrew B. Kahng
10. The World Map of Integer Programs
Abstract
Integer programs are very hard to solve. Even the knapsack problem, one of the simplest integer programs, is NP-complete. In order to solve this problem, most people would use the dynamic programming-type algorithm of Gilmore and Gomory. This algorithm is pseudo-polynomial and has time complexity O(nb), where b is the weight-carrying capacity of the knapsack. The knapsack problem can also be solved using Landa’s algorithm, as we saw in Sect. 8.​2. Landa’s algorithm is also pseudo-polynomial and has time complexity O(nw 1), where w 1 is the weight of the best item.
T. C. Hu, Andrew B. Kahng
11. Linear and Integer Programming in Practice
Abstract
Ultimately, we learn about linear programming and integer programming because we wish to solve real-world problems using these techniques. In this chapter, we first discuss how problems can be formulated as linear and integer programs. We then give example formulation techniques that go well beyond the conversions used to obtain equivalent formulations in Section 4.​1. Last, we note several formats in which linear and integer programs are commonly expressed so that modern solver codes can be applied to obtain solutions. Many more examples and exercises are given at this book’s website, http://​lipme.​org.
T. C. Hu, Andrew B. Kahng
Backmatter
Metadaten
Titel
Linear and Integer Programming Made Easy
verfasst von
T. C. Hu
Andrew B. Kahng
Copyright-Jahr
2016
Electronic ISBN
978-3-319-24001-5
Print ISBN
978-3-319-23999-6
DOI
https://doi.org/10.1007/978-3-319-24001-5

Neuer Inhalt

    Bildnachweise