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

Professional Awards Research Teaching Skills


Go to top.

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

Go to top.

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

Go to top.

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.

Go to top.

Teaching Experience

University of California at Berkeley

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.

Indian Institute of Technology - Madras

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.
Go to top.

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.

Go to top.