Binary Quadratic Programming Relaxation

2020 7 12
1 个回答
更新时间：2020 7 12
4 次查看（30 天）

0 个投票

what is the best solver to solve Binary Quadratic Programming Problem in Matlab, and is it neccessary to relax the {0,1} to solve it.
Knowng that my problem has linear equality and linear inequality constraints (the constraints are linear).

请先登录，再回答此问题。

回答（1 个）

John D'Errico
John D'Errico 2020-7-12

0 个投票

While you could just use a tool like quadprog with continuous varibles in the interval [0,1], then round the result at the end, but there is no assurance the result is then optimal. And if you do round the solution at the end, it will probably no longer even satisfy the eqaulity constraints. So you would just be wasting your time.
Therefore GA is probably your main choice, with binary variables and a quadratic objective.

2 个评论
显示 无 隐藏 无

Mohammad Al ja'idi
Mohammad Al ja'idi 2020-7-12
you mean no need to relax the variables {0,1} using for example positive semidefinite programming (PSD) technique. you recommend just using GA to solve the problem.
Mohammad Al ja'idi
Mohammad Al ja'idi 2020-7-12
Sorry for bothering, but do you see if I use quadprog to solve the problem with binary values {0,1} will get better result than making relaxaion of the variabls 0,1

请先登录，再进行评论。

类别

在 帮助中心 和 File Exchange 中查找有关 Quadratic Programming and Cone Programming 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by