Planlamada sütun bazlı optimizasyon nasıl yapılır ?

[mrmarman]

Merhaba.

Uzun sayılabilecek bir zaman önce buna benzer bir optimizasyon için çalışma yapmış ama başaramayınca bırakmıştım. Bugün bir başka başlıkta yine optimizasyon ile ilgili soru (şekil düzenleme) görünce aklıma bu eski çalışmam geldi ve sormadan durmadım. Mevcut bir projemde kullanıcının mouse ile taşıma yapmasını sağlayarak buna manuel olarak imkan vermiştim, ancak içimde kalmış ve gereklilik olarak gördüğüm bir fonksiyondur.

Aşağıdaki resimde aynı planlamaya ait iki tablo görülmektedir. Excel formatındaki halini

Optimizasyon.rar

Örnek tablonun "Excel" hali. RAR paketin içindedir.

(4.19 KiB) 91 kere indirildi

dosyasında yaz/boz yaparak inceleyebilirsiniz.

Üst kısımda veritabanından geldiği gibi soldan sağa ve yukarıdan aşağıya doğru uygun olan ilk boşluklara yerleştirme yapılmıştır.

Alttaki tabloda aynı planlamadaki arada kalan ve (x) ile ifade edilmiş boşlukların en sağa aktarılacağı şekilde optimizasyon yapılmış olduğu hali görüyorsunuz.

Arada boşluk kalmayacak şekilde olması gerekiyor çünkü her bir boşluk kayıp gün demektir. Bu boşlukları sona taşıyarak, sütunlarla ifade edilen ekip sayısından tasarruf edilmek amaçlıdır. En az ekiple en fazla iş yapmak üzerine bir optimizasyon çalışmasıdır.

Sütun bazında arada yukarıdan aşağıya boşluklar olacaksa da bu boşlukların da maksimum sayıda olması gözetilir ki, planlamada esneklik sağlaması açısından faydaya dönüştürülebilir nitelik sağlar.

Burada satır numaraları tarihi simgelemektedir ve sabittir. Renk farklı bloklar birbirinde bağımsız olarak yer değişebilir ancak bulundukları satırlara sadık kalınması gerekmektedir. Sütun bazında yer değişiklikleri yapıldığını örnekte görebilirsiniz.



Buna ilişkin tecrübelerini paylaşanlar için şimdiden teşekkürler.

[orhancc]

belki faydası olur. Bu tür işler için adamlar bazı algoritmalar geliştirmiş.

http://www.bilgisayarkavramlari.com/200 ... lgorithms/

[mrmarman]

Teşekkürler

Diğer başlıkta da vermiş olduğun bu linki ve diğerlerini uzun uzadıya incelemiştim. Hatta "En iyi yerleştirme ( best fitting )" kavramını görünce gözlerim parlamış, bunun üzerinde google taramaları yapıp etüd ettikten sonra sonuç alamayınca bu başlığı açmıştım.

Tanımları içeren verdiğin linkten bağlı diğer linkleri de inceleyince tek boyutlu çözümler (aynı tipte nesneler, birimler) üzerine fikirler verilmiş olmasından dolayı bu soruma cevap olacak bir yaklaşım bulamadım.

Armut piş hesabı motomot bana çözüm üretmesini de zaten beklemiyordum. Ama verilen tanıma ilişkin bir gönderme yapmasını beklerdim. Ben halen araştırmaya devam ediyorum.

Verdiğiniz linkteki mesaj alanına bu sorumu ilettim.

Tekrar teşekkürler.

[orhancc]

Bu tarz işlerle ilgili bazı yazılar okumuştum ama nerede hangi kitapta olduğunu hatırlayamadım bulursam gönderirim onları da.

[mrmarman]

Şadi Bey gönderdiğim mesaj için cevap yazma inceliği gösterdiler. Cevap mesajını burada da paylaşayım.

Ah bu meşhur bir np-complete problemdir J time tabling olarak geçer literatürde. Ne yazık ki deterministic bir yolu yok. Genetik algoritmalarla konu üzerinde çalışan bir iki arkadaş vardı. Ben konuyla ilgili bir makale yazıp sitede yayınlamaya çalışayım.

Başarılar

Şadi Evren ŞEKER

Bir diğer detay soru için de başka bir cevabi mesaj iler aşağıdaki şekilde dile getirdiler.

