projets/lagrange.cpp at main · Flastre/projets · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
struct repLgr{
    double solDual;
    vector<double> sousGradient;
};

repLgr lgrRelaxe(MKPInstance& instance, int idObjet, vector<double>& lambda) {
    repLgr rep;
    rep.solDual = 0;
    for(int j = 0; j < instance.k; j++) {
        rep.sousGradient.push_back(-instance.capacities[j]);
    }

    for(int i = 0; i < instance.k; i++) {
        rep.solDual += lambda[i] * instance.capacities[i];
    }

    for(int i = idObjet; i < instance.n; i++) {
        double curSomme = 0;
        for(int j = 0; j < instance.k; j++) {
            curSomme += instance.weights[j][i] * lambda[j];
        }

        if(instance.profits[i] - curSomme > 0) {
            rep.solDual += instance.profits[i] - curSomme;
            for(int j = 0; j < instance.k; j++) {
                rep.sousGradient[j] += instance.weights[j][i];
            }
        }
    }

    return rep;
}

double descente(MKPInstance& instance, int idObjet) {
    vector<double> lambda;
    for(int i = 0; i < instance.k; i++) {
        lambda.push_back(alea(5, 10));
    }


    int k = 1;

    double delta = 100000;
    double bestSol = delta;
    double preced = delta;

    while(k < 30 && delta/bestSol > 0.005) {
        repLgr cur = lgrRelaxe(instance, idObjet, lambda);
        double pas = (double)1/(k*k);

        vector<double> sg = cur.sousGradient;

        for(int coord = 0; coord < instance.k; coord++) {
            lambda[coord] += pas * sg[coord];
            lambda[coord] = max(0., lambda[coord]);
        }

        bestSol = min(bestSol, cur.solDual);

        if(k > 1) {
            delta = preced - cur.solDual;
            preced = cur.solDual;
        }
        if(delta < 0) delta = -delta;
        k++;
    }

    return bestSol;
}

int valOpti = 0;

void bb(MKPInstance& instance, int idObjet, bool active) {
    for(int i = 0; i < instance.capacities.size(); i++) {
        if(instance.capacities[i] < 0) {
            return;
        }
    }

    if(instance.n == idObjet) {
        valOpti = max(valOpti, instance.valCur);
        return;
    }

    if(active && instance.valCur + descente(instance, idObjet) < valOpti) {
        return;
    }

    updateInstance(instance, idObjet, 1);
    bb(instance, idObjet+1, active);

    updateInstance(instance, idObjet, -1);
    bb(instance, idObjet+1, active);

    return;
}