Code Sharing | Exact algorithm with new lower bound algorithm and dominance rules to solve the unrestricted container rummaging problem

Preface

The concepts and principles of the exact algorithm to solve the unrestricted container tumbling problem have been introduced before. This article is for code sharing. Before reading this article, please study the collection of tweet papers | Exact algorithm with new lower bound algorithm and dominance rules to solve the unrestricted container tumbling problem.

The project code is written based on C99, code download link: https://github.com/jinboszu/ucrp-idbb

Original paper: An exact algorithm for the unrestricted container relocation problem with new lower bounds and dominance rules", Bo Jin*, Shunji Tanaka, European Journal of Operational Research, Volume 304, Issue 2, 16 January 2023, Pages 494-514. https://doi.org/10.1016/j.ejor.2022.04.006

References:

• JZW (evaluation heuristic) algorithm: Jin, B., Zhu, W., & Lim, A. (2015). Solving the container relocation problem by an improved greedy look-ahead heuristic. European Journal of Operational Research, 240(3), 837–847. https://doi.org/10.1016/j.ejor.2014.07.038.
• SM-2 algorithm: Tricoire, F., Scagnetti, J., & Beham, A. (2018). New insights on the block relocation problem. Computers & Operations Research, 89, 127–139. https://doi.org/10.1016/ j.cor.2017.08.010.

Problem review

The main body of this algorithm is an iterative deepening search framework. Let’s review it based on the methods in the code.

Iteratively deepen the search framework:

• First, the input Perform multiple retrievable operations to minimize it to .
• Then use lowerbound in the code, that is, choose one of the methods LB-N, LB-TS, and LB-TS to calculate the root lower bound lb.
• Use upperbound in the code (corresponding to the Probe function), that is, the JZW or SM2 method to initialize the search threshold. , the method returns the length value and a known optimal solution .
• If the obtained lower bound is equal to the threshold, the optimal solution is found; if the lower bound is less than the threshold, use the search function. During the search process, use dominance rules to remove nodes that do not comply with the rules and obtain the child nodes. , to determine whether the search is completed. If it is not completed, a dynamic lower bound f is generated, and f is compared with .
• If f is greater than , indicating that the real threshold is greater than the current threshold , order , continue the cycle.
• If , then use the probe method to obtain the new solution S, and check whether the solution is optimal
• If the optimization is not obtained after the above steps, the nodes in the candidate branch set are sorted and traversed according to certain rules, and the search function is used again for each traversal.

The LB-N algorithm was not introduced in the previous tweet, and will be briefly introduced below.

LB-N:

1. First initialize the height vector , among which Represents the current height of stack s.
2. Entering the iteration, in each iteration, the algorithm finds the block with the highest priority at the highest level of the block heap, which is the target container.
3. X是包含所有目标容器的集合，其中目标容器的位置（s，t）满足s在S中，t在1到ηs之间，并且 equal to .
4. X⊥ is a subset of X that contains target containers that have no other target containers above them.
5. For each target container (s∗, t∗) in X⊥, the algorithm processes the following steps in sequence:
• The old height of record stack s∗ is .
• Set the height of stack s∗ to t∗ - 1, and remove container (s∗, t∗) and all containers above it.
• For each target container in X⊥, try to restore the height of stack s∗ to .
• The Check function is called to verify whether it is possible to get all containers above the target container (s*, t*) to be well placed by forcing a relocation operation. If the Check function returns True, the algorithm terminates immediately and returns B+1, where B is the total number of bad placement containers in configuration C.
• If the Check function returns False, the container (s*, t*) and all containers above it are removed again.
6. If all Check calls return False, the algorithm returns B.

Check function:

• First find the stack with the largest q among the non-full stacks for subsequent comparisons.

• Create a set D containing those stacks that can be used to place blocking containers. D contains a stack that satisfies one of the following conditions:

• The stack height is less than T;
• The stack height is T, but the top of the stack is a bad placement container, and the priority of the container above the stack is not higher than qmax.

• for each stack , perform the following steps:

