1
$\begingroup$

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?

Improve this question
$\endgroup$
7
$\begingroup$

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$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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 $2*N$ 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, m*y_{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 ? $\endgroup$ – FredNgu Aug 31 '20 at 18:18
  • $\begingroup$ @FredNgu see this thread, where several solvers are mentioned. $\endgroup$ – RobPratt Aug 31 '20 at 18:27
  • $\begingroup$ 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 ? $\endgroup$ – FredNgu Aug 31 '20 at 20:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.