Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Introduction Read chapter Read first chapter

2018 | OriginalPaper | Chapter

7. Advanced Techniques

Author : Serge Kruk

Published in: Practical Python AI Projects

Publisher: Apress

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In this chapter I cover some of the tricks optimizers have developed over the years to twist models and cajole solvers into providing solutions for problems that do not easily fit the Procrustean rules of mathematical optimization.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Classic Mixed Models
Footnotes
1
The expression column generation stemmed, in the minds of optimizers, as literal-minded as ever, from looking at the set of constraints as a matrix.
 
2
The interested reader should look up “reduced cost” and “column generation of the cutting stock” to pursue these matters.
 
3
Optimizers working in engineering or applied mathematics traditionally minimize convex functions. There is a whole area of research appropriately called convex analysis devoted to the theory of such problems. In contrast, optimizers in business usually maximize concave functions. The theory is the same, but everything is upside down. Maybe we should call one group the optimizers and the other the pessimizers?
 
4
Yet another example of the sadly unimaginative naming tradition of optimizers. Maybe this explains it. My Ph.D. advisor, said, only half in jest: “Do not name your algorithms with interesting names if you ever want them to be known by your name.” The implication was that if one names his algorithms Alg-1 and Alg-2 or something equally pedestrian, colleagues will have no choice but to refer to them as Smith-star or Jonesrevised. Alas, such hope at posterity is belied by the use of SOS2 and other mutts of the same ilk.
 
5
Though it is possible to model such constraints, it rarely makes much sense for continuous variables.
 
6
From res (genitive rei), Latin for object. The unusually creative nomenclature is due not to optimizers but to computer scientists working in the related (some would say adversarial) field of constraint programming.
 
7
The interested reader needs to research the branch-and-bound technique of integer programming.
 
8
Mathematics of Operations Research, the umbrella title for the topics of this book.
 
9
And priceless during the inevitable discussions with staff complaining vociferously that their preferences were not met. A modeler’s work is incomplete until the user accepts the solution.
 
10
Think NBA if you are US American, NHL if Canadian, ARL if Australian, or EPL if you are the colonizer of the previous three.
 
11
For the theoretically-minded, the primal-dual gap is smaller; optimality detection is easier.
 
12
Actually, even with deep internal knowledge, it may be near impossible to tell. Trying the approach to see if it works is orders of magnitude easier than reading the entrails of current integer solvers. Written in C, or worse C++, they have layers upon layers of complex cut generation routines with subtle interactions, not to mention cruft accumulated over years of development and debugging.
 
13
A rook attacks any piece in the same column or row, no matter the distance.
 
14
I have run this code on over 20,000 puzzles. In most cases, the model runs in a small fraction of a second; occasionally it will take a few seconds.
 
15
Raymond M. Smullyan, The Lady or the Tiger, and Other Logic Puzzles (Mineola, New York: Dover Publications, 2009).
 
16
In general, for integer programs, it is very difficult to find all solutions, but it is possible for many practical cases.
 
17
I believe the tradition started with Dennis Ritchie and Unix as simplifying medication against the Multics headache-inducing complexities.
 
Metadata
Title
Advanced Techniques
Author
Serge Kruk
Copyright Year
2018
Publisher
Apress
Book
Practical Python AI Projects

Print ISBN: 978-1-4842-3422-8

Electronic ISBN: 978-1-4842-3423-5

Copyright Year: 2018

DOI
https://doi.org/10.1007/978-1-4842-3423-5_7

Premium Partner

    Image Credits