Njål Foldnes
Dr. Scient in
mathematics,
University of Oslo.
- mail: njaalf@math.uio.no
- phone:(47)47415950, 22855309
Spring 2005: Currently I am working on the project Computers
in
Science Education at the Centre
of
Mathematics for Applications. In addition I wrote and
produced a play about
mathematics for children, together with my wife Grethe Mo.
- Research Interests :
Polyhedral
Combinatorics, Network Design, Knapsack Problem
PUBLICATIONS:
"LP
based heuristics for the multiple knapsack problem with assignment
restrictions" G.Dahl and N.Foldnes
submitted to Annals of operational research, November 2003.
Abstract:
Starting with a problem in wireless telecommunication, we are led to
study the
multiple knapsack problem with assignment restrictions. This problem is
NP-hard. We consider special cases and their computatiojnal complexity.
We
present both randomized and deterministic LP based algorithms, and show
both
theoretically and computationally their usefulness for large-scale
problems.
Keywords: Multiple knapsack problem, randomized rounding, traffic
routing
"A note on
hop-constrained walk polytopes",
G.Dahl, N.Foldnes and L.Gouveia,
Operations Research Letters, Volume 32, Issue 4,
A hop-constrained walk is a walk with at most $H$ arcs. The cases $H
\leq 3$
have been addressed in Dahl and Gouveia~\cite{dahl}. Here, we consider
the case
$H= 4$. We present an extended formulation for 4-walks and use the
projection
theorem of Balas and Pulleyblank~\cite{pulleyblank} to derive a
complete linear
description of the 4-walk polytope.
Keywords: Complete description, hop-constraints, walk, extended
formulation.
"Complete
description of a class of knapsack polytopes",
G.Dahl and N.Foldnes,
Oper.Res.Letters, Volume 31, Issue 5, Sept 2003
Abstract:
We study the knapsack polytopes that arise whenever the item weights
are of two
types: either of weight 1 or of weight p. A complete linear description
of the
associated integral polytope is given by showing that the system is
totally
dual integral.
Keywords: Complete description; Facets; Knapsack polytope; Totally dual
integral
"The jump
formulation for the hop-constrained minimum spanning tree problem",
G.Dahl, T. Flatberg, N.Foldnes and L. Gouveia
Submitted to Informs Journal of Computing, April 2004
Abstract:
In the hop-constrained minimum spanning tree problem one seeks a
minimum cost
spanning tree such that the path from a specified root node to any node
has
length at most $H$. We introduce a new formulation for this problem,
using
so-called jump inequalities, which we show are facet defining. Compared
with
the best formulations presented in the literature, the new formulation
has the
disadvantage of having a weaker linear programming relaxation, but the
advantage of using fewer variables. As the new formulation includes an
exponentially sized set of jump inequalities, we propose a Lagrangean
relax-and-cut scheme. The computational results are promising,
suggesting that
jump inequalities may play an important role for hop-constrained
network design
problems.
Keywords: Hop-constraints, spanning tree, Lagrangean relaxation.
Fall 2001
Spring 2002
- Working on a paper that gives a
complete description for a special class of knapsack polytopes. A joint
work between me and my supervisor Geir Dahl.
- Moved to new office in
Forskningsparken, room 114.
- Our seminar.
- I presented work on knapsack facets at
IFORS 2002 in
July.
Fall 2002
- Moved on to consider special cases of
multiple knapsack problems. Preliminary results presented at MPS 2002.
- Wrote an essay (in Norwegian) on
the nature of mathematics and the mathematics of nature.
Spring 2003
- I was at the University of Lisbon, visiting prof. Luis Gouveia. Worked on hop-constrained paths.
Fall 2003
- Gave a talk at ISMP 2003. on the hop-constrained path polytopes.
- Got a dog.
- Working on the multiple knapsack problem, and presented this work at INOC 2003.
Spring 2003
- I was at the University of Lisbon, visiting prof. Luis Gouveia. Worked on hop-constrained paths.
Spring 2004
I made it!
· Defended my thesis on march 31 2004. Opponents were Prof. Alexander Martin and Prof. Kaj Holmberg.
· The press release of my thesis (in norwegian) is here.
· My work is also mentioned in Norwegian research magazine, here