Abstract
Combinatorial optimization assumes that all parameters of the optimization problem, e.g. the weights in the objective function, are fixed. Often, these weights are mere estimates and increasingly machine learning techniques are used to for their estimation. Recently, Smart Predict and Optimize (SPO) has been proposed for problems with a linear objective function over the predictions, more specifically linear programming problems. It takes the regret of the predictions on the linear problem into account, by repeatedly solving it during learning. We investigate the use of SPO to solve more realistic discrete optimization problems. The main challenge is the repeated solving of the optimization problem. To this end, we investigate ways to relax the problem as well as warm-starting the learning and the solving. Our results show that even for discrete problems it often suffices to train by solving the relaxation in the SPO loss. Furthermore, this approach outperforms the state-of-the-art approach of Wilder, Dilkina, and Tambe. We experiment with weighted knapsack problems as well as complex scheduling problems, and show for the first time that a predict-and-optimize approach can successfully be used on large-scale combinatorial optimization problems.
| Original language | English |
|---|---|
| Title of host publication | AAAI 2020 - Thirty-Fourth AAAI Conference on Artificial Intelligence |
| Editors | Vincent Conitzer, Fei Sha |
| Place of Publication | Palo Alto CA USA |
| Publisher | Association for the Advancement of Artificial Intelligence (AAAI) |
| Pages | 1603-1610 |
| Number of pages | 8 |
| ISBN (Electronic) | 9781577358350 |
| DOIs | |
| Publication status | Published - 2020 |
| Externally published | Yes |
| Event | AAAI Conference on Artificial Intelligence 2020 - New York, United States of America Duration: 7 Feb 2020 → 12 Feb 2020 Conference number: 34th https://aaai.org/Conferences/AAAI-20/ (Website) |
Publication series
| Name | AAAI 2020 - 34th AAAI Conference on Artificial Intelligence |
|---|---|
| Publisher | Association for the Advancement of Artificial Intelligence |
| Number | 2 |
| Volume | 34 |
| ISSN (Print) | 2159-5399 |
| ISSN (Electronic) | 2374-3468 |
Conference
| Conference | AAAI Conference on Artificial Intelligence 2020 |
|---|---|
| Abbreviated title | AAAI-20 |
| Country | United States of America |
| City | New York |
| Period | 7/02/20 → 12/02/20 |
| Other | The Thirty-Fourth AAAI Conference on Artificial Intelligence was held on February 7–12, 2020 in New York, New York, USA. The surge in public interest in AI technologies, which we have witnessed over the past few years, continued to accelerate in 2019–2020, with the societal and economic impact of AI becoming a central point of public and government discussion worldwide. AAAI-20 saw submissions and attendance numbers that were records in the history of the AAAI series of conferences and continued its tradition of attracting top-quality papers from all areas of AI. We were excited to see increases in submissions across almost all areas. The AAAI-20 program consisted of a core technical program of original research presentations, including a special track on AI for social impact and a sister conference track. It additionally featured a broad range of tutorials, workshops, invited talks, panels, student abstracts, a debate, and presentations by senior members. The program was rounded out by technical demonstrations, exhibits, an AI job fair, the AI in Practice program, a student outreach program, and a game night. The conference also continued its tradition of colocating with the long-running IAAI conference and the EAAI symposium, as well as the newer conference on AI, Ethics, and Society. |
| Internet address |
|