• If there is a blocking container with a priority ps∗,t higher than the current θs value of all stacks in D, that is, no matter where this block moves, it will cause additional relocation, then True is returned, indicating that the container (s∗,t∗) cannot be well placed by forcing the relocation operation.
• Otherwise, select the stack s' in D with the largest value of θs such that θs' satisfies ps∗,t ≥ θs'. This is a greedy choice, meaning choosing a stack where container (s∗, t) can be relocated most easily. Update the value of θs' of stack s' to ps∗,t, indicating that container (s∗,t∗) is placed on stack s'.
• Initialize a temporary mass value θs to the current mass of stack s.
• Starting from the position of the target container (s∗, t∗), the blocking containers above the stack s are processed layer by layer, from top to bottom.

Code explanation

The solution to the problem is stored in the array hist, as shown in the data structure in the figure below.

List and rank arrays: The list is sorted by priority value, and rank stores the index of the list corresponding to different stacks.

//state.c
int compare_stack(int s1, int s2, int *h, int **q, int **b) {
return q[s1][h[s1]] != q[s2][h[s2]] ? q[s1][h[s1]] - q[s2][h[s2]]
: b[s1][h[s1]] - b[s2][h[s2]];
}
/*
compare_stack is used to compare the top elements of two stacks s1 and s2. It first compares the masses q of the top elements of stacks s1 and s2,
If not equal, return the difference in mass;
If the qualities are equal, the difference in badness is returned.
*/

static void adjust_left(state_t *state, int s){
int i = state->rank[s];
while (i > 0 && compare_stack(s, state->list[i - 1], state->h, state->q,
state->b) < 0) {
state->list[state->rank[state->list[i - 1]] = i] = state->list[i - 1];
i--;
}
state->list[state->rank[s] = i] = s;
}
/*
adjust_left is used to improve the ranking of heap s in the rank, that is, to move the rank value of heap s to the left in the rank array.
*/

static void adjust_right(state_t *state, int s) {//Similarly
int i = state->rank[s];
while (i < state->n_stacks - 1 &&
compare_stack(s, state->list[i + 1], state->h, state->q, state->b) >
0) {
state->list[state->rank[state->list[i + 1]] = i] = state->list[i + 1];
i++;
}
state->list[state->rank[s] = i] = s;
}


Therefore, in the relocate_out and relocate_in functions, the rank value of the heap s will be updated after the block is moved.

The following focuses on the search function.