Evet literatürde bu şekilde geçiyor hatta ttml (timetabling markup language) isminde bir dil bile var problemlerin modellenmesi için. Bir vakitler siteye birşeyler eklemiştim bu konuda ama sizin problemin genel tanımı ve alternatif çözümleri içeren bir yazı vakit bulur bulmaz koyacağım.

Başarılar
Şadi Evren ŞEKER

[mkysoft]

@mrnarman üzerine uğraştığınız problem aslında o kadar zor değil. tam sayılı programlama (linear integer programming) modeli ile küçük boyutlu olanları kolayca çözebilirsiniz. genetik algoritma gibi sezgisel algoritmalar kullanmanıza gerek yok. Tabi veri sayınızın az olduğunu varsayıyorum. Tam sayılı programla için sourceforge.net'de hazır projelerde var. DLL olarak yada source olarak projenize dahil edebilirsiniz. Eğer tam sayılı ptogramlama modelinizide kendiniz yazmak isterseniz döküman paylaşabilriim. Kolay gelsin.

[mrmarman]

Genetik algoritmalar sizin de uğraştığınızı değerlendirdiğim üzere (buradan cevabınızı okuyanlar için açıklayıcı olsun diye yazıyorum) farklı seviyelerdedir.

En basit haliyle 1 bitlik bir sinir ucunu ele alırsak, iç içe durum sorgulaması yapılarak başta true olan bir durum, şartların ardışık sorgulanmasıyla zamanla false durumuna kayabilir ve daha sonra da tekrar true'ya dönebilir. Sonucu True diyemeyiz çünkü bir önceki şartta false idi. False diyemeyiz çünkü sonra true olabilir.

Yapay sinir ağı deyince olabilecek en zor ve karmaşık yapıyı akla getirmek büyük hata olur. Aslında (göreceli olarak olduğunun altını çizeyim) göründüğünden basit bir yapıdır (resim işleme projelerinde sıkça kullanırız ve bir çok kişi de farkında olmadan aynı metodları bir çok alanda kullanmıştır).

İşte bu sebeple gerek yoktur deyip refüze etmek bence hatalı yaklaşımdır.

Burada sorguladığım durum, zorluk derecesi 1 ile 10 arasındaki olduğunu varsayarsak belki de 1 numaralı en basit halidir. Buradaki sanat, durum değerlendirmesinin en kısa yoldan doğru sonucu verecek hali tespit ederek uygulamaktır. Aradığım da budur.

Sorduğum soru için daha önce bir çalışma yaptığımın altını çizmiştim. İlk akla gelen metod simülasyon metodudur. Bunun için;

Öncelikle kağıt üzerinde kendim yaptığım optimizasyonu, gerçekleştirdiğim sorgulama adımları şeklinde bir kağıda döküp, bunu simüle ederek yaklaşım üretmeye çalıştım kendi yaptığım gibi olmadı. Adımlarımdan ana unsurlar aşağıdadır;

1. Dönemin ilk planı yani örneğimizde ayın 1'inde olanlar olmazsa olmazlar kabul ederek yan yana sütunlar halinde dökerek minimum sütun sayısını elde ediyorum.
2. Sonra da her bir sütundaki son tarihi takip eden tarihli işlerin bir listesini elde ediyorum. Bunları büyük tarih bloklardan başlayarak küçüğe doğru yerleştiriyorum.
3. Tarih sürekliliği yoksa soldan sağa ilk uygun sütuna yerleştiriyor, ardından döngüyü başa alıyorum.

deyip onlarca adımlı bir sorgu elde etmiştim. Buradan üreteceğim fonksiyonun farklı hallerde nasıl davranacağını elde etmeyi hedeflemiştim. Daha önce farklı konularda simülasyon metoduyla sorunsuz çözüm üretebildiğim halde bu konuda başarısız olunca soruyu burada açmış bulundum.

1 ayda ortalama 60 ekip için planlama yapılıyor. 30 x 60 günlük bir dinamik (bu dinamik içinde aynı gün farklı mesailerde çalışma da var. Ayın farklı tarihlerdeki 15 günü böyledir) içine, 1 gün'den 20 güne kadar farklı sayıda 100'ün üzerinde planı dağıtma işini elle yapıyorum. Bunun için soracağım soruların tümünü elde ettiğimde, cevabı zaten çözmüş olucam. Yaklaşım için metodoloji ve tecrübeye ihtiyacım var. Böylece aklıma gelmeyen onlarca soruyu sormaktan bir adım daha öteye gideceğimden, sonuca daha hızlı ulaşacağımı değerlendiriyorum.

