<div dir="ltr"><br><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">---------- Forwarded message ---------<br>From: <strong class="gmail_sendername" dir="auto">Abbas Omidi</strong> <span dir="auto"><<a href="mailto:abb.omidi@gmail.com">abb.omidi@gmail.com</a>></span><br>Date: Mon, Jun 26, 2023 at 2:47 PM<br>Subject: MIP-start in SCIP<br>To:  <<a href="mailto:scip@zib.de">scip@zib.de</a>><br></div><br><br><div dir="ltr">Dear support team,<br><div><br></div><div><div>I am working on a large-scale scheduling problem in order to compare the current resource capacity and the required one to maximize resource utilization. Let's say there exist more than 80 resources and around 250 tasks that should be processed in the weekly duration. Also, all of the data and its limitations are already known in advance. </div><div><br></div><div>In the first step, I have tried to formulate the problem as a MIP. I managed to investigate around four different formulations. However, each of which has its limitations in the solving process. For example, the first and the second contain more than 11M rows and 10M variables. (9M are binary). The third and the fourth have a better situation with the aid of tightening formulation. They still have around 3M binary variables and 500K rows. Actually, neither SCIP nor CPLEX could not solve such a problem in a reasonable amount of time as we expected.</div><div><br></div><div>an approach I am working on is by producing as good an initial solution as possible and then feeding that into the solver. For that I write an optimization model, again a MIP, to capture some of the original problem limitations. The main variable in this auxiliary model is the same as the main variable in the original model. I can solve this auxiliary problem by a solver or by a heuristic method to invoke either an optimal or near-optimal solution respectively.</div></div><div><br></div><div><div>The strange behavior is here:</div><div>When the auxiliary problem is solved, I fix the value of the variables as a MIP-start on the original problem. By that, the solver log shows the MIP-start cannot produce any incumbent. And the solving process continues as the usual paradigm that the solver decides. In the second attempt, I try fixing the original main problem variable bounds (LB and UB simultaneously) by the auxiliary problem output. In this situation, the strange thing is that the solver can find a very good initial incumbent at the early stage of the solving process, and also the solving time significantly decreases.</div></div><div><br></div><div>---------</div><div>P.S: </div><div>The original problem contains mixed variables. The main is a binary, also auxiliary binary variables for interchanging relations, and some of the positive variables as intervals. In the auxiliary problem, there is a binary as the same as the original main binary variables. Also, the provided initial solution by the auxiliary problem covers all of the main binary variables in the original one, but not for the rest.</div><div><br></div><div>We managed to test some instances of the original problem, (already as small as possible so that we can track the behavior of the model and its solution), and actually with the practical data. In all of the cases, the solution of the original problem corresponds to what we were expecting. Also, by having the fixed main binary variables the outputs are the same as the original ones. I should still say, I mean by CPLEX and SCIP is by calling them into a third-party language, GAMS. However, I tried different MIP-start parameters in GAMS/SCIP, but it does not have any impact on the solving process behavior.  </div><div><div>---------</div><br></div><div><b><i>I was wondering if, how is it possible the solver rejects an initial solution as a MIP-start, but accepts that after fixing the main variable bounds?<br></i></b></div><div><br></div><div><br></div><div>Thanks in advance</div><div>Regards</div><div>Abbas</div></div>
</div></div>