3
$\begingroup$

Suppose L is a linear program that is a relaxation of some 0/1 integer linear program ILP. There is a systematic way to construct SDP relaxations of ILP that are tighter than L by using a Lasserre hierarchy. There are many software tools available to solve linear programs (e.g. CPLEX, lpSOLVE, GLPK) . I am looking for a (free) software tool that can do the following. If I give a linear program and a number t as input, then the tool must output the optimal value of the objective and values of the SDP variables at the t-th level of hierarchy.

$\endgroup$
  • $\begingroup$ It seems to me that you want two different pieces of software. (1) an SDP solver and (2) a program that constructs the SDP at the $t$-th level of the hierarchy. Finding software for (1) is not hard. $\endgroup$ – Peter Shor Mar 1 '15 at 16:49
  • $\begingroup$ Yes, a script that will do just (2) is also fine. But I expect some SDP solver to have this option. $\endgroup$ – Jagadish Mar 1 '15 at 18:58
  • $\begingroup$ What about the original code homepages.laas.fr/henrion/software/gloptipoly3 $\endgroup$ – AndreaCassioli Mar 1 '15 at 20:31
  • $\begingroup$ as far as I know no SDP solver as this algorithm built in. $\endgroup$ – AndreaCassioli Mar 1 '15 at 20:33

Your Answer

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

Browse other questions tagged or ask your own question.