//algorithm.c
static bool search(int level, branch_t *children) {
n_nodes++; // Increase node count

/*
* Check time limits
*/
if (++n_timer == timer_cycle) {
n_timer = 0;
if (get_time() >= end_time) {
return true; // If the time limit is reached, return true
}
#if defined(VERBOSE) || !defined(NDEBUG)
debug_info("running"); // Print debugging information
#endif
}

/*
* Current status
*/
int curr_lb = hist[level].lb; // current lower bound
state_t *curr_state = hist[level].state; // current state
memory_t *curr_memory = hist[level].memory; // current memory

//The following is the preparation parameter stage
/*
* Prepare TC, IB
*/
if (level > 0) {
int min_last_change_time = level + 1;
for (int s = 0; s < n_stacks; s++) {
min_last_change_time_fw[s] = min_last_change_time;
if (curr_state->h[s] < n_tiers &&
min_last_change_time > curr_state->last_change_time[s]) {
min_last_change_time = curr_state->last_change_time[s];
}
}

int max_last_relo_out_time = 0;
for (int s = n_stacks - 1; s >= 0; s--) {
max_last_relo_out_time_bw[s] = max_last_relo_out_time;
if (max_last_relo_out_time < curr_state->last_relo_out_time[s]) {
max_last_relo_out_time = curr_state->last_relo_out_time[s];
}
}
}

/*
* Prepare EA
*/
int leftmost = -1;
for (int s = 0; s < n_stacks; s++) {
if (curr_state->h[s] == 0) {
leftmost = s;
break;
}
}

/*
* Prepare SC, SD
*/
if (level > 0) {
memset(group_src_bw[0], 0, sizeof(int) * (max_prio + 1) * n_stacks);
for (int sk = 0; sk < n_stacks; sk++) {
if (curr_state->last_change_type[sk] == RELOCATE_OUT) {
int k = curr_state->last_change_time[sk];
int pk = path[k - 1].pri;
for (int s = 0; s < sk; s++) {
if (group_src_bw[pk][s] < k) {
group_src_bw[pk][s] = k;
}
}
}
}

memset(group_dst_bw[0], 0, sizeof(int) * (max_prio + 1) * n_stacks);
for (int dk = 0; dk < n_stacks; dk++) {
if (curr_state->last_change_type[dk] == RELOCATE_IN) {
int k = curr_state->last_change_time[dk];
int pk = path[k - 1].pri;
for (int d = 0; d < dk; d++) {
if (group_dst_bw[pk][d] < k) {
group_dst_bw[pk][d] = k;
}
}
}
}
}

/*
* Prepare branch
*/
copy_state_body(hist[level + 1].state, curr_state, true);
int size = 0;

//The function of this nested for loop is to traverse all possibilities of relocation and reduce the amount of calculation through rule judgment.
/*
* Enumerate source stack
*/
for (int sn = 0; sn < n_stacks; sn++) {
/*
* Check the feasibility of the source stack
*/
if (curr_state->h[sn] == 0) {
continue;
}

int pn = curr_state->p[sn][curr_state->h[sn]];
int q_sn = curr_state->q[sn][curr_state->h[sn]];
int lv = curr_state->l[sn][curr_state->h[sn]];
int lid = curr_memory->lid[sn][curr_state->h[sn]];

/*
* Lower bounding
*/
int temp_lb = curr_lb - (pn > q_sn) - (lid != -1);
if (level + 1 + temp_lb > best_lb) {//Roughly check whether the lower bound is better than the current optimal lower bound
continue;
}


/*
* Check TA, TC
*/
if (lv > 0) {
int k = lv;
int sk = path[k - 1].src;
if (curr_state->last_change_time[sk] == k &&
curr_state->last_change_type[sk] == RELOCATE_OUT) {
continue; // TA
}

if (min_last_change_time_fw[sn] < k) {
continue; // TC
}
}

/*
* Check SC
*/
if (level > 0) {
if (curr_state->last_change_time[sn] < group_src_bw[pn][sn]) {
continue;
}
}

/*
* Prepare temporary state and memory
*/
copy_state_head(temp_state, curr_state, true);
reuse_state_body(temp_state, hist[level + 1].state);

relocate_out(temp_state, sn, level + 1, true);

if (lid != -1) {
copy_memory(temp_memory, curr_memory, n_stacks, n_tiers);
temp_memory->n_layers--;
for (int s = 0; s < n_stacks; s++) {
temp_memory->lid[s][temp_memory->tau[lid][s]] = -1;
}
}

/*
* Update path when generating branches
*/
path[level].pri = pn;
path[level].src = sn;

/*
* Enumerate destination stack
*/
for (int dn = 0; dn < n_stacks; dn++) {
/*
* Check feasibility
*/
if (dn == sn || curr_state->h[dn] == n_tiers) {
continue;
}

/*
* Check EA
*/
if (curr_state->h[dn] == 0 && dn != leftmost) {
continue;
}

/*
* Check TB
*/
if (curr_state->last_change_time[dn] < lv) {
continue;
}

/*
* Check IB
*/
if (level > 0) {
int k = max_last_relo_out_time_bw[sn];
if (curr_state->last_change_time[sn] < k &&
curr_state->last_change_time[dn] < k) {
continue;
}
}

/*
* Check SA, SB, SD
*/
if (level > 0) {
if (curr_state->last_change_type[dn] == RELOCATE_OUT) {
int k = curr_state->last_change_time[dn];
int pk = path[k - 1].pri;
int dk = path[k - 1].dst;
if (pk == pn) {
if (curr_state->last_change_time[sn] < k) {
continue; // SA
}
if (curr_state->last_change_time[dk] == k) {
continue; // SB
}
}
}
if (curr_state->last_change_time[dn] < group_dst_bw[pn][dn]) {
continue; // SD
}
}

int q_dn = curr_state->q[dn][curr_state->h[dn]];

/*
* Lower bounding
*/
if (level + 1 + temp_lb + (pn > q_dn) > best_lb) {
continue;
}

state_t *child_state = children[size].child_state;

copy_state_head(child_state, temp_state, true);
reuse_state_body(child_state, hist[level + 1].state);

relocate_in(child_state, dn, pn, level + 1, true);

/*
* Update path when generating branches
*/
path[level].dst = dn;

bool dominated = false;
while (is_retrievable(child_state)) {
int s_min = child_state->list[0];
int p = child_state->p[s_min][child_state->h[s_min]];
int l = child_state->l[s_min][child_state->h[s_min]];

/*
* Check RA
*/
if (l > 0) {
int k = l;
int sk = path[k - 1].src;
if (child_state->last_relo_out_time[sk] == k &&
child_state->last_relo_in_time[sk] < k &&
hist[k - 1].state->q[sk][hist[k - 1].state->h[sk]] == p) {
dominated = true;
break;
}
}

/*
* Check RB
*/
if (l > 0) {
int k = l;
for (int d = 0; d < s_min; d++) {
if (hist[k - 1].state->h[d] < n_tiers &&
child_state->last_relo_out_time[d] < k &&
child_state->last_relo_in_time[d] < k &&
hist[k - 1].state->q[d][hist[k - 1].state->h[d]] >= p) {
dominated = true;
break;
}
}
if (dominated) {
break;
}
}

retrieve(child_state, level + 1, true);
}

if (dominated) {
continue;
}

/*
* Goal test
*/
if (child_state->n_blocks == 0) {
best_ub = level + 1;
memcpy(best_sol, path, sizeof(relocation_t) * best_ub);
time_to_best_ub = get_time();
#if defined(VERBOSE) || !defined(NDEBUG)
debug_info("goal");
#endif
return true;
}

/*
* Child lower bound
*/
memory_t *child_memory = children[size].child_memory;
bool inherited = false;
int inherited_n_layers = curr_memory->n_layers - (lid != -1);
if (inherited_n_layers == 0) {
inherited = has_empty_stack(child_state);
} else {
for (int s = 0; s < n_stacks; s++) {
if (child_state->h[s] == inherited_n_layers) {
inherited = true;
break;
}
}
}
if (inherited) {
copy_memory(child_memory, lid != -1 ? temp_memory : curr_memory,
n_stacks, n_tiers);
child_memory->lid[dn][curr_state->h[dn] + 1] = -1;
}
int child_lb;
switch (lb_type) {
case LB_N:
child_lb = curr_lb - 1 > child_state->n_bad
? curr_lb - 1
: lb_n_impl(child_state, array_s1, array_s2, array_s3,
array_s4);
break;
case LB_TS:
child_lb = inherited ? child_state->n_bad + child_memory->n_layers
: lb_ts_impl(child_state,
best_lb - level - child_state->n_bad,
array_s1, child_memory);
break;
default: // LB_PS:
child_lb =
inherited
? child_state->n_bad + child_memory->n_layers
: lb_ps_impl(child_state, best_lb - level - child_state->n_bad,
pending, active, array_s1, array_s2, child_memory);
break;
}

/*
* Lower bounding
*/
if (level + 1 + child_lb > best_lb) {
continue;
}

/*
* Probing
*/
//The explanation of probing is in the next paragraph
if (level + 1 + child_lb == best_lb - 1) {
n_probe++;
if (ub_type == JZW || ub_type == HYBRID) {
copy_state(probe_state, child_state, false);
int new_len = jzw_impl(probe_state, path, level + 1, best_ub - 1);
if (new_len != -1) {
best_ub = new_len;
memcpy(best_sol, path, sizeof(relocation_t) * best_ub);
time_to_best_ub = get_time();
#if defined(VERBOSE) || !defined(NDEBUG)
debug_info("update");
#endif
if (best_lb == best_ub) {
return true;
}
}
}
if (ub_type == SM2 || ub_type == HYBRID) {
copy_state(probe_state, child_state, false);
int new_len = sm2_impl(probe_state, path, level + 1, best_ub - 1);
if (new_len != -1) {
best_ub = new_len;
memcpy(best_sol, path, sizeof(relocation_t) * best_ub);
time_to_best_ub = get_time();
#if defined(VERBOSE) || !defined(NDEBUG)
debug_info("update");
#endif
if (best_lb == best_ub) {
return true;
}
}
}
}

children[size].pri = pn;
children[size].src = sn;
children[size].dst = dn;
children[size].q_src = q_sn;
children[size].q_dst = q_dn;
children[size].child_lb = child_lb;
size++;
}
}

// If there are sub-branches, sort the sub-branches and search recursively
if (size > 0) {
qsort(children, size, sizeof(branch_t), compare_branch);

state_t *child_state = hist[level + 1].state;

for (int i = 0; i < size; i++) {
path[level].pri = children[i].pri;
path[level].src = children[i].src;
path[level].dst = children[i].dst;

hist[level + 1].lb = children[i].child_lb;
reuse_state_head(child_state, children[i].child_state);
hist[level + 1].memory = children[i].child_memory;

int dn = path[level].dst;
if (child_state->h[dn] == curr_state->h[dn] + 1) {
set_block(child_state, dn, child_state->h[dn], path[level].pri,
level + 1, true);
}

if (search(level + 1, children + size)) {
return true;
}
}
}

return false;
}


