Large Scale Optimization

Základní informace

  • Název: Large Scale Optimization: Exact Methods (NOPT059)
  • Předmět bude vyučován v českém nebo anglickém jazyce podle zájmu studentů.
  • Výuka bude probíhat v letním semestru 2024/25.
  • Rozvrh: Přednáška ??? a cvičení ve středu od 15:40 na chodbě S301 na Malé Straně
  • Přednášející: Jakub Bulín

Cíle předmětu

Cílem předmětu je porozumění principů různých optimalizačních metod použitelných na velké instance pocházejících z praxe. Exaktní metody:
  • Lineární programování, dualita, komplementarita
  • Celočíselné lineární programování, větvení a mezí
  • Řezné nadroviny, generování podmínek
  • Generování sloupců, Dantzig-Wolve dekompozice
  • Lagrange relaxace

Zápočet

Zápočet udělen za domácí úkoly, jejichž zadání najdete v gitu. Vytvořte si soukromý klon tohoto repozitáře na fakultním gitlabu a přidejte mě (login: finkj1am) s rolí reporter.

Gurobi

Gurobi is a solver (not only) for solving integer linear programming problems which we will use in the course. Although it is a commercial software, it provides an academic licence for free. For our course, it is sufficient to install Guroby's Python API.

Minimalistic instalation guide

  • Install Python package gurobipy
  • Fill the Academic License Registration and wait for their response
  • Download and unpack Licence tools
  • From the unpacked file run a program grbgetkey. The exact grbgetkey command to run for a specific license is indicated at the bottom of the License Details page (e.g., grbgetkey 253e22f3-...). Warning: Please make sure you are connected to your university network.
If you are validating a home machine, use VPN or SSH to the university.
  • Run the command ssh -D 8888 login@u-pl1.ms.mff.cuni.cz
  • In the internet connection setting of your browser, set SOCKS host to localhost and port 8888.
  • Obtain a licence key from Gurobi's website.
  • Open another terminal to run on your local computer the following commands. $ export https_proxy=socks5://localhost:8888/ $ ./grbgetkey "the licence key"
You can install complete Gurobi optimizer software with other useful tools, but their usage is not necessary in our course. The following links may be useful to install Gurobi. The following links may be useful to learn how to use Gurobi API in Python.