<html xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=Windows-1252">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
.MsoChpDefault
{mso-style-type:export-only;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style>
</head>
<body lang="EN-US" link="blue" vlink="#954F72">
<div class="WordSection1">
<p class="MsoNormal"><span lang="EN-GB">Dear all,<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">Using CBC 2.10.3, I’m trying to solve a simple MIQP (MIP with quadratic objective) using CBC, but CbcMain1 incorrectly concludes that "Linear relaxation infeasible”.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">The output includes lines which look like the correct solution (-7.5) is found, but then the end result is Linear relaxation infeasible.<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span lang="EN-GB">..<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span lang="EN-GB">Clp0000I Optimal - objective value -7.5<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span lang="EN-GB">Cbc0004I Integer solution of -7.5 found after 0 iterations and 0 nodes (0.00 seconds)<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span lang="EN-GB">Cbc0001I Search completed - best objective -7.5, took 0 iterations and 0 nodes (0.00 seconds)<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span lang="EN-GB">..<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span lang="EN-GB">Result - Linear relaxation infeasible<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span lang="EN-GB">..<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">I must be doing something wrong. The same problem without loading the quadratic part of the objective works as expected.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">The code is below. Any suggestions?<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">Many thanks for your help.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">Regards,<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">Jan-Willem<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> // See https://www.inverseproblem.co.nz/OPTI/index.php/Probs/MIQP<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> // min 0.5 x1^2 + x2^2 - x1x2 - 2x1 - 6x2<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> // st. x1 + x2 <= 2<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> // -x1 + 2x2 <= 2<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> // 2x1 + x2 <= 3<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> // x1 >= 0, x2 >= 0 <o:p>
</o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> // x1 and x2 integer<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> // <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> // Linear relaxation: x1 = 0.66, x2 = 1.333 -> obj = -8.22222<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> // Integer solution: x1 = 1, x2 = 1 -> obj = -7.5<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> int numcols = 2;<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> int numrows = 3;<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> // The main problem<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> int startA[3] = { 0, 3, 5 }; // per variable (column), the starting position of its nonzero data, plus final<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> int indexA[6] = { 0, 1, 2, 0, 1, 2 }; // The constraint index number per nonzero element<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> double valueA[6] = { 1.0, -1.0, 2.0, 1.0, 2.0, 1.0 }; // The nonzero elements<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> double collb[2] = { 0.0, 0.0 };<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> double colub[2] = { 10000.0, 10000.0 };<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> double obj[2] = { -2.0, -6.0 };<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> double rowlb[3] = { -10000.0, -10000.0, -10000.0 };<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> double rowub[3] = { 2.0, 2.0, 3.0 };<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> // Quadratic objective<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> int startObj[3] = { 0, 2, 3 };<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> int columnObj[3] = { 0, 1, 1 };<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> double elementObj[3] = { 1.0, -1.0, 2.0 }; // diagonals get double coefs, non-diagonals normal coefs values<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> OsiClpSolverInterface solver1;<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> CbcModel cbcModel(solver1);<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> // solver1 was cloned, so get current copy<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> OsiClpSolverInterface* osiClp = dynamic_cast<::OsiClpSolverInterface*>(cbcModel.solver());<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> osiClp->loadProblem(numcols, numrows, startA, indexA, valueA, collb, colub, obj, rowlb, rowub);<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> osiClp->setRowName(0, "row1");<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> osiClp->setRowName(1, "row2");<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> osiClp->setRowName(2, "row3");<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> osiClp->setColName(0, "x1");<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> osiClp->setColName(1, "x2");<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> osiClp->setInteger(0);<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> osiClp->setInteger(1);<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> // Commenting out the next two lines gives the expected MIP solution.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> ClpSimplex* clpSimplex = osiClp->getModelPtr();<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> clpSimplex->loadQuadraticObjective(numcols, startObj, columnObj, elementObj);<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> CbcMain0(cbcModel);<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> const char* argv[] = { "TestQuad1", "-solve", "-quit" };<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> CbcMain1(3, argv, cbcModel);<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"><o:p> </o:p></span></p>
<p class="MsoNormal" style="text-indent:.5in"><span lang="EN-GB">bool optimal = cbcModel.isProvenOptimal(); // false<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> double objValue = cbcModel.getObjValue();<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> const double* sol = cbcModel.getColSolution();<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> int n = cbcModel.getNumCols();<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> double x1Value = sol[0];<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"> double x2Value = sol[1];</span><o:p></o:p></p>
</div>
</body>
</html>