Geir Dahl                     For English text: click here


    Professor i matematikk
    Matematisk institutt,
    Universitetet i Oslo.

    Adresse : Matematisk inst., Postboks 1053 Blindern, NO-0316 Oslo, NORWAY.
    Kontor : Matematikkbygget (NHA hus) rom 1029
    Kontortelefon: 22 85 58 35
    Fax : 22 85 43 49
    Email : geird@math.uio.no

    Min CV, finnes her: CV

    To polyedre og GD

Veiledning Master:

Kombinatorisk Optimering og Lineær Algebra:  her er informasjon om Master studier i Matematikk eller Anvendt Matematikk, spesialisering Kombinatorisk optimering og lineær algebra.  Ta gjerne kontakt  for mer informasjon!

Her er en liste over mine tidligere Master og Ph.D. studenter. Oppgavetitlene kan indikere mulige områder for Master oppgaver.

  • Torkel Haufmann: "On Completely Positive Matrices" (2011)
  • Morten Helgesen: "On solving the inverse problem of intensity modulated radiation therapy" (2011)
  • Andreas Brandsæter: "Optimale randbetingelser for det diskrete Laplace-problemet" (2011)
  • Are Kaspersen: "Financial contagion: Robustness of financial network structures" (2011)
  • Ragnhild Nyhavn: "Combinatorial Feature Optimization using Multi-objective Evolutionary Algorithms applied to a Biological Warfare Classification Problem" (2010)
  • Jon Marius Venstad: "System optimum vs. user equilibrium in static and dynamic traffic routing" (2008)
  • Andreas Huse Kebede: "Trafikktilordning og optimering", 2008
  • Mohammad Ali Norozi: "Information retrieval models and relevancy ranking", 2008
  • Ph.D Truls Flatberg: "Majorization and optimization related to graphs and (0,1)-matrices" (2004)
  • Ph.D Njål Foldnes: "Polyhedra and algorithms for some knapsack problems and hop-constrained paths" (2004)
  • Aizan Magomadova: "Lineær optimering i et algoritmisk perspektiv" (2009)
  • Torunn Hegna: "DNA, Markov modeller og optimering." (2006)
  • Anders N. Wik: "Lineær optimering og geometri" (2006)
  • Stein Grongstad: "Lineær approksimasjon og lineær optimering" (2006)
  • Bjørn Austenaa: "Lineær optimering og billedanalyse" (2006)
  • Bjørn Songe-Møller: "Kvadratisk optimering med anvendelser" (2005)
  • Anders Breivik: "Trafikkoptimering i satelittsystemer" (2003)
  • Kristin Tolstad Uggen: "Transportproblemet for kostnadsmatriser med monotont økende rader" (2002)
  • Lars Duvaas: "Visualisering av grafalgoritmer" (2002)
  • Mikkel Lier: "Kuratowskis teorem og planaritetstesting" (2001)
  • Bjarne Johannessen: "An integer programming approach to a network design problem" (2000)
  • Bjørnar Realfsen: "Kombinatorisk optimering og approksimasjon av kurver" (1998)
  • Alice Fadnes: "Kombinatorisk optimering anvendt på støyfiltrering av bilder" (1997)
  • Per Johan Brun: "Optimal utforming av sykeloverdekninger i nettverk i telekommunikasjon" (1996)
  • Bjørnar Elgetun: "Optimization of response from 2D arrays for medical ultrasound" (1996)
  • Bjørn Sigurd Benestad Johansen: "Planare grafer" (1993)

Undervisning:

Jeg er involvert i undervisning i optimering og lineær algebra. Her er våre kurs i disse områdene:
Ta gjerne en titt på Noen forelesningsnotater:

Forskning:

Fagområder: Matematisk optimering: spesielt kombinatorisk optimering. Lineær algebra: kombinatorisk matriseteori.

Jeg arbeider med polyedrisk kombinatorikk som er bruk av lineær programmering og teori for lineære ulikheter (konveks analyse) for å studere og utvikle effektive algoritmer for kombinatoriske optimeringsproblemer (typisk problemer i grafer og nettverk). I lineær algebra arbeider jeg med studier av polyedre knyttet til bl.a. stokastiske matriser og majorisering. Jeg jobber også med optimeringsproblemer i tilknytning til anvendelser i telekommunikasjon og billedanalyse. Arbeider sammen med ulike miljøer ( i Norge og i utlandet).

