0
$\begingroup$

I am new to the optimization problem of Quadratic programming. In equation $8$ of this paper, there is an equation:

$$\min \operatorname{cost} (x) = x' H x +c' H x \quad \text{subject to,} \tag{8} \\ Ax=b, \quad x\in\{0,1\}^n$$

The authors state that this is an 'Integer Quadratic Programming (IQP)' formula.

Alternatively, in this other website, there is the following equation which is described as a 'Mixed Integer Quadratic Programming (MIQP)' formulation:

$$\min\limits_x f(x) = \frac12 x^T F x +c^T x$$

From my perspective, both of the equations shown above are similar, with the only difference being that the MIQP formula has '$1/2$' included in it.

  1. I am looking for an explanation on the differences between the IQP and MIQP and in particular what the '$1/2$' represents in MIQP.

  2. In addition, I am interested to apply quadratic programming to the assignment problem, thus, looking for any insight into which should be used (i.e., IQP vs. MIQP) and when.

$\endgroup$
5
  • 1
    $\begingroup$ IQP implies all variables can only be integers. MIQP implies some can only be integers while others can be real numbers. $\endgroup$ Commented Mar 15, 2019 at 20:19
  • $\begingroup$ @RohitPandey do you know why the '1/2' term is added to the MIQP formulation? $\endgroup$
    – user121
    Commented Mar 15, 2019 at 20:31
  • 2
    $\begingroup$ Don't know for sure, but its generally just a scaling factor so that taking derivative cancels the $2$ out. Some people tend to include it, others don't. Doesn't affect the optimization problem in spirit and I highly doubt it has anything to do with the problem being MIQP. $\endgroup$ Commented Mar 15, 2019 at 20:40
  • $\begingroup$ good explanation. $\endgroup$
    – user121
    Commented Mar 15, 2019 at 20:42
  • 1
    $\begingroup$ @user121 The scaling factor of $1/2$ is the same as the one you'll find in some definitions of quadratic forms: for example, see this history section of the Wikipedia article on integral quadratic forms. $\endgroup$
    – Théophile
    Commented Mar 15, 2019 at 21:27

0

You must log in to answer this question.

Browse other questions tagged .