Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
3.3 kB
2
Indexable
Never
void bound(node_t* p, node_list_t* h, double* zp, double* x) {
    //printf("bound");
    if(p->z > *zp) {
        *zp = p->z;
        int i;
        for(i = 0; i < p->n; i++) {
            x[i] = p->x[i];
        }
        node_t* temp;
        node_t* next = h->first;
        node_t* prev;
        while(next != NULL) {
            temp = next;
            if(temp->z < p->z) {
                if(temp == h->first) {
                    h->first = temp->next;
                } else {
                    prev->next = temp->next;
                }
                next = temp->next;
                free(temp);
            } else {
                next = temp->next;
                prev = temp;
            }
        }
    }
}

int branch(node_t* q, double z) {
    //printf("branch");
    double min, max;
    if(q->z < z) {
        return 0;
    }
    int h;
    for(h = 0; h < q->n; h++) {
        if(!is_integer(&q->x[h])) {
            if(q->min[h] == -INFINITY) {
                min = 0;
            } else {
                min = q->min[h];
            }
            max = q->max[h];
            if(floor(q->x[h]) < min || ceil(q->x[h]) > max){
                continue;
            }
            q->h = h;
            q->xh = q->x[h];
            freeMatrix(q->a, q->m);
            free(q->a);
            free(q->b);
            free(q->c);
            free(q->x);
            return 1;
        }
    }
    return 0;
}

void succ(node_t* p, node_list_t* h, int m, int n, double** a, double* b, double* c, int k, double ak, double bk, double* zp, double* x) {
    //set h
    node_t* q = extend(p, m, n, a, b, c, k, ak, bk);
    if(q == NULL) {
        return;
    }
    //print_lin_program(q->m, q->n, q->b, q->c, q->a);
    q->z = simplex(q->m, q->n, q->a, q->b, q->c, q->x, 0);
    //print_lin_program(q->m, q->n, q->b, q->c, q->a);
    if(isfinite(q->z)){
        if(integer(q)){
            bound(q, h, zp, x);
        } else if (branch(q, *zp)) {
            if(h->first == NULL) {
                h->last = q;
                h->first = q;
            } else {
                h->last->next = q;
                h->last = q;
            }
            //add q to h
            return;
        }
    }
    free(q);
}

double intopt(int m, int n, double** a, double* b, double* c, double* x) {
    node_t* p = initial_node(m, n, a, b, c);
    node_list_t h; //set h = {p}
    h.first = p;
    h.last = p;
    double z = -INFINITY;
    p->z = simplex(p->m, p->n, p->a, p->b, p->c, p->x, 0);
    int i;
    if(integer(p) || !isfinite(p->z)) {
        z = p->z;
        if(integer(p)) {
            for(i = 0; i < n; i++) {
                x[i] = p->x[i];
            }
        }
        free(p);
        return z;
    }
    branch(p, z);
    while(h.first != NULL) {
        node_t* p1 = h.first;
        h.first = p1->next;
        if(h.last == p1) {
            h.last = NULL;
        }
        succ(p1, &h, m, n, a, b, c, p1->h, 1, floor(p1->xh), &z, x);
        succ(p1, &h, m, n, a, b, c, p1->h, -1, -ceil(p1->xh), &z, x);
        free(p1); 
    }
    if(z == -INFINITY) {
        return NAN; //return nan
    } else {
        return z;
    }
}