Implement a special converter of Quadratic Program of Qiskit Optimization

[a-matsuo]

Description

We work on implementing special converters for specific constraints.
When users solve an optimization problem with Qiskit Aqua, they apply InequalityToEquality to convert inequality constraints into equality constraints by introducing slack variables, and then apply LinearEqualityToPenalty to translate the constraints into penalties of the objective function of QUBO. But, there are some special patterns are known that does not require slack variables.

The objective of this project is to implement such special converters and compare the performance with and without the special converters.

A Tutorial on Formulating and Using QUBO Models introduces examples of the special patterns in page 10 as follows.
image

Reference
A Walkthrough of Qiskit’s New Optimization Module
Max-Cut and Traveling Salesman Problem
Converters for Quadratic Programs
InequalityToEquality
LinearEqualityToPenalty
PyQUBO: Python Library for Mapping Combinatorial Optimization Problems to QUBO Form

Mentor/s

Atsushi Matsuo (@a-matsuo), Researcher at IBM Research Tokyo, Qiskit Optimization core developer

Type of participant

You should have basic knowledge of Qiskit and Python, and ideally (but not necessarily required) are familiar with mathematical optimization

Number of participants

2

Deliverable

A PR to the Qiskit Optimization, maybe also extending the existing tutorial.

[hykavitha]

I'm interested in this topic to work.

[HuangJunye]

@ibmamnt @knamba-jp Can you comment on this issue so that I can assign you? Please also work with your mentor to refine the project, define scope and deliverables and update the project description in this issue.

[knamba-jp]

@HuangJunye We've just started talking with our mentor and studying this issue.

[ibmamnt]

@HuangJunye I (ibmamnt) has also started to work on this project.