Geir Dahl                     For English text: click here

    Professor i matematikk
    Center of Mathematics for Applications CMA, Universitetet i Oslo.
    Adresse : CMA c/o 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 Curriculum Vitae, med full publikasjonsliste, finnes her: CV

    To polyedre og GD

Veiledning Master:

Her er informasjon om Master studier innen Kombinatorisk Optimering og Lineær Algebra. Ta gjerne kontakt med undertegnede for mer informasjon! Her er en liste over mine nåværende og tidligere Ph.D. og Master studenter. Oppgavetitlene kan indikere mulige områder for Master oppgaver.
  • 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)
  • Tore Langedal Endestad: "Topologisk ordning og optimale studieplaner"
  • Anders N. Wik: "Lineær optimering og geometri" (2006)
  • Torunn Hegna: "DNA, Markov modeller og optimering." (2006)
  • Alf Krogrud: "Minimum kutt problemet og anvendelser."
  • 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)
  • Deniza Helic-Kavara: "Lineær algebra i økonomi"
  • 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 heltalls og kombinatorisk optimering. Lineær algebra: kombinatorisk matrise teori. 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, bl.a. her ved UiO, og miljøer i USA, Tyskland og Portugal.

Noen artikler:

  • 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.
  • M.O. Ball, G. Dahl, and T. Vossen, " Matchings in Connection with Ground Delay Program Planning". 2006. Submitted.
  • 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 and T. Flatberg, ``Reconstructing (0,1)-matrices from projections using integer programming''. To appear in Computational Optimization and Applications.
  • 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 B. Johannessen, ``The 2-path network design problem'', Technical report, 2000.
  • 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, "Nodes, edges, triangles and convex hulls". May 2000. (Submitted.)
  • 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:

  • 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).

    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

    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 kan vi anbefale Harvey Greenberg (University of Boulder, Colorado) sin hjemmeside: Her finner du bl.a.:
  • Ordliste i optimering
  • Et kort kurs i lineær programmering
  • Myter og moteksempler i optimering

    Se også Frequently Asked Questions: lineær programmering

    Hva kan optimering brukes til i praksis? Det kan brukes til å formulere (matematisk) mange praktiske problemer og deretter løse dem. J.E. Beasley (London) har samlet mange eksempler på slike problemer fra ulike bransjer som finans, olje, distribusjon etc.:

  • Lineær optimering - eksempler og formuleringer.

    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.

    En annen populær Web side er Michael Trick's Operations Research Page.

    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 matematikk for ungdom er Kristina og Elins matte-tips for ungdom

    Oppdatert Aug. 2007, GD