Eğer tam sayılı ptogramlama modelinizide kendiniz yazmak isterseniz döküman paylaşabilriim.

Teşekkürler. Her türlü kaynak değerlendirmeye değerdir. Ayrıca sourceforge.net ile codeproject benim hep ilk iki adresim olmuştur. Oralarda bulamayınca problemin çözümünü yapan üçüncü parti yazılımları aradım. Yabancı dilim oldukça yeterlidir. Google taramasında kullandığım Schedule / Task Optimization, Crew Optimization, Staff Opimization, Timeline / Crew Optimization ve onlarca dahasından sonuç alsaydım çözümlerini inceleyecektim ama bulamadım.

Özetle durum böyle. Uzun oldu kusura bakma, yeterli araştırma yapmadan buraya konu açmazdım bunu belirmek için böyle detay verdim.

Aşağıda bayram ayı olduğundan ayın ortası boş olan yani yoğunluğu tüm seneye göre en az olan bu ayki planı görüyorsunuz. Saatlik yapımlar elenmiş, önceki aydan sarkan veya gelecek aya sarkanlar elenmiş, südyo görevleri elenmiş olanlardan sadece dış çekim görevleri olanları listeliyorum. Bunlardan en az sayıda ekip (sütun) çıkartmak / elde etmek ana hedeftir.

Kod: Tümünü seç

