Beskjeder
Then the exam results are published, and I hope (most of) you are pleased with the results. The solutions to the exam may be found at this webpage.
As mentioned, the results were very good, so many have worked very well in this course. The level of difficulty of the exam is perhaps a bit higher than previous years, but, in the corrections, we did some slight compensation for this, especially in the last three questions.
I wish everyone a nice summer! And good luck in your further studies! Maybe some of the things you learned here will be useful.
Best regards, Geir
I hope you were pleased with the exam questions, and feel that you could do your best.
The exam is now corrected and results sent to the faculty, so they will be published very soon. Then I will put the exam solutions on the course page, along with some comments. But I can already now say that the results were very good!
We finished the lectures/classes today.
Some advice for exam preparations: (i) Go carefully through the lecture notes, and use the book as needed, (ii) work on previous exercises (see webpage, also previous year) and in particular previous exams; they are found under "Oppgaver", for a number of years, with solution.
There will not be exam questions on the interior point method for LP.
During the exam I will come by ca 1 hour after the start, in case there are questions. So it is a good idea to read through all the questions initially, and ask me if there are unclear points.
I hope you have liked the course/topic, and thanks to the rather constant group that followed the lectures, and participated actively.
Good luck to you all in the preparations and on the exam!
We continued with convexity, and finished the syllabus on 4 Monday. Also, we worked on exercises, a previous exam (see plan) on network flows, and then the remaining exercises in the convexity notes.
In the final week I will do some repetition and suggest how to prepare for the exam. You can ask questions on all topics in the course. Maybe/probably we also look at some exercises.
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!