Both JZW and SM-2 are used to search nodes and select solutions with fewer relocations as results.

In the search function, when calling the JZW function, try to find a better solution at level + 1, with best_ub - 1 as the upper bound, where best_ub is the current best upper bound. The jzw_impl function will return the new length (new_len) as the upper bound; if new_len is not equal to -1, it means that a better upper bound has been found, then it will update best_ub to new_len, copy the path information in path to best_sol, and also record the time to track when the new upper bound is reached. If the best lower bound has been reached at this time (best_lb is equal to best_ub), true is returned to indicate that the problem has been solved. The same applies when calling SM2.

int jzw_impl(state_t *state, relocation_t *path, int len, int len_limit) {
if (len + state->n_bad > len_limit) {
return -1;
}

int n_stacks = state->n_stacks;
int n_tiers = state->n_tiers;
int *h = state->h;
int *list = state->list;
int *rank = state->rank;
int **p = state->p;
int **q = state->q;
int **b = state->b;

while (state->n_bad > 0) {
while (is_retrievable(state)) {
retrieve(state, len, false);
}

int q_min = q[list[0]][h[list[0]]];//list[0] is the stack with the smallest q
int i_next = -1;
for (int i = 0; i < n_stacks; i++) {//Find the moved block
int s = list[i];
if (q[s][h[s]] > q_min) {
break;
}

//The following inequality is true, then there are enough vacancies in the stack except s, and bad blocks can be moved in
if (b[s][h[s]] <= (n_stacks - 1) * n_tiers - (state->n_blocks - h[s])) {
i_next = i;
break;
}
}
if (i_next == -1) {
return -1;//No space, cannot move
}

int i_max;
int q_max;
for (int i = n_stacks - 1;; i--) {
int s = list[i];
if (i != i_next && h[s] < n_tiers) {
i_max = i;//Find the empty space that can be moved into
q_max = q[s][h[s]];//Record the q value of this position
break;
}
}

bool has_multi_q_max = false;
if (q_min < q_max) {//Check whether there are multiple stacks with the same q_max
for (int i = i_max - 1;; i--) {
int s = list[i];
if (q[s][h[s]] < q_max) {
break;
}
if (h[s] < n_tiers) {
has_multi_q_max = true;
break;
}
}
}

int src = list[i_next];
int dst;

//Find the stack that is moved in and out
if (p[src][h[src]] <= q_max) {//Find dst
for (int i = i_next + 1;; i++) {
int s = list[i];
if (h[s] < n_tiers && p[src][h[src]] <= q[s][h[s]]) {
dst = s;//The priority value of src is less than q[s][h[s] and can be moved into s
break;
}
}

int x = -1;
if (h[dst] < n_tiers - 1) {//Whether the target stack has vacancies
for (int i = 0; i < rank[dst]; i++) {//Find src that may be updated
int s = list[i];
if (s != src && b[s][h[s]] > 0 && p[src][h[src]] <= p[s][h[s]] &&
p[s][h[s]] <= q[dst][h[dst]] &&
(x == -1 || p[x][h[x]] < p[s][h[s]])) {
x = s;//Select a bad block whose priority value is not less than src and not greater than the q value of dst
}
}
}
if (x != -1) {
src = x;//Change the block of src to the found x
}
}

else {//p[src][h[src]] > q_max, that is, if src is still a bad block wherever it is moved, try to find a new src.
if (len + state->n_bad == len_limit) {//Whether the length limit is reached
return -1;
}

int i_opt = -1; //i_optimal, which is the optimal i, here is the potential target stack
//Starting from the current i_max, increase or decrease i in the dir direction. The initial value of dir is 1, indicating forward traversal.
for (int dir = 1, i = i_max;; i += dir) {
int s = list[i];
if (i == n_stacks || (i > i_max && q[s][h[s]] > q_max)) {
dir = -1; //i exceeds the maximum stack number/i is greater than the current imax and q is greater than qmax
i = i_max - 1; //In this case, reverse the traversal direction,
s = list[i];//Get the stack value corresponding to imax-1
}
if (q[s][h[s]] == q_min) {//If a stack with the same q value as list[0] is found, i-opt is not found
break;
}
if (b[s][h[s]] == 0 && p[src][h[src]] <= q[s][h[s] - 1] &&
(i != i_max || has_multi_q_max)) {
//There are no bad blocks on s, i is not imax or there are multiple heaps with qmax, and the src priority value is not greater than the q value of the previous layer of s
i_opt = i;
break;
}
}

if (i_opt != -1) {
src = list[i_opt];
for (int dir = -1, i = i_opt - 1;; i += dir) {//reverse traversal
int s = list[i];
if (i < i_opt && q[s][h[s]] < p[src][h[src]]) {//Increase the number of s bad blocks after placing src
dir = 1;
i = i_opt + 1;
s = list[i];
}
if (h[s] < n_tiers) {//After placing src, the number of bad blocks in s will not be increased and there will be vacancies at s
dst = s;
break;
}
}

int x = -1;
if (h[dst] < n_tiers - 1) {//The number of dst vacancies is greater than 1
for (int i = 0; i < rank[dst]; i++) {//Traverse the stack ranked in front of dst
int s = list[i];
//There are still bad heap blocks on s. The priority value of s is not less than src, not greater than the q value of dst, or there is a priority value greater than x.
if (s != src && b[s][h[s]] > 0 && p[src][h[src]] <= p[s][h[s]] &&
p[s][h[s]] <= q[dst][h[dst]] &&
(x == -1 || p[x][h[x]] < p[s][h[s]])) {
x = s;
}
}
}
if (x != -1) {
src = x;
}
} else {
dst = list[i_max]; // If i_opt is not found, select i_max as dst
if (h[dst] == n_tiers - 1) {//dst has only one empty position
for (int k = 1; k < b[src][h[src]]; k++) {//src has more than 1 bad blocks
if (p[src][h[src] - k] < p[src][h[src]]) {//If the kth priority from the top down is larger
for (int i = i_max - 1; i >= 0; i--) {//Traverse the stack to the left
int s = list[i];
if (s != src && h[s] < n_tiers) {//Find the free stack closest to imax
dst = s;
break;
}
}
break;
}
}
}
}
}

if (path != NULL) {
path[len].pri = p[src][h[src]];
path[len].src = src;
path[len].dst = dst;
}//Update path
relocate(state, src, dst, ++len, false);//Execute and record the relocate operation
}

return len;
}