No  ProgAdi                         BasTar     BitTar
--  ------------------------------- ---------  ---------
1   Akıl Oyunları                   29-Kas-10  30-Kas-10
2   Alternatif  Rotalar             08-Kas-10  12-Kas-10
3   Alternatif  Rotalar             28-Kas-10  30-Kas-10
4   Anne Elimi Tutsana              08-Kas-10  11-Kas-10
5   Aşkın Pusulası                  06-Kas-10  12-Kas-10
6   Ben Yaparım                     03-Kas-10  06-Kas-10
7   Ben Yaparım                     27-Kas-10  30-Kas-10
8   Bizim Ev                        23-Kas-10  30-Kas-10
9   Bizim Kampüs                    01-Kas-10  04-Kas-10
10  Bizim Kampüs                    22-Kas-10  26-Kas-10
11  Bizim Yunus                     24-Kas-10  26-Kas-10
12  Çingeneler                      01-Kas-10  07-Kas-10
13  Doğunun Yıldızları              01-Kas-10  07-Kas-10
14  Gap Spot                        24-Kas-10  30-Kas-10
15  Gezelim  Görelim                14-Kas-10  21-Kas-10
16  Hava Kuvvetleri Protokol        01-Kas-10  11-Kas-10
17  Hava Su ve Toprak               22-Kas-10  28-Kas-10
18  Hayal Su Gerçek                 05-Kas-10  10-Kas-10
19  Hayatın  Renkleri               03-Kas-10  07-Kas-10
20  Hayatın  Renkleri               24-Kas-10  30-Kas-10
21  İçimizden  Biri                 24-Kas-10  30-Kas-10
22  İnsan Hakları                   08-Kas-10  13-Kas-10
23  İnsan Hakları                   10-Kas-10  14-Kas-10
24  Kampüs Aktüel                   04-Kas-10  07-Kas-10
25  Kampüs Aktüel                   11-Kas-10  14-Kas-10
26  Kampüs Aktüel                   18-Kas-10  21-Kas-10
27  Kampüs Aktüel                   25-Kas-10  28-Kas-10
28  Kentler ve Nehirler             04-Kas-10  12-Kas-10
29  Kentler ve Nehirler             26-Kas-10  30-Kas-10
30  Kolay Gelsin                    01-Kas-10  05-Kas-10
31  Kolay Gelsin                    27-Kas-10  30-Kas-10
32  Komşumuz Ermenistan             06-Kas-10  12-Kas-10
33  Komşumuz Ermenistan             29-Kas-10  30-Kas-10
34  Konuşan Tarih                   09-Kas-10  13-Kas-10
35  Konuşan Tarih                   22-Kas-10  25-Kas-10
36  Köklerimiz                      01-Kas-10  03-Kas-10
37  Köklerimiz                      27-Kas-10  30-Kas-10
38  Kültür Şenliği                  02-Kas-10  06-Kas-10
39  Kültür Şenliği                  05-Kas-10  11-Kas-10
40  Kültür Şenliği                  23-Kas-10  26-Kas-10
41  Mutfak                          01-Kas-10  05-Kas-10
42  Mutfak                          23-Kas-10  29-Kas-10
43  Müziğin  Kahramanları           27-Kas-10  30-Kas-10
44  Müzik Okulu                     02-Kas-10  05-Kas-10
45  Müzik Yolu                      22-Kas-10  25-Kas-10
46  Nasıl Çalısır                   23-Kas-10  24-Kas-10
47  Oto Vizyon                      01-Kas-10  06-Kas-10
48  Oto Vizyon                      22-Kas-10  25-Kas-10
49  Ömür  Dediğin                   06-Kas-10  09-Kas-10
50  Ömür  Dediğin                   22-Kas-10  29-Kas-10
51  Reçete                          01-Kas-10  01-Kas-10
52  Reçete                          04-Kas-10  04-Kas-10
53  Reçete                          10-Kas-10  10-Kas-10
54  Reçete                          22-Kas-10  22-Kas-10
55  Reçete                          29-Kas-10  29-Kas-10
56  Sağlığım İçin                   08-Kas-10  28-Kas-10
57  Sağlık İçin                     08-Kas-10  14-Kas-10
58  Sağlık İçin                     22-Kas-10  28-Kas-10
59  Savaşta  Barışta  Türk Ordusu   01-Kas-10  05-Kas-10
60  Savaşta  Barışta  Türk Ordusu   08-Kas-10  12-Kas-10
61  Savaşta  Barışta  Türk Ordusu   30-Kas-10  30-Kas-10
62  Son Nokta                       01-Kas-10  09-Kas-10
63  Söyleyeceklerim Var             23-Kas-10  30-Kas-10
64  Söz Sende(Serbest Kürsü)        01-Kas-10  06-Kas-10
65  Söz Sende(Serbest Kürsü)        22-Kas-10  27-Kas-10
66  Stüdyo Avaz                     01-Kas-10  02-Kas-10
67  Stüdyo Avaz                     11-Kas-10  12-Kas-10
68  Stüdyo Avaz                     22-Kas-10  23-Kas-10
69  Stüdyo Avaz                     29-Kas-10  30-Kas-10
70  Suretler                        08-Kas-10  13-Kas-10
71  Suya  Cemre Düştü               22-Kas-10  27-Kas-10
72  Şimdi Derby Zamanı              24-Kas-10  30-Kas-10
73  Tarım Yaşam Gıda                22-Kas-10  28-Kas-10
74  Tıp Teknolojileri               07-Kas-10  13-Kas-10
75  Tıp Teknolojileri               24-Kas-10  28-Kas-10
76  Tur Rehberi                     08-Kas-10  13-Kas-10
77  Tur Rehberi                     26-Kas-10  30-Kas-10
78  Türk Osmanlı Şerbeti            07-Kas-10  13-Kas-10
79  Türk Osmanlı Şerbeti            26-Kas-10  30-Kas-10
80  Türkçe Türkçe Türkçe            10-Kas-10  13-Kas-10
81  Türkiye'nin Renkleri Sesleri    05-Kas-10  14-Kas-10
82  Türkiyenin Tanıkları            03-Kas-10  13-Kas-10
83  Yakın Takip                     22-Kas-10  26-Kas-10
84  Yenigün                         02-Kas-10  02-Kas-10
85  Yenigün                         05-Kas-10  05-Kas-10
86  Yenigün                         09-Kas-10  09-Kas-10
87  Yenigün                         12-Kas-10  12-Kas-10
88  Yenigün                         23-Kas-10  23-Kas-10
89  Yenigün                         26-Kas-10  26-Kas-10
90  Yenigün                         30-Kas-10  30-Kas-10
91  Yıldızlar                       22-Kas-10  25-Kas-10
92  Zağarların Peşinde              01-Kas-10  08-Kas-10
93  Zamanın Gölgesinde (O Gün)      26-Kas-10  30-Kas-10

Kod: Tümünü seç

