Vertically Integrated Projects (VIP) provides UMD students of all backgrounds, disciplines, and levels of experience with the opportunity to engage in scaffolded, multidisciplinary team-based projects.
VIP Team Information
VIP Team
Open-Source Optimization Algorithms
VIP Faculty Mentors:
Dr. John Silberholz
Decision, Operations & Information Technologies Area
Meeting Location, Day & Time:
Location: Van Munching Hall, Room To Be Announced
Time: Fridays, 4:00pm - 5:00 pm
Description:
Across many disciplines, decision makers face difficult decision problems. How should we route our fleet of vehicles? How can we lay out a new computer chip? For many questions, there is no known efficient way to find the best possible solution (e.g. the precise routes that minimize total fuel consumption, or the chip layout that minimizes the total silicon footprint). Instead, researchers develop heuristics, which are computer algorithms that seek to obtain good solutions quickly for the problem at hand. For important problems, researchers have developed and published dozens or even hundreds of these algorithms.
For many of these important problems, the state of science around these heuristics is poor. Papers proposing a new algorithm are generally behind paywalls in academic journals and do not publish open-source code implementing their new algorithm. They often test their algorithm on a limited set of test cases. The end result is that practitioners (the people trying to solve these decision problems in the field) can’t tell which algorithms are best for them, and even if they did pick out an algorithm they liked, they wouldn’t have an easy way to run it (they would need to code it up from scratch, which is often a considerable effort).
It doesn’t have to be this way! The open science movement is an effort to produce open-source software, open data from experiments, and open-access publications, expanding the dissemination of scientific ideas and increasing the impact of research. This VIP Team will seek to take an open science approach to the research around heuristics for important decision problems, with a goal of considerably increasing the impact and accessibility of algorithms research that has already been performed but remains largely hidden behind paywalls in the academic literature.
Some high-level goals for a team include:
Developing high-quality implementations of heuristics from the academic literature and distributing these via open-source software packages.
Collaborating with practitioners to develop high-quality open-source benchmarks that can be used by the research community to test new heuristics.
Using machine learning and other AI methods to learn which algorithms work the best for different types of problem instances.
Disseminating our work among practitioners (get them using the packages we create) and among researchers (encourage open science practices in the heuristics community).
I have seen first-hand the effect such a project can have. I co-led an open-science initiative around the Max-Cut and Quadratic Unconstrained Binary Optimization (QUBO) problems. This was hugely valuable to quantum computing researchers who want to benchmark their quantum computers against classical computers on hard optimization problems, and our MQLib project has become a de facto standard for evaluation in that field.
Methods:
This VIP team will take a systematic approach to open-source optimization algorithms.
Long-term strategic planning: Which optimization problems should we be working on to have the largest impact? Students working on strategic planning might employ methods like interviews / surveys of both practitioners and academics, literature reviews, and multi-criteria decision making (MCDM).
What algorithms should we implement? Once we settle on an optimization problem, we need to decide what algorithms we should implement. Students selecting what algorithms to implement might employ methods like large-scale literature review and multi-criteria decision making (MCDM).
Open-source implementation: At the heart of this VIP team lies open-source implementation of algorithms. There are many ingredients here: requirements gathering / project planning, project management, software architecture and design, software development, software testing, deployment and release management, documentation, etc. Many of these steps will be performed with AI support.
Open-source benchmarks: The way to tell if an algorithm is “good” or “not so good” is to test it on real problems faced by practitioners and see how it does. Students building benchmarks may engage in tasks like interviews with practitioners, literature review, exploration of metrics that differentiate benchmarks, exploration of tools to generate synthetic instances, and exploration of how best to distribute open-source benchmarks.
Computational testing: With algorithms implemented and benchmarks in hand, we are ready for computational testing! We want to run each algorithm on each benchmark (and, of course, publish all the data from those experiments). Students working on computational testing will wrestle with questions like: What cloud platform should I use? How can I test cost-effectively? How do I ensure comparable hardware when testing?
What works best when? Ultimately, we want to use the results of our computational testing to learn which algorithm works best on what types of benchmark instances, an AI / machine learning task. Students would define relevant benchmark features, test different machine learning models, and deploy those machine learning models in an open-source package.
Dissemination: Dissemination is a core task for the team. Students might perform informational interviews, produce publications, make presentations to practitioners to raise awareness, and make presentations to academics to share our work and encourage them to follow the open-science principles we adhere to in our work.
An example project following many steps of the proposed approach can be found at https://github.com/MQLib/MQLib
Majors:
Students of any major with enthusiasm around the open-science approach taken by the VIP team could contribute, particularly around long-term strategic planning, practitioner outreach, and dissemination. That said, some majors are a particularly good fit for the specific research tasks being conducted by this VIP team:
Computer Science: All aspects of open-source implementation, plus computational testing and machine learning to predict algorithm performance.
Business majors (especially Operations Management & Business Analytics and Information Systems): long-term strategic planning, algorithm selection, requirements gathering, project management, sourcing relevant benchmarks.
Computer Engineering / Electrical Engineering: Software development, computational testing, optimization problems from engineering applications.
Mathematics (particularly statistics and applied math tracks): Design of computational testing, defining features of benchmark instances (often inspired by graph theory and other areas of math), predicting algorithm performance.
Information Science / Technology and Information Design: Practitioner interviews, requirements gathering, project management, documentation, open-source distribution.
Preferred Interests:
No specific skills are required to join the VIP team. As this VIP team involves quite a bit of “setup” to get going (learning about optimization algorithms, learning about software development, etc.), students who can contribute over multiple semesters are preferred.