You're looking at Less Wrong's discussion board. This includes all posts, including those that haven't been promoted to the front page yet. For more information, see About Less Wrong.

Thomas comments on Open thread, Jul. 11 - Jul. 17, 2016 - Less Wrong Discussion

4 Post author: MrMind 11 July 2016 07:09AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Article Navigation

Comments (131)

Comments (131)

You are viewing a single comment's thread. Show more comments above.

Comment author: Thomas 12 July 2016 04:45:09PM 1 point [-]

parallel genetic algorithm

I wouldn't say it's "genetic algorithm", I prefer the term "evolution algorithm".

In what way is it more automatic than existing similar apps?

We did some testings. For example, we took some existing schedules and optimized them with our tool. The difference was substantial.

We also did some packings of circles inside a square and some spheres inside a cube, denser than it has been previously achieved.

We have built some 3D croswords 8 by 8 by 8 letters with no black field at all - field with English words.

I don't know if optalaner can do the same. I think not.

spreadsheet, some soft, some hard and it spits out a few of the top solutions

Every constrain has its own user specified weight. From 0 to 10^12 and every integer inside this interval. This is the measure of how soft or hard a constrain is.

Comment author: Vitor 12 July 2016 09:56:20PM 2 points [-]

Did you also test what other software (optaplanner as mentioned by HungryHobo, any SAT solver or similar tool) can do to improve those same schedules?

Did you run your software on some standard benchmark? There exists a thing called the international timetabling competition, with publicly available datasets.

Sorry to be skeptical, but scheduling is an NP-hard problem with many practical applications and tons of research has already been done in this area. I will grant that many small organizations don't have the know-how to set up an automated tool, so there may still be a niche for you, specially if you target a specific market segment and focus on making it as painless as possible.

Comment author: Thomas 13 July 2016 05:25:32AM *  0 points [-]

We did some benchmarks. Sometimes we did it well, sometimes not that well.

For example in the case of Job Shop Scheduling benchmark we were unable to break a single record. There are records waiting to be break in JSS area, but we haven't broken a single one.

But we are still holding some (years old) packing records right now.

One may say, that JSS is the base of every scheduling and that packing is not. In fact, the real life scheduling is more complicated than either one of those benchmarks. We have many more constrains in real life. And it turns out, that many constrains somehow help the evolution to find trade-offs.

Comment author: HungryHobo 13 July 2016 10:24:37AM 1 point [-]

if you're the holders of some records for certain problem types then that grabs my interest.

I'd suggest leading with that since it's a strong one.

Comment author: gjm 13 July 2016 03:49:04PM -2 points [-]

Not necessarily for their target market.

Comment author: NancyLebovitz 14 July 2016 01:04:13PM 0 points [-]

I belief that being flexible about target markets is one of the major ways businesses grow.

Comment author: Thomas 14 July 2016 04:15:03PM *  0 points [-]

The best way to win principals is to show them that a ridiculously complex constrain may be applied and calculated automatically.

  • 4.5 school hours of S per week (4 hours on odd weeks and 5 hours on even weeks)
  • when there is the fifth hour in the week, then this hour may be the second hour of the subject S on that day
  • if it is on the same day, it should be immediately after the previous hour of the subject S
  • in the above case, it must be the last hour for the teacher
  • three classes of students are divided into 5 groups for the subject S
  • there are 4 teachers for those 5 groups, one teacher teaches groups number 2 and 4
  • there is a given list of students for groups 1, 3 and 5 and a combined list for students for groups 2 and 4
  • computer should divide the combined list into two separated lists (2 and 4) but they must not differ for more than 4 students in size
  • as one of those groups (2 or 4) are always idle, the subject M which is equally divided, must be taught then - or the S should be the first hour of the day
  • for there are only 4 hours of subject M per week
  • there are only 3 teachers of M
  • there are also 3 hours of subject A per week for those same students in 5 differently set groups
  • there are 5 teachers of A, but one of them also teaches the group number 1 of S
  • it would be nice but not mandatory if the number of waiting hours for students were 0

This is a real life example, I have discussed 1 hour ago with one of the teachers (math teacher) in one of our schools. It is not the most complex demand we had, by far.

S = Slovenian language M = Math A = Anglescina (guess what that is)

Comment author: HungryHobo 15 July 2016 09:22:21AM 1 point [-]

fair enough, I was underwhelmed by your initial post describing it but I agree that showing that your system can handle weird constraints in real examples is an excellent demonstration.

The record thing to me just happens to be a good demonstration that you're not just another little startup with some crappy schedualling software, you're actually at the top of the field in some areas.

Comment author: Lumifer 12 July 2016 05:24:35PM 0 points [-]

If your algorithm is actually the best-of-class for this problem, there are serious applications for it outside of schools.

Comment author: Thomas 12 July 2016 06:15:10PM 0 points [-]

I know that. But my focus in this thread are North America's schools as a big market.

But yes - how good this algorithm really is? Where is its optimal domain?

I guess, evolving algorithms is the best usage. Either from a previous known algorithm, either from scratch, either from data. Like evolving Kepler's law from planetary data. I wrote a post about that here, a few years ago.

http://lesswrong.com/lw/9pl/automatic_programming_an_example/

Comment author: Lumifer 12 July 2016 06:33:54PM 0 points [-]

North America's schools as a big market

The thing is, it's a very fragmented market. The US schools are local, basically run at the town level, so for you it is essentially a retail market with a large number of customers each of which buys little. I'm guessing that you'll need a large sales organization to break in.

Comment author: HungryHobo 13 July 2016 10:26:36AM 0 points [-]

Or possibly to find an existing company selling office/organization/planning software that's already got a big share of the market and selling them license to the tech.

Powered by Reddit Powered by Reddit