CP Optimizer无法计算下界及搜索策略适配问题咨询

问题背景 #

我正在解决一个生产线配置问题，需完成以下任务：

• 将机器分配到工作站
• 将任务分配到工作站
• 为每台机器选择配置

约束条件包括节拍、任务优先级、机器选择限制等，目标是最小化总机器成本和使用的工作站数量。

我采用调度方法，用interval variables建模，遇到以下核心问题：

• 使用IterativeDiving搜索程序求解时，计算得到的下界为0; 1（机器成本；工作站数量），求解器提示无可行解；但用MultiPoint策略时，能找到可行解并优化至接近文献中的最优解。想知道为何除MultiPoint外的其他策略无法找到可行解？
• MultiPoint能高效找到可行解，但证明最优性/不可行性效率低。我尝试先用MultiPoint找到第一个解，再通过warmstart切换到IterativeDiving，但此时最小化问题的下界始终等于或高于当前解，导致搜索直接终止。
• 我尝试查找下界计算相关信息但无收获，推测模型存在问题但无法定位。

部分模型代码（简化版） #

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]);  
}   

搜索策略输出日志 #

Restart策略日志 #

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

MultiPoint策略日志 #

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

内容的提问来源于stack exchange，提问作者Loda