Deepak Rajan
Email: drajan "at" us.ibm.com
Web:
research.ibm.com/people/d/dpkrjn
|
823 Huntingon Drive, |
IBM T.J. Watson Research Center, |
|
Fishkill, NY - 12524
|
19 Skyline Drive, Hawthorne NY - 10532
|
|
(510) 501-5852
|
(914) 784-6046
|
Education
Ph.D University of
California at Berkeley, Dec 2004.
Industrial Engineering and Operations
Research
Minors: Statistics, Computer Science.
Designing capacitated survivable networks: Polyhedral analysis
and algorithms.
A network is said to be survivable if all
demands on the network can be met under the failure of any one of
its edges. We present new models,
study relevant pricing problems and
develop cutting planes that are incorporated in a computationally
efficient algorithm. We also study various
mixed-integer sets and their polyhedra in to develop strong
valid inequalities for the mixed-integer knapsack set.
[PDF]
Dissertation Committee :
Alper
Atamtürk,
Ilan Adler,
Dorit
Hochbaum,
Thomas Henzinger.
M.S University of
California at Berkeley, 2001.
Industrial Engineering and
Operations Research
B.Tech
Indian Institute of Technology - Madras, 1999.
Mechanical Engineering
Employment
Research Staff Member,
Software Tools and Techniques group (Manager: Dr. Philip S. Yu)
IBM T.J. Watson
Research Center, Hawthorne NY, USA
Oct 6, 2004 - present,
full time.
Responsible for carrying out fundamental research in Computer Science
and Operations Research, as well as towards the System S project,
a large-scale distributed stream processing system.
Specifically, I am responsible for the design and development of the
scheduler of the system, as well as dynamic optimization of
query graphs, resource adaptive stream operators, and the development
of power-aware load scheduling techniques.
Previous Research Experience / Professional Training
Student Researcher
University of California at
Berkeley,
Mar 2000 - Sep 2004, part time.
With Alper
Atamtürk,
Mar
2000 - Sep 2004.
General mixed-integer knapsack set.
Developed strong valid inequalities using sequence
independent lifting (in polynomial time) of facets of the restriction with one
continuous and two integer variables.
Capacitated survivable network design.
Proposed a method which introduces slack on directed cycles used as
failure-flow patterns to restore disrupted flow.
Studied pricing problems and developed metric-type
inequalities.
Network design arc-set polyhedra.
Analyzed the optimization problems over arc sets,
developed a linear-time separation algorithm for the
splittable arc-set, and introduced two classes of inequalities for the
unsplittable arc-set.
With
George Shanthikumar, Aug - Dec 2002.
Matroids and transposition increasingness.
Attempted to link deterministic optimization over structured sets
(e.g. matroids) to optimization over these sets for partial stochastic
orders.
Summer Intern
IBM T.J. Watson Research
Center, Jun - Aug 2003, full time.
With Jon Lee and
Samer Takriti.
Unit commitment problem.
Studied a strong relaxation (minimum up/down
constraints) of the unit commitment polytope, and derived the
inequalities that completely defined our relaxation.
With
Gyana Parija, et al.
Fire program analysis.
Explored and implemented many solution strategies that exploited
problem structure and assumptions in data,
considerably reducing problem sizes and solution times.
Student Researcher
Indian Institute of Technology - Madras, Aug 1998 - May 1999,
part time.
With
G.
Srinivasan.
Cutting stock problem.
Developed and implemented an LP-based heuristic that efficiently solves the
1-D problem by crash-starting the LP
using a near-optimal LP relaxation basis, and
then applies a single-pass rounding heuristic.
Professional Affiliations
Institute for Operations Research and the Management Sciences
(INFORMS).
Awards / Fellowships
IBM Invention Achievement Award
First Plateau Award
Dissertation Award,
Informs Technical Section on Telecommunications,
INFORMS, 2006
Honorable Mention.
Judith Liebman
Award,
INFORMS, 2004
Recognizes outstanding student volunteers who have been "moving
spirits" in their universities, their student chapters, and the
Institute.
Best Student Research Presentation,
PRISMS, 2002.
Over 100 participants from seven universities, including
Stanford
University and University of
California at Berkeley.
Regents Block Grant Fellowship,
University of
California at Berkeley, 1999-2000
National Talent Search
Scholarship, India, 1993 - 1998.
One of 750 awarded among applicants from high schools all over India.
Patents
Filed
Method and apparatus for scheduling work in a stream-oriented computer
system.
Method and apparatus for assigning fractional processing nodes to work
in a stream-oriented computer system.
Method and apparatus for assigning candidate processing nodes
in a stream-oriented computer system.
Method and systems for assigning non-continual jobs to candidate
processing nodes in a stream-oriented computer system.
Submitted
Method and apparatus for predicting resource usage of reusable stream
processing elements
Research Interests
My interests broadly lie in the area of optimization, and more
specifically in optimization techniques such as integer programming.
I am also interested in approximation algorithms (esp. applied to
scheduling), computational optimization, and stochastic combinatorial
optimization. Recently, I have been working on power-aware
microprocessor scheduling and on network design problems, and on a
variety of optimization problems in data mining.
Publications
Atamtürk, A. and Rajan, D.
"Partition inequalities for capacitated survivable network design
based on directed p-cycles." To appear in
Discrete Optimization.
[PS]
[PDF]
Rajan, D., and Yu, P. S.
"On temperature-aware scheduling for single-processor systems."
HiPC 2007,
LNCS 4873, 342-355.
[PS]
[PDF]
Rajan, D., and Yu, P. S.
"Temperature-aware scheduling: When is system-throttling good
enough?"
IBM Research Report RC24331, 2007.
[PS]
[PDF]
Lucchese, C., Vlachos, M., Rajan, D., and Yu, P. S.
"Rights Protection of Multidimensional Time-Series Datasets with
Neighborhood Preservation."
To appear in
Proceedings of the 24th International Conference on Data Engineering.
[PDF]
Vlachos, M., Rajan, D., Lucchese, C., and Yu, P. S.
"Ownership Protection of Shape Datasets
with Geodesic Distance Preservation."
To appear in
Proceedings of the 11th International Conference on Extending Database
Technology.
[PDF]
Rajan, D., and Yu, P. S.
"Discovering partial orders in binary data."
Proceedings of the 2006 IEEE International Conference on Data Mining
(ICDM), 2006, 510-521.
[PS]
[PDF]
Rajan, D. and Takriti, S.
"Minimum up/down polytopes of the unit commitment problem with start-up
costs."
IBM Research Report RC23628, 2005.
[PS]
[PDF]
Rajan, D. and Atamtürk, A.
"A directed cycle based column-and-cut generation method for
capacitated survivable network design."
Networks, 43, 201-211, 2004.
[PS]
[PDF]
Atamtürk, A. and Rajan, D.
"On
splittable and unsplittable flow capacitated network-design arc-set
polyhedra."
Mathematical Programming, 92, 315-333, 2002.
[PS]
[PDF]
Rajan, D. and Atamtürk, A.
"Survivable network design : Routing of flows and slacks."
Chapter in
Telecommunications Network Design and Management, 65-81,
Kluwer Academic Publishers, 2002.
[PS]
[PDF]
Atamtürk, A. and Rajan, D.
"A new model for designing survivable networks."
Proceedings of the 10th International Conference on
Telecommunication Systems Modeling and Analysis (ICTSM10), 2002.
[PS]
[PDF]
Rajan, D., and Yu, P. S.
"Temperature-aware scheduling: When is system-throttling good
enough?"
Submitted to
22nd IEEE International Parallel and Distributed Processing Symposium.
[PS]
[PDF]
Dash, S., Lodi, A., and Rajan, D.
"The {-1,0,1} unconstrained QP."
In preparation.
Atamtürk, A. and Rajan, D.
"On the polyhedron of the general mixed-integer knapsack set."
In preparation.
Rajan, D. and Shanthikumar, G.
"On a class of easily solvable combinatorial optimization problems with
stochastic objective." In preparation.
Presentations
Rajan, D., and Yu, P. S.
"Discovering partial orders in binary data,"
The 2006 IEEE International Conference on Data Mining
(ICDM),
Dec 2006, Hong Kong, China.
Atamtürk, A. and Rajan, D.
"Partition inequalities for survivable network design using p-cycles,"
The Eighth INFORMS Telecommunications Conference,
Mar 2006, Dallas, Texas.
IBM T.J. Watson Research Center, Mar 2006, Yorktown Heights, New York.
Rajan, D., Dash, S. and Lodi, A.
"3-State Unconstrained Quadratic Programming,"
INFORMS Annual Meeting, Nov 2005, San Francisco, California.
IBM T.J. Watson Research Center, Nov 2005, Yorktown Heights, New York.
INFORMS International Meeting, Jul 2007, Puerto Rico.
Atamtürk, A. and Rajan, D.
"Metric-type Inequalities for Survivable Network Design using
Directed Cycles,"
INFORMS Annual Meeting, Oct 2004, Denver, Colorado.
IBM T.J. Watson Research Center, Dec 2004, Yorktown Heights, New York.
Atamtürk, A. and Rajan, D.
"Polynomially-Computable Lifting Functions for Two-Variable
Integer Knapsack Inequalities,"
INFORMS Annual Meeting, Oct 2004, Denver, Colorado.
Rajan, D.
"Designing capacitated survivable networks: Polyhedral analysis
and algorithms,"
University of Minnesota,
Apr 2004, Minneapolis, Minnesota.
The Eighth INFORMS Telecommunications Conference,
Mar 2006, Dallas, Texas.
IBM T.J. Watson Research Center, Mar 2006, Yorktown Heights, New York.
Atamtürk, A. and Rajan, D.
"On the knapsack set with one continuous and two integer
variables,"
INFORMS Annual Meeting, Oct 2003, Atlanta, Georgia.
Rajan, D., Lee, J. and Takriti, S.
"The unit commitment problem : A polyhedral study,"
IBM T.J. Watson Research Center, Aug 2003, Yorktown Heights, New York.
INFORMS Annual Meeting, Oct 2003, Atlanta, Georgia.
Rajan, D. and Atamtürk, A.
"A new model for designing survivable networks,"
The 10th International Conference on
Telecommunication Systems Modeling and Analysis (ICTSM10), Oct
2002, Monterey, California.
HP Labs,
Apr 2003, Palo Alto, California.
IBM T.J. Watson Research Center, Jul 2003, Yorktown Heights, New York.
Rajan, D. and Atamtürk, A.
"Designing survivable networks with directed cycles for routing
disrupted flow,"
Pacific Region Intercollegiate Symposium for the Management
Sciences (PRISMS),
Mar 2002, Palo Alto, California.
Atamtürk, A. and Rajan, D.
"Designing capacity-efficient survivable networks with failure
flow patterns,"
INFORMS Annual
Meeting, Nov 2001, Miami Beach, Florida.
Atamtürk, A. and Rajan, D.
"A branch and cut algorithm for multicommodity network design
problems,"
INFORMS
Annual Meeting, Nov 2000, San Antonio, Texas.
Teaching Experience
Instructor.
Completely responsible for class.
Operations Research I. Aug - Dec 2003.
Introduction to deterministic optimization. Nonlinear programming,
integer programming, network flows.
Teaching Assistant.
Held discussion sections/labs, office hours and graded papers/exams.
Operations Research I. Aug - Dec 2000.
Introduction to deterministic optimization. Nonlinear programming,
integer programming, network flows.
Teaching Assistant.
Held discussion sections/labs, office hours and graded papers/exams.
Fundamentals of Operations Research.
Jul - Nov 1998.
Linear programs, simplex method, sensitivity analysis,
duality theory, complementary slackness.
Teaching Interests
Graduate Coursework.
Operations Research; in particular - Linear and Nonlinear
Optimization, Integer Programming, Combinatorial Optimization, Network Flows.
Undergraduate Coursework. Introductory and advanced courses in
operations research, especially in deterministic optimization methods
and modeling.
Other Skills
Programming/Software Languages :
CPLEX
Callable Libraries,
C/C++,
Java,
AMPL,
Matlab,
R/Splus,
SIGMA,
LaTeX, HTML,
Pascal,
Perl,
SQL.
Operating Systems : Unix/Linux/Solaris (system
administrator), Windows 98/NT/2000/XP.
Languages : Fluent in English, Hindi and Tamil.
Professional Activities
Referee
International Conference on Distributed Computing Systems,
INFORMS Journal of Computing,
Mathematical Programming,
Networks,
Networks and Spatial Economics,
Operations Research.
Session Chair
INFORMS International Meeting 2007.
Coordinator,
Pacific Region
Intercollegiate Symposium for the Management Sciences, 2003.
Student conference for OR/MS programs in the Bay Area - more than 50
participants.
President,
Berkeley Student INFORMS Chapter, 2001-2002.
Instrumental (with fellow officers) in reviving the long-dormant
student organization.
Graduate Student Representative, Departmental Research
Seminar Committee, 2001-2002.
Organize weekly research seminar, with invited faculty/industry
practitioners.
References available upon request.
Citizen of India.