No  ProgAdi                            BasTar	    BitTar
1	 Reçete                             01-Kas-10	01-Kas-10
2	 Stüdyo Avaz                        01-Kas-10	02-Kas-10
3	 Köklerimiz                         01-Kas-10	03-Kas-10
4	 Bizim Kampüs                       01-Kas-10	04-Kas-10
5	 Kolay Gelsin                       01-Kas-10	05-Kas-10
6	 Mutfak                             01-Kas-10	05-Kas-10
7	 Savaşta  Barışta  Türk Ordusu      01-Kas-10	05-Kas-10
8	 Oto Vizyon                         01-Kas-10	06-Kas-10
9	 Söz Sende(Serbest Kürsü)           01-Kas-10	06-Kas-10
10	Çingeneler                         01-Kas-10	07-Kas-10
11	Doğunun Yıldızları                 01-Kas-10	07-Kas-10
12	Zağarların Peşinde                 01-Kas-10	08-Kas-10
13	Son Nokta                          01-Kas-10	09-Kas-10
14	Hava Kuvvetleri Protokol           01-Kas-10	11-Kas-10
15	Yenigün                            02-Kas-10	02-Kas-10
16	Müzik Okulu                        02-Kas-10	05-Kas-10
17	Kültür Şenliği                     02-Kas-10	06-Kas-10
18	Ben Yaparım                        03-Kas-10	06-Kas-10
19	Hayatın  Renkleri                  03-Kas-10	07-Kas-10
20	Türkiyenin Tanıkları               03-Kas-10	13-Kas-10
21	Reçete                             04-Kas-10	04-Kas-10
22	Kampüs Aktüel                      04-Kas-10	07-Kas-10
23	Kentler ve Nehirler                04-Kas-10	12-Kas-10
24	Yenigün                            05-Kas-10	05-Kas-10
25	Hayal Su Gerçek                    05-Kas-10	10-Kas-10
26	Kültür Şenliği                     05-Kas-10	11-Kas-10
27	Türkiye'nin Renkleri Sesleri       05-Kas-10	14-Kas-10
28	Ömür  Dediğin                      06-Kas-10	09-Kas-10
29	Aşkın Pusulası                     06-Kas-10	12-Kas-10
30	Komşumuz Ermenistan                06-Kas-10	12-Kas-10
31	Tıp Teknolojileri                  07-Kas-10	13-Kas-10
32	Türk Osmanlı Şerbeti               07-Kas-10	13-Kas-10
33	Anne Elimi Tutsana                 08-Kas-10	11-Kas-10
34	Alternatif  Rotalar                08-Kas-10	12-Kas-10
35	Sağlığım İçin                      08-Kas-10	12-Kas-10
36	Savaşta  Barışta  Türk Ordusu      08-Kas-10	12-Kas-10
37	İnsan Hakları                      08-Kas-10	13-Kas-10
38	Suretler                           08-Kas-10	13-Kas-10
39	Tur Rehberi                        08-Kas-10	13-Kas-10
40	Sağlık İçin                        08-Kas-10	14-Kas-10
41	Yenigün                            09-Kas-10	09-Kas-10
42	Konuşan Tarih                      09-Kas-10	13-Kas-10
43	Reçete                             10-Kas-10	10-Kas-10
44	Türkçe Türkçe Türkçe               10-Kas-10	13-Kas-10
45	İnsan Hakları                      10-Kas-10	14-Kas-10
46	Stüdyo Avaz                        11-Kas-10	12-Kas-10
47	Kampüs Aktüel                      11-Kas-10	14-Kas-10
48	Yenigün                            12-Kas-10	12-Kas-10
49	Gezelim  Görelim                   14-Kas-10	21-Kas-10
50	Kampüs Aktüel                      18-Kas-10	21-Kas-10
51	Reçete                             22-Kas-10	22-Kas-10
52	Stüdyo Avaz                        22-Kas-10	23-Kas-10
53	Konuşan Tarih                      22-Kas-10	25-Kas-10
54	Müzik Yolu                         22-Kas-10	25-Kas-10
55	Oto Vizyon                         22-Kas-10	25-Kas-10
56	Yıldızlar                          22-Kas-10	25-Kas-10
57	Bizim Kampüs                       22-Kas-10	26-Kas-10
58	Yakın Takip                        22-Kas-10	26-Kas-10
59	Söz Sende(Serbest Kürsü)           22-Kas-10	27-Kas-10
60	Suya  Cemre Düştü                  22-Kas-10	27-Kas-10
61	Hava Su ve Toprak                  22-Kas-10	28-Kas-10
62	Sağlık İçin                        22-Kas-10	28-Kas-10
63	Tarım Yaşam Gıda                   22-Kas-10	28-Kas-10
64	Ömür  Dediğin                      22-Kas-10	29-Kas-10
65	Yenigün                            23-Kas-10	23-Kas-10
66	Nasıl Çalısır                      23-Kas-10	24-Kas-10
67	Kültür Şenliği                     23-Kas-10	26-Kas-10
68	Mutfak                             23-Kas-10	29-Kas-10
69	Bizim Ev                           23-Kas-10	30-Kas-10
70	Söyleyeceklerim Var                23-Kas-10	30-Kas-10
71	Bizim Yunus                        24-Kas-10	26-Kas-10
72	Tıp Teknolojileri                  24-Kas-10	28-Kas-10
73	Gap Spot                           24-Kas-10	30-Kas-10
74	Hayatın  Renkleri                  24-Kas-10	30-Kas-10
75	İçimizden  Biri                    24-Kas-10	30-Kas-10
76	Şimdi Derby Zamanı                 24-Kas-10	30-Kas-10
77	Kampüs Aktüel                      25-Kas-10	28-Kas-10
78	Yenigün                            26-Kas-10	26-Kas-10
79	Kentler ve Nehirler                26-Kas-10	30-Kas-10
80	Tur Rehberi                        26-Kas-10	30-Kas-10
81	Türk Osmanlı Şerbeti               26-Kas-10	30-Kas-10
82	Zamanın Gölgesinde (O Gün)         26-Kas-10	30-Kas-10
83	Ben Yaparım                        27-Kas-10	30-Kas-10
84	Kolay Gelsin                       27-Kas-10	30-Kas-10
85	Köklerimiz                         27-Kas-10	30-Kas-10
86	Müziğin  Kahramanları              27-Kas-10	30-Kas-10
87	Alternatif  Rotalar                28-Kas-10	30-Kas-10
88	Reçete                             29-Kas-10	29-Kas-10
89	Akıl Oyunları                      29-Kas-10	30-Kas-10
90	Komşumuz Ermenistan                29-Kas-10	30-Kas-10
91	Stüdyo Avaz                        29-Kas-10	30-Kas-10
92	Savaşta  Barışta  Türk Ordusu      30-Kas-10	30-Kas-10
93	Yenigün                            30-Kas-10	30-Kas-10

