- Pablo Jensen, chercheur à l'ENS Lyon dont j'ai incidemment commencé la lecture de l'ouvrage Entrer en matière il y a quelques temps, vient de publier un article sur l'adaptation des techniques de calcul des interactions atomiques au choix optimal de l'emplacement d'un magasin. Je n'ai pas encore lu le pdf, mais il me semble qu'il ne tient pas compte d'un phénomène majeur d'agglomération des commerces dans les quartiers attractifs. Si une boulangerie gagnera sûrement à s'implanter suffisamment loin de potentiels concurrents, un magasin de chaussures paumé au milieu de nulle part aura sûrement moins de clients que s'il est situé sur une artère commerçante.
- Comme déjà dit, Vladimir Kramnik et Vesselin Topalov s'affrontent actuellement pour savoir lequel des deux gagnera le titre de champion du monde d'échecs réunifié. Ils ont cependant failli gagner tous les deux le titre de finalistes les plus ridicules de l'histoire des échecs, et peut-être même de l'histoire des sports/jeux en général. Ca a commencé lorsque le team Topalov s'est plaint des innombrables pauses-pipi de Kramnik pendant un match (plus de 50 au cours de la deuxième rencontre !), le soupçonnant plus ou moins directement de profiter de ces pauses pour tricher (chaque joueur disposant d'une cabine personnelle, évidemment hors de toute surveillance pendant les rencontres). Les organisateurs décidèrent alors de condamner les deux cabines personnelles et d'en ouvrir une troisième, commune aux deux joueurs. Kramnik, outré qu'on puisse le soupçonner et prétextant qu'il avait besoin de place pour marcher, décida alors de ne pas se présenter devant l'échiquier au début de la cinquième partie (il menait alors 3-1). Il fut sanctionné par la perte d'un point, et la rencontre passa à deux doigts de l'implosion. Les choses semblent cependant s'être calmées, les deux joueurs s'étant à nouveau serré la main (l'histoire ne dit pas si Kramnik s'était lavé les siennes en sortant des toilettes avant de ce faire ...).
- Vicnent, j'ai besoin de tes lumières là-dessus. Pas encore eu le temps de m'y pencher, mais la formulation de l'abstract m'interpelle ... :
In this paper, we present a first linear programming formulation of the Traveling Salesman Problem (TSP). The proposed linear program is very-large scale. However, it can be explicitly stated in polynomial time, having O(n9) variables and O(n7) constraints. Hence, it resolves in the affirmative, the very-long-standing and central issue in Operations Research and Mathematics in general of the equality of computational complexity classes P and NP.
- Pas encore lu non plus, mais ce n'est pas une raison pour ne pas le partager, un papier sur la dynamique du marketing viral
3 réactions
1 De Vicnent - 03/10/2006, 21:21
je me lance : si en dehors de toute considération de forme (il n'est pas connu, il rédige sous word au lieu de LaTeX, il n'est pas en R&D, son papier est soumis à Arxiv au lieu de Math Prog (mon rêve intérieur...), il n'a jamais publié etc), mais que je considère plutôt :
1/ <i>"The proposed linear program is "</i> de l'abstract avec ce qui est écrit comme "overall model" dans son paragraphe 2.1 (qui est un "integer linear programming model"), ça part mal.
2/ Mais si on considère par la suite qu'il en propose une relaxation (même avec un simplex, hum...) ça va mieux.
3/ sauf quand il explique que les deux problèmes sont équivalents (corollaire 1 et 2 page 28), même en changeant une partie de la formulation initiale pour passer de IP à IP barre (=LP).
Ok, c'est un peu rapide, mais l'idée est là : si on savait transformer tout problème en variable duale d'une programmation linéaire entière (et binaire pour le coup) en programmation linéaire via une relaxation reformulée, ça se saurait :-) Faudrait que je passe plus (et en fait trop) de temps pour pointer exactement en quoi les deux enveloppes convexes ne sont pas équivalentes.
D'un autre coté, c'est pas mal, ça fait passer P=NP, avec pour le TSP, si 1000 villes, alors 10^27 variables à coder, avec 10^21 contraintes, le tout avec un simplex... (bon, ok, LP est dans P, mais son simplex, c'est bête...)
2 De vicnent - 16/12/2006, 14:49
il semblerait que j'aie vu juste.
je cite tout : (+ coord article inside)
(from news : sci.op-research ) (voir "key point...)
Dear Group Members,
I start discussion about Mr. Diabys algorithm claimed to be polynomial
time solver for any TSP (known to be NP-complete) problem. Article can
be found on arxiv.org/abs/cs.CC/06090... with its twin about QAP
arxiv.org/abs/cs.CC/06090... Second one was even presented on
IMECS 2006 conference where author obtained merit award for it.
In very short summary. Author builds up Integer Linear Programming
problem consisting of n^9 variables and n^7 boundaries. He shows its
correspondence to TSP. Then he relaxes integer assumption and obtain LP
problem (with number of variables O(n^9) and O(n^7) boundaries).
Problem is, that after some research I have prepared counter-example:
arxiv.org/abs/cs.CC/06101... for n=32 (there is source code of
program generating variables, their values, boundaries and whole LPT
instance - compatible with SoPlex - for BLP model presented in
article - resources are available to download (links are in my
paper)).
After some discussion I have written another article "Why LP cannot
solve NP-complete problems" - it is available here:
arxiv.org/abs/cs.CC/06110... Key point is that for plytope
representing NP-complete problem there are O(2^n) vertexes, polytope
has O(2^n) facets and that's why polynomial number of restrictions
cannot "see" them all. And if it omits some of them, then situation
analogical to presented in picture www.teycom.pl/diaby/eq2.p...
may occur.
Author claims to have proved that:
forall t in TSP-solution exists b in BLP-feasible-solutions t subset b
But what my point is, that it does not prove (or disprove) my thought:
exists b in BLP-feasible-solutions forall t in TSP-tours
overallCost(b)<overallCost(t)
My counter example is quite simple - there are 32 cities in four
valleys. Cost of traveling within valley is 1 and cost of mountain
re essaie de postage n°1 après "MySQL Error : 2013 - Lost connection to MySQL server during query" :-)
3 De Eric C. - 19/12/2006, 15:34
(Après c'est SpamClear qui a considéré ton commentaire comme du spam, vu comment je l'ai dressé pour le moment il doit considérer que tout ce qui est écrit en anglais et avec des URLs dedans en est ...)
Merci pour les liens, ça va me faire un peu de lecture en plus (si j'ai le courage, mais je crains que ça ne vole trop haut pour moi).