Beskjeder
The shortest path problem was lectured by ?yvind R, and he showed algorithms for solving this problem, and examples. It can be viewed as a special case of networks flows, but Dijkstra's or Bellman's algorithms are simpler and faster. Then, I started on the final topic of this course, convexity. Here we use the notes I wrote, see syllabus and resources on this page. Convexity gives a mathematical foundation of optimization, so there are important concepts and results, and we look at some of these (3 weeks).?
You may deliver in Canvas now. Sorry that I opened for submission so late (yesterday morning).?
We finished the material on the MCF, minimum cost network flow problem. Explaining how the simplex algorithm simplifies, and we get bases that correspond to spanning trees. We saw how we computed efficiently corresponding primal (x) and dual (y,z) variables, using a leaf elimination order in the tree. On 24 March I presented special cases of MCF, and the integrality theorem; assignment problem, transportation problem, maximum flow problem. This was not very detailed. Some details on efficiency in the simplex algorithm were skipped (but they are in the notes; not very important). Have a nice Easter holiday later!
Some of you detected an error i Oblig 1/Comp. project 1 solution, exercise c): All the points should be multiplied by 2; this is corrected now. Sorry for this (but most of you got it right anyway!).?
It was a pleasure to see the projects/solutions from many of you, in fact, from all those who had really done some work. Well done!?
Still, a (too) high number delivered blank, or almost blank. I am sure each of you in this category understand that a lot of work is needed to catch up, and be prepared for the exam.?
.. is now published. Deadline 16. April 2025, 14.30
We finished the presentation of the simplex algorithm in matrix version, and discussed some computational issues. Then (week 11) it was on interior point methods for LP. This is based on some topics from multivariable calculus (gradients, Lagrange multiplier method, optimality conditions, and we studied the barrier problem and its optimality conditions: a nonlinear system of equations). An example was shown.?
We have worked on Chapter 5, duality theory. Main results are weak and strong duality theorems. We have seen how this gives bounding procedures and optimality condition, in terms of complementary slack. We also studied the Negative Transpose property and how it implies that the optimal dual solution can be found directly from the optimal primal dictionary. We looked at exercises on this, and on how to find dual problems. Finally we studied briefly the dual simplex algorithm, and started on the matrix version of simplex algorithm; more on this next week.?
We considered degeneracy and methods to handle that. Fundamental theorem of LP. And efficiency of the simplex algorithm, the Klee-Minty problem, pivot rules. We also looked at the geometry of LP/simplex alg. i two and three dimensions, and consider how LP can be used in machine learning/classification problems (optimal near-separation of two points sets). Worked on exercises.?
- Student representatives are: Marie Katrine Ekeberg ?(makatek@math.uio.no) and (lektorprog.) Knut Oddvar Skaug (ko.s@tuta.com). You can contact each of these with suggestions, complaints etc. In fact, the teacher realizes that the course may not be Optimal, so maybe some pivots are needed :)
- So far: After two weeks we have covered the basic stuff: what is LP, applications and simplex algorithm; even with phase I (for finding, if possible, a feasible solution). We also did the geometry of this when there are two variables (see also Vanderbei). You are now familiar with the pivot tools, but don't forget some hand calculations! Also for solving larger problems one may use e.g. Matlab's function linprog., and I showed an example.?
20/1: Vi trenger to studenter som kontaktpersoner for en enkel evaluering: ta imot synspunkt p? opplegget, og ha to m?ter med meg i l?pet av semesteret. Send en email til meg hvis du er interessert! Ellers er notater for LP1 (f?rst uke LP) lagt ut. Vi jobbet ganske mye med eksempler og bruk av pivot-verkt?y (se link). Ellers er Oblig 1 lagt ut, med frist 12 mars.
The text has been published; see main page (resources). The deadline is 12 March, at 14.30.
See also general info on such projects.?
Velkommen til MAT3100 Line?r optimering! Her kan du l?re kjernefeltet innen optimering; det matematiske grunnlaget, algoritmer, og anvendelser! Mye g?y, og nyttig stoff!
Welcome to MAT3100 Linear optimization. Here you can learn the core of optimization; the mathematical basis, algorithms, and applications. Fun, and useful material!