[mkysoft]

Bende kısaca sana tam sayılı programlamayı anlatayım, senin konun üzerinden. Şimdi elinde yapılacak işler var, bunların sadece sütunlarını değiştirebiliryorsun, satırları sabit. Bu durumda her işe bir integer değişken atamış olalalım (X1,X2,X3,...). Bu değişkenler 0 ile maxsutun arasında değerler alabilir. Ayrıca birde amacımız var. Anlattığına göre amacımız boşlukları azaltmak. Amacımızdan önce kısıtlarımızıda belirtmemiz lazım. Bu kısıtlar işlerin üst üste gelmesini engelleyecek ve toplam zamanı aşmayacak şekilde tanımlanmış olmalıdır. Mesala 1. sutuna atanan değerler kontrol edilerek (mesala x1 ve x2 atanmış olsun) işlerin biri biri üstüne binmediğine (x1 in bitişi x2 nin başlangıcımdan büyük olmamalı) ve toplam zamanı doldurmamalı (x1+x2 <=çalışma zamanı). Bu kısıtlarıda belirledikten sonra şimdide amacımızı yazarsak, her bir sutun için toplam çalışma zamanından o sutunlara atanan zamanları çıkarmamız gerekir. Tam sayılı programlamada kullanılan temel yöntemlerden biri dal-sınır algoritmalarıdır. Senin probleminde şu şekilde çalışır. x1 alabileceği değerleri tek tek atayarak, daha sonra x2 atanır. Burada hangi işten başladığın senin problemin için önemli olmadığından işi kolaylaşacaktır. x1 için mesala 1 atadın, sonra x2 ye geçtin onada 1 atadın, çakıştılar diyelim bu durumda x1=1 ve x=2 dalını artık kapatabilirsin, çünkü kısıtlarını ihlal etmektedir. Tüm dalları tamamladığında artık amaç fonksiyonun değerini hesaplayabilirsin. Anlattığım bu yapıda tüm kombinasyonları denemiş olacak, ve çözümünün en iyi olduğunu garanti altına almış olacaksın. Çok iyi kod yazabildiğini bildiğimden kolayca yazabileceğine eminim. Bu kadar kombinasyonu denemek performans açısından zaman kaybı gibi gelebilir ancak 60 değişken çokda fazla değil. Kısıtlarından dolayı çok çabuk dalların iptal olacaktır. Bu konuda hazır bir program istersen ILOG Cplex var, sınıfının en hızlı programı. Tabiki fiyatı fazla gelebilir. Ayrıca multi thread yazarak her bir dalı bölme şansında var (Cplex yapıyor).
Sourceforgeden bu iş için kullanabileceğin hazır iki proje önereceğim:
http://sourceforge.net/projects/lpsolve/
http://sourceforge.net/projects/winglpk/

