[SCIP] MIP-start in SCIP

[Abbas Omidi]

Dear support team,

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.

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.

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.

The strange behavior is here:
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.

---------
P.S:
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.

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.
---------


*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?*


Thanks in advance
Regards
Abbas
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20230626/4a5e30f9/attachment.html>