<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<style type="text/css" style="display:none;"> P {margin-top:0;margin-bottom:0;} </style>
</head>
<body dir="ltr">
<div><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">Hi everyone,</span></div>
<div><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);"><br>
</span></div>
<div class="elementToProof"><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">I am currently trying to run a column-generation algorithm on a problem with a convex objective function and linear constraints.</span></div>
<div><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);"><br>
</span></div>
<ul data-editing-info="{"orderedStyleType":1,"unorderedStyleType":2}" style="margin-block: 0px;">
<li style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0); margin: 0in 0in 0in -0.25in; list-style-type: "- ";">
<span style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">I implemented the Restricted Master Program (RMP) in SCIP, using a constraint to reproduce the convex objective function ; so my problem is :<br>
</span></li></ul>
<div class="elementToProof"><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);"> o Min z</span></div>
<div class="elementToProof"><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);"> o f(x) < z</span></div>
<div class="elementToProof"><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);"> o A x < b</span></div>
<div class="elementToProof"><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);"> Variables z and x=(x_1…x_n) are real-valued ; the column generation algorithm creates new x_k variables.</span></div>
<ul data-editing-info="{"orderedStyleType":1,"unorderedStyleType":2}" style="margin-block: 0px;">
<li style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0); margin: 0in 0in 0in -0.25in; list-style-type: "- ";">
<div class="elementToProof"><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">I used SCIP 8.1.0 with IPopt as nonlinear solver, and wrote the problem and pricer in C/C++ ; I set the “constraints/nonlinear/assumeconvex”
to True and remove pre-processings,</span></div>
</li><li style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0); margin: 0in 0in 0in -0.25in; list-style-type: "- ";">
<div class="elementToProof"><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">The pricer callback functions is based on the dual variables of the linear constraints adds new columns in the RMP (the pricing problem
is derived from the KKT conditions on my master problem) ; I also use at the current solution via the SCIPgetBestSol(...) function in the pricer.</span></div>
</li></ul>
<div class="elementToProof"><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);"><br>
</span></div>
<div class="elementToProof"><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">When I run the program I face several issues:</span></div>
<ul data-editing-info="{"orderedStyleType":1,"unorderedStyleType":2}" style="margin-block: 0px;">
<li style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0); margin: 0in 0in 0in -0.25in; list-style-type: "- ";">
<div class="elementToProof"><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">When I try the SCIPisDualSolAvailable(...) function I get a warning message telling clearly that the dual variables are not available:
“WARNING: Dual information only available for pure LPs (only linear constraints)”</span></div>
</li><li style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0); margin: 0in 0in 0in -0.25in; list-style-type: "- ";">
<div class="elementToProof"><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">Yet I can access the dual variables of my linear constraints, but their value are clearly not what I would expect (similar to what is
described here: https://listserv.zib.de/pipermail/scip/2023-August/004736.html )</span></div>
</li><li style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0); margin: 0in 0in 0in -0.25in; list-style-type: "- ";">
<div class="elementToProof"><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">Even ignoring the dual variables and focusing on the primal solution, I see pricer is called well before the RMP converged, and the
primal solution is far from optimal. So when I run my program the pricer is called way too often, leading to very poor performances.</span></div>
</li></ul>
<div><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);"><br>
</span></div>
<div class="elementToProof"><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);"><br>
</span></div>
<div class="elementToProof"><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">So I am wondering if it is possible to run a column-generation algorithm on a NLP in SCIP?</span></div>
<div class="elementToProof"><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);"><br>
</span></div>
<div class="elementToProof"><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">If it isn’t possible to access reliably the duals of the linear constraints, is it possible to ensure the pricing problem is only called
when the RMP has converged to a (reasonably) optimal solution ?</span></div>
<div class="elementToProof"><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);"><br>
</span></div>
<div><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">Many thanks,</span></div>
<div class="elementToProof"><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">Guillaume</span></div>
</body>
</html>