UNIVERSITY OF NEBRASKA
Grant: $220,000 - National Science Foundation - Jul. 31, 2009
No votes have been cast for this award yet
Join the conversation: Post a comment about this award
Award Description: This proposal concerns the development of a means for efficient computerized search for combinatorial objectswith a specified isomorph-invariant property. One of themost powerful techniques developed by the computer science and operations research communities for computationally solving combinatorial optimization problems is integer programming. However, solving integer programs using the linear programming relaxation does not perform well when searching for a combinatorial object X with a specified isomorphinvariant property P. Every object isomorphic toX also satisfies P, and, counter-intuitively, the presence ofmany objectswith the desired property significantly slows the solving techniques of branch-and-bound and cutting planes. Additionally, the integrality condition often means the rational relaxation is not a good approximation to the integer program. This frequently occurs when searching for combinatorial objects because of divisibility conditions. The PI proposes two new methods to address the difficulties caused by symmetry and divisibility conditions: rejecting isomorphic nodes from the branch-and-bound search tree through the use of symmetry-breaking orbital cuts, and using p-modular relaxations where the linear constraints are considered modulo a prime p. The PI proposes to implement the combinatorial search framework of integer programming, isomorph rejection, and p-modular relaxations as computer code, and then apply the framework to several problems in the theory of graphs and hypergraphs. IntellectualMerit This proposal focuses on developing the use of integer programming combined with symmetry-breaking orbital cuts, and using p-modular relaxations symmetry-breaking cuts in the study of combinatorial objects. Integer programming is a powerful computational technique that has been developed over the last sixty years. The resulting theoretical framework is intendedto be usedas a tool for exploration andexperimentation in the study of graphs and hypergraphs. The PI will use the framework to study several particular problems. Broader Impacts The PI will involve his current graduate students in the proposed research. The PI will also continue his involvement in other mathematical endeavors, including mentoring undergraduate research through the department’s NSF-funded Mentoring through Critical Transition Points (MCTP) program, outreach programs such as the Lincoln Area Math Teacher’s Circle andMath in theMiddle (an NSF-funded professional development program for Nebraska middle school teachers), and service to the profession, including refereeing and organizing special sessions at conferences.
Project Description: For this project, graduate student Derrick Stolee and investigator Stephen Hartke have begun refining the method of symmetry-breaking cuts that was outlined in the grant proposal. Derrick has begun coding the general framework to implement the method using the LP/IP solver IBM ILOG CPLEX. Our first test application will be to search for a (99,14,1,2) strongly regular graph.
Infrastructure Description: N/A
Jobs Summary: As an educational institution, jobs created or retained fall into broad categories of faculty salaries, administrative salaries, managerial professional salaries and clerical or technical salaries. They may also include some academic salaries for student workers. Salaries are used in support of research or other sponsored projects being performed at UNL. Faculty post-docs and graduate students are the primary recipients of salary dollars; however, some managerial or professional, clerical and technical or students may benefit as well. Faculty personnel usually include the titles professor, assistant professor, associate professor, instructor, assistant instructor and post-doctoral assistant. Administrative and clerical salaries are charged if they meet the criteria detailed in OMB Circular A-21. Keeping post-docs, graduate students and undergraduate students employed has an additional impact of allowing them to pursue additional education, preparing them for future employment. As a broader impact, results of some projects may result in additional jobs in the public sector as technology is expanded to that market. For this project and quarter, full-time equivalent positions were created and/or retained either by UNL or by sub-awards made from this grant, if applicable. Calculations were made in accordance with the Office of Management and Budget Memorandum M-09-21 and subsequent guidance as provided by the OMB. (Total jobs reported: 0)
Project Status: Less Than 50% Completed
This award's data was last updated on Jul. 31, 2009. Help expand these official descriptions using the wiki below.
No comments have been added for this project.