Éviter la recherche d'une solution MIP lorsque la solutio
Original reporter: ikus060
Created At: 2012-09-06 13:34:34
Pour plusieurs instance d'optimisation, la rechercherche d'une solution à nombre entier n'est pas nécéssaire. C'est-à-dire, si la valeur de l'objectif est égal à zéro (0) avec la méthode simplex, il n'est pas nécéssaire de calculer une solution à nombre entier.
Voici un example. Ici, on t'ente de maximizer l'affectation d'un employé à son poste préféré. Avec la méthode simplex, l'employé est assigné aucune fois (l'objectif est égal à 0). Ainsi, il n'est pas nécéssaire de trouver une solution à nombre entier.
09:24:40.810 [ModalContext] INFO c.p.core.GeneratePlanifContext - Maximize employee 4 preferred position.
09:24:40.810 [ModalContext] DEBUG c.p.core.GeneratePlanifContext - Maximize employee 4 preferred team.
09:24:40.810 [ModalContext] DEBUG c.p.core.GeneratePlanifContext - Check feasiblility with employee 4 working on team 0.
09:24:40.812 [ModalContext] TRACE c.p.core.GeneratePlanifContext - GLPK Integer Optimizer, v4.45
09:24:40.812 [ModalContext] TRACE c.p.core.GeneratePlanifContext - 2884 rows, 12579 columns, 38911 non-zeros
09:24:40.812 [ModalContext] TRACE c.p.core.GeneratePlanifContext - 12579 integer variables, 12529 of which are binary
09:24:40.812 [ModalContext] TRACE c.p.core.GeneratePlanifContext - Preprocessing...
09:24:40.835 [ModalContext] TRACE c.p.core.GeneratePlanifContext - 2498 rows, 10735 columns, 33155 non-zeros
09:24:40.835 [ModalContext] TRACE c.p.core.GeneratePlanifContext - 10735 integer variables, all of which are binary
09:24:40.835 [ModalContext] TRACE c.p.core.GeneratePlanifContext - Scaling...
09:24:40.837 [ModalContext] TRACE c.p.core.GeneratePlanifContext - A: min|aij| = 1.000e+00 max|aij| = 1.000e+00 ratio = 1.000e+00
09:24:40.837 [ModalContext] TRACE c.p.core.GeneratePlanifContext - Problem data seem to be well scaled
09:24:40.837 [ModalContext] TRACE c.p.core.GeneratePlanifContext - Constructing initial basis...
09:24:40.843 [ModalContext] TRACE c.p.core.GeneratePlanifContext - Size of triangular part = 2498
09:24:40.844 [ModalContext] TRACE c.p.core.GeneratePlanifContext - Solving LP relaxation...
09:24:40.844 [ModalContext] TRACE c.p.core.GeneratePlanifContext - GLPK Simplex Optimizer, v4.45
09:24:40.844 [ModalContext] TRACE c.p.core.GeneratePlanifContext - 2498 rows, 10735 columns, 33155 non-zeros
09:24:40.847 [ModalContext] TRACE c.p.core.GeneratePlanifContext - 118840: obj = 0.000000000e+00 infeas = 2.970e+02 (0)
09:24:40.864 [ModalContext] TRACE c.p.core.GeneratePlanifContext - 119000: obj = 0.000000000e+00 infeas = 2.750e+02 (0)
09:24:40.932 [ModalContext] TRACE c.p.core.GeneratePlanifContext - 119500: obj = 0.000000000e+00 infeas = 2.378e+02 (0)
09:24:40.997 [ModalContext] TRACE c.p.core.GeneratePlanifContext - 120000: obj = 0.000000000e+00 infeas = 1.900e+02 (0)
09:24:41.076 [ModalContext] TRACE c.p.core.GeneratePlanifContext - 120500: obj = 0.000000000e+00 infeas = 1.640e+02 (0)
09:24:41.146 [ModalContext] TRACE c.p.core.GeneratePlanifContext - 121000: obj = 0.000000000e+00 infeas = 1.170e+02 (0)
09:24:41.237 [ModalContext] TRACE c.p.core.GeneratePlanifContext - 121500: obj = 0.000000000e+00 infeas = 7.638e+01 (0)
09:24:41.331 [ModalContext] TRACE c.p.core.GeneratePlanifContext - 122000: obj = 0.000000000e+00 infeas = 2.050e+01 (0)
09:24:41.456 [ModalContext] TRACE c.p.core.GeneratePlanifContext - 122500: obj = 0.000000000e+00 infeas = 3.167e+00 (0)
09:24:41.560 [ModalContext] TRACE c.p.core.GeneratePlanifContext - *122923: obj = 0.000000000e+00 infeas = 2.518e-15 (0)
09:24:41.560 [ModalContext] TRACE c.p.core.GeneratePlanifContext - OPTIMAL SOLUTION FOUND
09:24:41.561 [ModalContext] TRACE c.p.core.GeneratePlanifContext - Integer optimization begins...
09:24:41.562 [ModalContext] TRACE c.p.core.GeneratePlanifContext - +122923: mip = not found yet <= +inf (1; 0)
09:24:42.054 [ModalContext] TRACE c.p.core.GeneratePlanifContext - Applying FPUMP heuristic...
09:24:42.059 [ModalContext] TRACE c.p.core.GeneratePlanifContext - Pass 1
09:24:42.526 [ModalContext] TRACE c.p.core.GeneratePlanifContext - Pass 2
09:24:43.560 [ModalContext] TRACE c.p.core.GeneratePlanifContext - Pass 3
09:24:44.946 [ModalContext] TRACE c.p.core.GeneratePlanifContext - Pass 4
09:24:46.013 [ModalContext] TRACE c.p.core.GeneratePlanifContext - Pass 5
09:24:48.168 [ModalContext] TRACE c.p.core.GeneratePlanifContext - +123748: mip = not found yet <= 0.000000000e+00 (2; 0)
09:24:53.549 [ModalContext] TRACE c.p.core.GeneratePlanifContext - +126064: mip = not found yet <= 0.000000000e+00 (6; 0)
09:24:58.805 [ModalContext] TRACE c.p.core.GeneratePlanifContext - +127331: mip = not found yet <= 0.000000000e+00 (11; 0)
09:25:04.835 [ModalContext] TRACE c.p.core.GeneratePlanifContext - +128491: mip = not found yet <= 0.000000000e+00 (17; 0)
09:25:09.926 [ModalContext] TRACE c.p.core.GeneratePlanifContext - +129778: mip = not found yet <= 0.000000000e+00 (22; 0)