2

There's something I don't understand about CVXPY's example on its MIQP use. It says that the algorithm returns a solution $x \in \mathbb{Z}^n$ but I thought in general the point of MIQP algorithms was to return a solution $x$ such as

$$\forall i, x_{i} \in [m,M] \cup \{0\}$$

given $m,M\in \mathbb{R}$. Am I missing some parameters here?

Rodrigo de Azevedo
  • 1
  • 2
  • 11
FredNgu
  • 157
  • 9

1 Answers1

7

What you described is a problem for which every variable is semicontinuous. In mixed integer programming, the variables are $(x,y)\in\mathbb{Z}^{n_1} \times \mathbb{R}^{n_2}$. For (pure) integer programming, take $n_2=0$.

RobPratt
  • 32,006
  • 1
  • 44
  • 84
  • Okay, and let's say I want to solve an optimization problem where the variables are the $x_{i}, i=1,\ldots,N$, can I consider it as a mixed integer programming problem with $2N$ variables, the first N being the vector $(x_{i})_{i=1,\ldots,N}$ and the other N are indicator variables $y \in {0,1}$ such as $\forall i, my_{i} \leq x_{i} \leq M*y_{i}$ ? Or do you know a more efficient way to solve a semi continous quadratic optimization in Python ? – FredNgu Aug 31 '20 at 18:18
  • @FredNgu see this thread, where several solvers are mentioned. – RobPratt Aug 31 '20 at 18:27
  • Thank you, they mentioned the lp_solver but unfortunately it seems like it only solves linear programming. Another solution they mentioned is the big-M formulation that is very similar to the approach in my last comment. I am going to try this approach, however I'm afraid the algorithm will face numerical errors. For example if for one binary variable $y_{i}=0$, we will have for that $i$ : $0 \leq x_{i} \leq 0$ but the algorithm will still affect a non-zero value (although very low) to it. What do you think about that ? – FredNgu Aug 31 '20 at 20:01