Quantum Computing in Regional Sciences: An Optimization Problem

[dsierrasosa]

Description

There are several proposals to solve optimization problems using Quantum Algorithms, some examples can be found in the Qiskit textbook, were an application of the Quantum Approximate Optimization Algorithm (QAOA) is presented and described. When we need to take into account the spatial dimension in an optimization problem, we are in the realm of Regional Sciences. In these problems, we work on grouping regions based on an objective function, merging adjacent locations into a homogenous regional cluster.

In this QAMP we are looking forward to explore the application of Quantum Computing to the Regional Science field, where several optimization formulations have been proposed and solved using heuristic methods that approximate an optimal solution.

Deliverables

• Develop a Qiskit implementation from regional science optimization problem
• Summarize the findings and methods on a draft paper for potential submission to peer-reviewed journal

Mentors details

• Mentor
  • Name: Daniel Sierra-Sosa
  • GitHub ID: @dsierrasosa
  • What they do: Assistant Professor, Hood College. Quantum Computing researcher and enthusiast

Number of mentees

1

Type of mentees

• Mentee
  • Required:
  • Interest in optimization problems
  • Proficiency in Python and Qiskit
  • Nice to have:
  • Background on classical optimization

[dsierrasosa]

Presentation for Checkpoint 1! QAMP-2022_Spring.pdf

[HuangJunye]

@VedDharkar @epelaaez @AntonSimen06 Can you please comment in the issue so that I can assign you? Thank you.

[epelaaez]

No problem

[AntonSimen06]

Sure!

[VedDharkar]

Sure!!

[HuangJunye]

@VedDharkar @epelaaez @AntonSimen06 Can you please provide your checkpoint 2 updates? Instructions are given in the slack channel.

[epelaaez]

Checkpoint 2

We’ve taken the code needed to solve the maximal covering location problem with a quantum circuit and condensed it in Python notebook as a walkthrough of the problem. After defining the problem mathematically and outlining the process to solve it, we import our specific problem from an Excel file and then use the gurobipy package to create a model for our problem. This model has binary variables, various constraints, and an objective function that we seek to minimize. To find the optimal solution for further comparison, we use Gurobi’s classical solver. To solve the problem with Qiskit, we first need to convert our model into a QUBO program. Doing this is done with the converters included in Qiskit’s optimization module. This allows us to first convert all constraints into penalties inside the objective function using slack variables, and then turn the integer slack variables into binary. Once we have our problem as a QUBO, we can run QAOA to optimize the objective function. After the optimization is done, we can see that the variables corresponding we are looking for are set to the correct values we found through classical methods, and thus we complete the walkthrough.

To solve the p-regions problem we need to first convert our problem statement to a quadratic program. We are using MIP models to formulate the p-regions problem into a quadratic equation. There are three different models that are Tree, Order, and Flow. Every model has its own set of constraints and variables. Every model is unique. For example: the Tree model was inspired by the MTZ constraints which were originally developed from TSP problem. The Order model is used to prevent cycles and ensure and keep the contiguity. The Flow model is also used to ensure the contiguity of the areas for the selected region. It was inspired by the work of Shirabe. We are trying to solve the problem with all these methods and then ensuring which one is more effective when run on a quantum computer.

[HuangJunye]

@VedDharkar @epelaaez @AntonSimen06 Can you please upload your final showcase presentation here? Thank you.