Sunday, June 21, 2009

Simplex method description

A comment led me to visit https://hudson.jboss.org/hudson/job/drools/lastSuccessfulBuild/artifact/trunk/target/docs/drools-solver/html_single/index.html. Section 1.3.1.3 has an interesting statement about the Simplex method:

Simplex turns all constraints and data into a big equation, which it transmutes into a mathematical function without local optima. It then finds an optimal solution to the planning problem by finding an optima of that mathematical function.

If the word Simplex was missing I would not recognize this is about the Simplex method. One big equation? (No word about not being suited to handle discrete variables).

The branch&bound section is also interesting. No mention about the unique feature that it provides bounds and hence an indication of the quality of the solution.

9 comments:

  1. ... and the local search definition is interesting.

    "Local search starts from an initial solution and evolves that single solution into a better and better solution."

    I wish it did always evolve to a better and better solution :-)

    Graham
    http://research-reflections.blogspot.com/

    ReplyDelete
  2. That's just the starter explanation. Later on it explains in detail, including about local optima etc.

    ReplyDelete
  3. What would be a better way to define local search, in a single sentence, for people who have never heard about it, without going in to many complicated details (so give the 10 000 m view)? And if it's a good sentence, can I reuse it in the manual? :)

    It's like saying "the world is round". We know it's really not a 100% round, nor a 100% eggshape.

    ReplyDelete
  4. I 'll adjust the manual about branch&bounds to mention that unique feature. Thanks for the feedback :)

    About the original topic: yes, my definition of simplex is probably wrong. However, as I am no expert in it at all, as I focus primarily on tabu search (etc),
    how would you correct the manual so it at least mentions simplex as an alternative method to solve planning problems? Or should I leave simplex out completely?

    Feed-back, corrections, patches and contributions on the drools-solver manual (as well as the source code) are very very welcome. Especially in the drools JIRA: https://jira.jboss.org/jira/browse/JBRULES

    ReplyDelete
  5. BTW: if you really want to turn your hair gray instantly, take a look at the current implementation of my SimulatedAnnealingAccepter.
    Patches welcome :) I have other priorities (conflict based statistics, ...) so fixing simulated annealing isn't on my short term todo list.

    ReplyDelete
  6. Geoffrey: I would suggest to try to find a coauthor who has some knowledge in this area. May be an academic. Not sure what the incentive could be. If your methods are sound and you really can solve difficult problems reasonably well, may be the prospect of an accompanying publishable paper can make it attractive for an academic to work on this.

    ReplyDelete
  7. Drools-solver's methods are sound: a very early version finished 4th in the international timetabling competition 2007's examination track and it has been confirmed to me that it has been used on several, different planning problems, some of which are already in production.

    However, all of those projects use the mature tabu search implementation. The simulated annealing implementation needs work and the branch & bound solver doesn't exist yet.

    It's an open source project, so the normal rules apply: anyone (researchers or non researchers) can contribute new features or improvements as a source code patch. I won't let those patches go stale and I 'll apply those patches (after peer review) fast. After a few good patches, you normally get svn commit rights so you can change the code directly and become part of the drools community team (like me).

    ReplyDelete
  8. I've created an issue about the remarks raised in the blog post:

    https://jira.jboss.org/jira/browse/JBRULES-2133

    Better proposals for any of the sections are welcome as comments on the issue or in a new issue :)

    ReplyDelete
  9. Fixed in subversion: the hudson manual site should update tonight.

    ReplyDelete