I am actually working on a problem recquiring to configure a manufacturing line by affecting machines to workstations, tasks to these workstations and select a configuration for every machine under the problem constraints (cadency, tasks' precedencies, limitations on machines selection). My current objective is to minimize the total machine cost and number of workstations exploited.
To do so, I decided to adopt a scheduling approach by using interval variables, and when I try to solve the problem by using the IterativeDiving search procedure, the calculated bound is "0; 1" (machine cost; nb of workstations) and the solver tells me that there is no solution. On another hand, when using the MultiPoint strategy, a solution is actually found and even optimized to converge towards the optimal solution (optimal solution calculated from a litterature paper I got the instance from). So I was wondering: why is the solver not able to instantiate a feasible solution for every strategy other than MultiPoint?
Since the MultiPoint was efficient to find a feasible solution (but less efficient to prove optimality/unfeasibility), I tried by using the script to search a first solution with MultiPoint and by using a warmstart procedure, switch to IterativeDiving after a solution is found. But by doing so, the lower bound computed (i'm in minimization) is every time equal to my solution/higher than my solution, thus resulting in the search stop.
I've tried to search more information about the bound calculation, but didn't find any clue yet. I expect my model to be unperfect and causing this bad bound calculation, but can't figure out why. Bellow is the code of some of my variables declaration and how they're used. I've tried to shortten it as much as possible (without precising input data for example) to avoid a big post, but i'm obviously ready to answer any question.
dvar interval task[P][OS] optional;
dvar sequence t_seq[p in P] in all (os in OS) task[p][os];
dvar interval x[p in P][os in OS][m in M][W] optional size (tau[os][m] * p.V);
dvar interval y[W][P] optional;
dvar boolean z[M][W];
dvar int+ nbStages in 1..Wmax;
forall(p in P){
forall(oc in p.OC_n)
sum(os in OS : oc in os.OC && os.ID in p.OS_n) presenceOf(task[p][os]) == 1;
forall(os in OS) if(os.ID not in p.OS_n){
!presenceOf(task[p][os]);
forall(m in M, w in W)
!presenceOf(x[p][os][m][w]);
}
forall(os in p.OS_n)
alternative(task[p][<os>], all(m in M, w in W) x[p][<os>][m][w]);
forall(g in G[p])
endBeforeStart(task[p][<g.os_i>], task[p][<g.os_j>]);
forall(os in OS, m in M, w in W) if (os.ID in p.OS_n)
presenceOf(x[p][os][m][w]) <= z[m][w] * a[os][m];/**/
noOverlap(t_seq[p]);
}
forall(w in W){
sum(m in M) z[m][w] <= 1;
sum(m in M) m_needed[w][m] <= Mmax;
forall(p in P)
sum(os in OS, m in M) presenceOf(x[p][os][m][w]) >= presenceOf(y[w][p]);
w_exploit[w] <= sum(p in P) presenceOf(y[w][p]);
}
forall(w_i in 1..Wmax-1, w_j in w_i+1..Wmax, p in P)
endOf_[p][w_i] <= startOf_[p][w_j];/**/
sum(m in M, w in W) m_needed[w][m] * phi[m] <= Budget;
nbStages == sum(w in W) max(p in P, os in OS, m in M) presenceOf(x[p][os][m][w]);
}
And following are the output for Restart and MultiPoint :
! --------------------------------------------------- CP Optimizer 22.1.1.0 --
! Minimization problem - 3 389 variables, 3 522 constraints
! Presolve : 12 extractables eliminated
! TimeLimit = 600
! Workers = 8
! LogVerbosity = Terse
! NoOverlapInferenceLevel = Extended
! PrecedenceInferenceLevel = Extended
! RestartFailLimit = 1 000
! SearchType = Restart
! Initial process time : 0,24s (0,24s extraction + 0,00s propagation)
! . Log search space : 696,3 (before), 696,3 (after)
! . Memory usage : 8,8 MB (before), 8,8 MB (after)
! Using parallel search with 8 workers.
! ----------------------------------------------------------------------------
! Best Branches Non-fixed W Branch decision
0 3 389 -
+ New bound is 0; 1
! Using temporal relaxation.
! ----------------------------------------------------------------------------
! Search completed, model has no solution.
! Best bound : 0; 1
! ----------------------------------------------------------------------------
! Number of branches : 7 643
! Number of fails : 112
! Total memory usage : 121,2 MB (118,5 MB CP Optimizer + 2,7 MB Concert)
! Time spent in solve : 0,67s (0,43s engine + 0,24s extraction)
! Search speed (br. / s) : 17 941,3
! ----------------------------------------------------------------------------
! --------------------------------------------------- CP Optimizer 22.1.1.0 --
! Minimization problem - 3 389 variables, 3 522 constraints
! Presolve : 12 extractables eliminated
! TimeLimit = 300
! Workers = 8
! LogVerbosity = Terse
! MultiPointNumberOfSearchPoints = 40
! NoOverlapInferenceLevel = Extended
! PrecedenceInferenceLevel = Extended
! RestartFailLimit = 1 000
! SearchType = MultiPoint
! Initial process time : 0,18s (0,18s extraction + 0,01s propagation)
! . Log search space : 696,3 (before), 696,3 (after)
! . Memory usage : 8,8 MB (before), 8,8 MB (after)
! Using parallel search with 8 workers.
! ----------------------------------------------------------------------------
! Best Branches Non-fixed W Branch decision
0 3 389 -
+ New bound is 0; 1
! Using temporal relaxation.
* 27 410 75 0,48s 1 (gap is 100,0% @ crit. 1 of 2)
New objective is 27 410; 8
* 14 575 187k 21,42s 4 (gap is 100,0% @ crit. 1 of 2)
New objective is 14 575; 7
! Time = 21,42s, Average fail depth = 44, Memory usage = 310,1 MB
! Current objective is 14 575; 7
! Current bound is 0; 1 (gap is 100,0% @ crit. 1 of 2)
! Best Branches Non-fixed W Branch decision
* 14 065 948k 125,82s 4 (gap is 100,0% @ crit. 1 of 2)
New objective is 14 065; 5
! ----------------------------------------------------------------------------
! Search terminated by limit, 25 solutions found.
! Best objective : 14 065; 5 (gap is 100,0% @ crit. 1 of 2)
! Best bound : 0; 1
! ----------------------------------------------------------------------------
! Number of branches : 27 871 109
! Number of fails : 48 120 355
! Total memory usage : 218,0 MB (215,3 MB CP Optimizer + 2,7 MB Concert)
! Time spent in solve : 300,02s (299,84s engine + 0,18s extraction)
! Search speed (br. / s) : 92 953,3
! ----------------------------------------------------------------------------
I also searched similar topics, but didn't find the solution to this problem. Thanks for your help.