Noen artikler:

  • R.A.Brualdi, G.Dahl, ``An extension of the polytope of doubly stochastic matrices'', Linear and Multilinear Algebra, 61 (3) (2013), p.393--408.

  • G. Dahl, ``Martingale matrix classes and polytopes'', Linear Algebra and its Appl. , 437(7), p. 1722-1733.

  • G. Dahl, ``A matrix-based ranking method with application to tennis'', Linear Algebra and its Appl., 437 (2012), 26--36.

  • R.A. Brualdi, G.Dahl, ``Majorization classes of integral matrices'', Linear Algebra and its Appl., 436 (2012), 802--813.

  • G.Dahl, ``Polytopes related to interval vectors and incidence matrices'', Linear Algebra and Its Appl., Vol. 435 (11), p.~2955--2960, 2011,

  • G.Dahl, ``Majorization permutahedra and (0,1)-matrices''. Linear Algebra and its Appl., Volume 432, Issue 12, 1, July 2010, Pages 3265-3271.

  • G.Dahl, H.Minken, ``A note on permutations and rank aggregation'', Mathematical and computer modelling , 2010 ;Volum 52.(1-2) p. 380-385

  • G.Dahl, "Disjoint congruence classes and a timetabling application." Discrete Applied Mathematics, 2009 ;Volume 157. s. 1702-1710.

  • G.Dahl, "Permutation matrices related to Sudoku". Linear Algebra and its Appl., Volume 430, Issues 8-9, 15 April 2009, Pages 2457-2463.

  • M.O. Ball, G. Dahl, and T. Vossen, "Matchings in Connection with Ground Delay Program Planning". Networks, 2009 ;Volum 53.(3) p. 293-307.

  • G.Dahl, "Transportation matrices with staircase patterns and majorization", Linear Algebra and its Applications, Volume 429, Issue 7, 1 October 2008, Pages 1840-1850.

  • G. Dahl and T. Flatberg, ``Reconstructing (0,1)-matrices from projections using integer programming''. Computational Optimization and Applications, (2009) 42: 141--154.

  • G. Dahl, "Combinatorial properties of Fourier-Motzkin elimination", Electronic Journal of Linear Algebra, 16 (2007), 334--346.

  • G. Dahl and T. Flatberg, "An Integer Programming Approach to Image Segmentation and Reconstruction Problems". In Geometric Modelling, Numerical Simulation, and Optimization: Applied Mathematics at SINTEF: Springer Publishing Company 2007, p.461-481.

  • G. Dahl, ``Majorization and distances in trees''. Networks, Vol. 50 (Issue 4) 2007, 251--257.

  • G. Dahl, ``A note on a parameter relating traffic equilibria and system optimal routing'', Applied Mathematics and Computation, 191 (2007) 445-450.

  • R.A. Brualdi and G. Dahl, ``The Bruhat shadow of a permutation matrix''. In ``Mathematical papers in honour of Eduardo Marques de Sa'', Universidade de Coimbra, Textos de Matematica, Departamento de Matematica, 2006. ISBN 978-972-8564-43-8.

  • G. Dahl and H. Minken, "Methods based on discrete optimization for finding road network rehabilitation strategies", 2006, To appear in Computers and Operations Research.

  • G. Dahl, J.M. Leinaas, J. Myrheim, E. Ovrum, "A tensor product matrix approximation problem in quantum physics". Linear Algebra and Its Applications Vol. 420 (2007) 711-725. (Technical report, Dept.of Math./CMA,University of Oslo, Pure Mathematics No. 3, ISSN 0806--2439 February 2006.)

  • G. Dahl and N. Foldnes, ``LP based heuristics for the multiple knapsack problem with assignment restrictions''. Annals of Operations Research, Volume 146, Number 1 (September), 2006, p. 91--104.

  • R.A. Brualdi and G. Dahl, ``Constructing (0,1)-matrices with given line sums and certain fixed zeros''. In Advances in Discrete Tomography and Its Applications, Eds.: Herman, G.T., Kuba, A. Birkhauser, Boston (2007).

  • R.A. Brualdi and G. Dahl, ``Matrices of zeros and ones with given line sums and a zero block'', Electronic Notes in Discrete Mathematics, Vol. 20 (2005), 83--97.

  • G. Dahl and T. Flatberg, ``A remark concerning graphical sequences'', Discrete Mathematics, Volume 304, Issues 1-3, 28 November 2005, Pages 62-64.

  • G. Dahl and T. Flatberg, ``Optimization and Reconstruction of hv-convex (0,1)-matrices'', Discrete Applied Mathematics, 151 (2005), 93-105. (Prelim. version published in Electronic Notes in Discrete Mathematics, Volume 12, March 2003).

  • G. Dahl, D. Huygens, A.R. Mahjoub and P. Pesneau, "On the k edge-disjoint 2-hop-constrained paths polytope" Oper. Res. Letters, 2006;34(5):577-582.

  • G. Dahl, ``A method for approximating symmetrically reciprocal matrices by transitive matrices'', Linear Algebra and Its Applications, Vol. 403 (2005), 207--215.

  • G. Dahl, L. Gouveia and C. Requejo, ``On formulations and methods for the hop-constrained spanning tree problem'', In Handbook of Optimization in Telecommunications, Eds. P.M. Pardalos and M.G.C. Resende. Springer, 2006

  • G. Dahl, ``Tridiagonal doubly stochastic matrices'', Linear Algebra and Its Applications, Vol. 390 (2004), 197-208.

  • G. Dahl, N. Foldnes and L. Gouveia, ``A note on hop-constrained walk polytopes''. To appear in Operations Research Letters.

  • G. Dahl, ``A note on linear discrepancy'', 2003. Electronic Journ. of Linear Algebra, Vol. 10 (2003), 77--80.

  • R.A. Brualdi and G. Dahl, ``Matrices of zeros and ones with given line sums and a zero block'', Linear Algebra and Its Applications, Vol. 371 (2003), 191--207.

  • G. Dahl, ``The doubly graded matrix cone and Ferrers matrices'', Linear Algebra and Its Applications 368 (2003), 171--190.

  • G. Dahl and N. Foldnes, ``Complete description of a class of knapsack polytopes'', (To appear in Operations Research Letters), 2002.

  • G. Dahl and T. Flatberg, ``Some constrained partitioning problems and majorization'', (To appear in European Journ. of Operational Research), 2002.

  • G. Dahl and B. Johannessen, ``The 2-path network problem'', Networks 43, No.3, 190-199 (2004).

  • G. Dahl and L. Gouveia, ``On the directed hop-constrained shortest path problem'', Operations Research Letters) 32 (2004) 15-22.

  • R.A. Brualdi and G. Dahl, ``Majorization-Constrained Doubly Stochastic Matrices'', Linear Algebra and Its Applications, Vol.361, 75--97, 2003.

  • G. Dahl, "Principal majorization ideals and optimization". Nov. 2000. (Linear Algebra and Its Applications, Vol.331, 113--130, 2001.)

  • G. Dahl, "Majorization polytopes", Linear Algebra and Its Applications Vol. 297, 157--175, 1999.

  • G. Dahl, "A note on diagonally dominant matrices". (To appear in Linear Algebra and Its Applications)

  • G. Dahl, "Matrix majorization". ( Linear Algebra and Its Applications, Vol. 288, 53--73, 1999.)

  • G. Dahl, G. Storvik and A. Fadnes, "Large-scale integer programs in image analysis". Operations Research, Vol.50 (2002), No.3, 490--500.

  • G. Dahl, "Notes on polyhedra associated with hop-constrained paths". ( Operations Research Letters Vol.25 (1999) 97--101.)

  • G. Dahl, "The 2-hop spanning tree problem". ( Operations Research Letters, Vol.23 (1998) 21--26.)

  • G. Dahl, "Stable set polytopes for a class of circulant graphs". ( SIAM Journal on Optimization , Vol.9, No.2, 493--503.)

  • G. Dahl, "Majorization, polyhedra and statistical testing problems". ( Linear Algebra and Its Applications, Vol. 272, 205--225, 1998.)

  • G. Dahl, "Polytopes related to some polyhedral norms". ( Operations Research Letters, Vol.22 (1998) 49--54.)

  • G. Storvik and G. Dahl, "Lagrangian based methods for finding MAP solutions for MRF models". November, 96. (To appear in IEEE Transactions on Image Processing )

  • G. Dahl and B. Realfsen, "The cardinality-constrained shortest path problem in 2-graphs". (Networks Vol. 36 (1), 1--8 (2000).)

  • G. Dahl and M. Stoer, "A cutting plane algorithm for multicommodity survivable network design problems". (INFORMS Journal on Computing, 10(1), Winter 1998, 1--11.)

  • G. Dahl, A. Martin and M. Stoer, "Routing through virtual paths in layered telecommunication networks". Oct, 95. (Operations Research, Vol. 47, No. 5, 1999, pp 693--702).

  • G. Dahl and F. Margot, "Weak k-majorization and polyhedra". ( Mathematical Programming, Vol.81 (1998), No.1, 37--53.).

  • G. Dahl, "Polyhedra and optimization in connection with a weak majorization ordering". Dec, 94. ( Lecture Notes in Computer Science, Vol. 920, Integer programming and combinatorial optimization, (Ed. Balas and Clausen), Springer, 1995.)

    Populærvitenskaplige foredrag:

  • Dahl_ILAS2013
  • Matematisk modellering --med vekt på lineær algebra
  • Matematikk og økonomi - fra John Nash (``A Beautiful Mind'') til analyse av trafikk i nettverk
  • Lineær algebra og optimering- matematikk med anvendelser
  • Dobbeltstokastiske matriser, polytoper og majorisering
  • Dobbeltstokastiske matriser, polyedre og transportproblemer
  • Moderne optimering - mer enn å derivere !! Faglig-pedagogisk dag, UiO, 4. jan., 2000
  • Verdens beste håndball-lag? Litt om håndball, kombinatorikk og optimering. Klassebesøk i matematikk (videregående skole).
  • mmc

    Traveling Salesman Problem (TSP):

    .... er å finne korteste rundtur gjennom visse byer. Kanskje er det verdens meste studerte matematiske problem! I alle fall er det en flott webside her som belyser mange sider ved dette problemet, se TSP

    Dagens teorem:

    .... Robin Whitty har laget en nettside om matematikk der mange sentrale teoremer presenteres på en spennende måte, se Theorem of the day

    MATLAB

    Programvare for Optimering

    Mer optimering, på Web etc.:

    Vil du vite mer om optimering (engelsk: "optimization" eller "mathematical programming"), enten det gjelder undervisning, forskning eller jobbmuligheter, finnes det mye informasjon på Web. For eksempel:
  • Ordliste i optimering
  • Frequently Asked Questions: lineær programmering

    • En flott introduksjon til moderne lineær programmering (med mer) er boken "Linear Programming: Foundations and Extensions" av Robert Vanderbei. Bl.a. har han en meget velskrevet gjennomgang av indrepunktsmetoder for LP. Han har laget en Web side knyttet til boken med tillegsstoff, rettelser, C-koder for ulike LP algoritmer, Java program med regneark for simpleksalgoritmen etc. Se

  • LP med R.Vanderbei

    Her finner du en nyttig ordliste i grafteori laget av Bill Cherowitzo. Se

  • Grafteori.

    For deg som har lest en del optimering: her er Myter og moteksempler i optimering

    En rekke pekere til optimering etc. internasjonalt, samt programvare og forskningsmiljøer finnes på Konrad-Zuse-Zentrum für Informationstechnik Berlin. Gå til Department Optimization.

    Ellers finnes det mange internasjonale organisasjoner i matematikk og anvendt matematikk, f.eks. SIAM (Society for Industrial and Applied Mathematics). De gir bl.a. ut bøker og en rekke tidskrifter og arrangerer konferanser i bl.a. optimering, lineær algebra, anvendt matematikk, numerisk analyse osv. Studenter kan også være medlemmer (til redusert pris). Ta en kikk! Se også på SIAM Activity group on Optimization (bl.a. med pekere til optimerings software). En annen stor organisasjon for optimering spesielt er Mathematical Programming Society. De gir ut tidskriftet "Mathematical Programming" og holder ulike konferanser.

    En webside med linker til matematikk (ungdomsskole) er Kristina og Elins matte-tips for ungdom

    Oppdatert April, 2012, GD