Bir projede lpsolve kullanan arkadaşım var, Cplex'e göre performansı düşük ama ücretsiz yorumunu yapıyor. Diğerinde de aynı problem olabilir, deneyimimiz lpsolve üzerine olduğundan onu tavsiye edeceğim.
Problemini yüklediğinde out of memory hatası yada saatler süren çalışma zamanıyla karşılaşırsan o zaman sezgisel olarak genetik, yapar sinir ağı, bağışıklık algoritmalarına başvurabilirsin. Eğer sezgisel kullanayım diyorsan o konuda da yardımcı olabilirim. Genetik yerine tavlama benzetimi (simulated annualing) kullanmanı tavsiye ederim başlangıç için. Genetik karmaşık gelebilir başlangıç için.
Kolay gelsin.

[mkysoft]

Kitap yazmayı unutmuşum:
Introduction to Algorithms, 2nd Edition, MIT Press, sayfa 770. pdf olarak bulunabilir.

[mrmarman]

Detaylı bir anlatım, zaman ve sabrın için teşekkürler.

Genetik algoritmalara bugüne değin nesnel olarak yaklaştığımdan ( özellikle OCR için kullanıyorum ) ürünü daima görüp, ona göre farklı ürünleri farklı seviyelerde oluşturup bunların karşılaştırmasını yaparak yeni ürünler elde ediyordum. Yeni üründen elde ettiğim sonucun önceki ürün(ler)e göre tutarlı sonuçlar verip vermediğini sorgulayarak tamam mı devam mı sorusuna karar verip bir sonraki seviyeye yeni ürüne geçiş sürecini kontrol edecek şekilde mekanizma kuruyordum. Bu mekanizma ürün(leri) komşuluk bazında image nesnesinin 1 bitlik desenini elde etmeme imkan tanıyor, yatay ve sütun yığıntı tepe değerlerine bakarak anlamlandırabileceğim sonuçlar veriyordu.

Konumuzda da benzer şekilde şimdiye kadar mevcut sütunları kısıtlara göre basit sıralı şekil de önce doldurup ondan sonra sütunların içerdiği blokları (yatay TETRİS oyunu gibi) birbiri karşılaştırma üzerine yoğunlaşan bir yapı izledim.

Burada sütun doldurma türevi işlem yapmaksızın öncelikle uygun çiftler, üçlüler, dörtlüler, (n)liler oluşturup bunları grup olarak sıraya alarak sonuca gidecek bir yapı oluşturmayı denemek gerektiğini anlıyorum. Yanlışsam düzeltin.

Kaynağı inceliycem. Tekrar teşekkürler.

[mkysoft]

tüm kombinasyonları denemiş olacağınız için ikili, üçlü, n'li yapıların hepsini denemiş olursunuz otomatikman. Bu yöntem kesin çözüm ürettiği için, en iyiyi bulmuş olacaksınız. Sizin denemiş olduğunuz mantıklarında her biri sezgiseldir. Kısa sürede çok başarılı sonuçlar elde edebilir. Ama bu sonuçlardan hiç bir zaman emin olamayacaksınız. eğer tam sayılı programlama ile çözerseniz (en azından denemek için) üretmiş olduğunuz sezgisel'in ne kadar iyi olduğunu görebileceksiniz. Daha önceden genetik deneyiminiz varsa direk genetiklede yazabilirsiniz. Bildiğimiz gibi en kısa yol bazen en iyi bildiğimiz yoldur. lpsolver kullanmak için program yazmanız gerekmediğinden (kendi problem giriş dili vardır) basitçe bir denemek yaparak değip değmeyeceğini görebilirsiniz en azından.