SM-2:

int src = -1;
int dst = -1;
int best_diff = INT_MAX;

if (q_min < q_max) {
for (int i = 0; i < i_max; i++) {
int from = list[i];
if (h[from] == 0) {
// empty stack
break;
}
if (b[from][h[from]] > 0 && p[from][h[from]] <= q_max) {
// from has bad blocks and the priority is not greater than qmax
for (int j = i + 1;; j++) {
// after i
int to = list[j];
int diff = q[to][h[to]] - p[from][h[from]];
if (diff >= best_diff) {
break;
}
if (h[to] < n_tiers && diff >= 0) {
// diff greater than 0 means that the number of bad blocks will not increase after moving in
src = from;
dst = to;
best_diff = diff;
break;
}
}
}
}
}

if (best_diff == INT_MAX) {
// No matter where it is moved, the number of bad blocks will increase
if (len + state->n_bad == len_limit) {
return -1;
}

//Check again if there is a block between q_min and q_max that can be moved
if (q_min < q_max) {
for (int i = 0; i < n_stacks; i++) {
int from = list[i]; // current source stack
// If the q value of the source stack is greater than q_max, exit the loop
if (q[from][h[from]] > q_max) {
break;
}
// If the source stack has no bad blocks and is not i_max or there are multiple maximum q values
if (b[from][h[from]] == 0 && (i != i_max || has_multi_q_max)) {
int s_bad = -1; //The most suitable bad block stack
int s_bad_alt = -1; // Alternative bad block stack

// Traverse the stack list again to find possible target stacks
for (int j = 0; j < n_stacks; j++) {
int s = list[j]; // current stack
// If the q value of the s stack is greater than or equal to the q value of the second level of the from stack, exit the loop; if it is less than the q value, continue
if (q[s][h[s]] >= q[from][h[from] - 1]) {
break;
}
int diff = q[from][h[from] - 1] - p[s][h[s]];
// If the s stack has bad blocks and the difference is greater than or equal to 0 and less than the optimal difference
if (b[s][h[s]] > 0 && diff >= 0 && diff < best_diff) {
//Update bad block stack and alternative bad block stack
if (s_bad == -1 || p[s_bad][h[s_bad]] < p[s][h[s]]) {
s_bad_alt = s_bad;
s_bad = s;
} else if (s_bad_alt == -1 || p[s_bad_alt][h[s_bad_alt]] < p[s][h[s]]) {
s_bad_alt = s;
}
}
}

// If a suitable bad block stack is found
if (s_bad != -1) {
int to = -1; // target stack
// Traverse the stack list again, this time in reverse to find possible target stacks
for (int dir = -1, j = i - 1;; j += dir) {
int s = list[j]; // current stack
// If the current direction is to the left and the q value of the s stack is less than the q value of the from stack, change the direction and continue searching.
if (dir == -1 && q[s][h[s]] < p[from][h[from]]) {
dir = 1;
j = i + 1;
s = list[j];
}
int diff = q[from][h[from] - 1] - p[s_bad][h[s_bad]] + q[s][h[s]] - p[from][h[from]]; // Calculate the difference
// If the difference is greater than or equal to the optimal difference, exit the loop
if (diff >= best_diff) {
break;
}
// If there is space in the target stack, update the target stack
if (h[s] < n_tiers) {
to = s;
break;
}
}

// If a suitable target stack is found
if (to != -1) {
// If the bad block stack is not the target stack, update the source and target stacks and the best difference
if (s_bad != to) {
src = from;
dst = to;
best_diff = q[from][h[from] - 1] - p[s_bad][h[s_bad]] + q[to][h[to]] - p[from][h[from]];
} else {
if (s_bad_alt != -1) {
// Calculate the migration difference from s_bad_alt to to (the number of bad blocks is reduced and moved to a lower priority position)
int diff = q[from][h[from] - 1] - p[s_bad_alt][h[s_bad_alt]] + q[to][h[to]] - p[from][h[from]];

if (diff < best_diff) {
// If the migration difference is smaller, update src and dst and the best difference value
src = from;
dst = to;
best_diff = diff;
}
}

// Traverse the stack before or after rank[to]
for (int dir = (rank[to] < i ? -1 : 1), j = rank[to] + dir; j <= i_max; j += dir) {
int s = list[j]; // current stack
if (dir == -1 && q[s][h[s]] < p[from][h[from]]) {
dir = 1;
j = i + 1;
s = list[j];
}

// Calculate the migration difference from s_bad to s
int diff = q[from][h[from] - 1] - p[s_bad][h[s_bad]] + q[s][h[s]] - p[from][h[from]];

if (diff >= best_diff) {
break; // If the difference is greater than or equal to the current best difference, exit the loop
}

if (h[s] < n_tiers) {
src = from;
dst = s; // Update src and dst
best_diff = diff; // Update the best difference value
break;
}
}
}
}
}
}
}
}

if (src == -1) {//Still not found, use inext and imax directly
src = list[i_next];
dst = list[i_max];
}
}


The above is the entire content of code analysis, I hope it will be helpful to you.

Machine-translated from the Chinese original 代码分享｜带新下界算法和支配规则的精确式算法解决非限制性集装箱翻箱问题 (published 2023-12-19). WeChat original ↗