Kokonaislukuoptimoinnin kokeiluympäristö
Ratkaise pieni kokonaislukujen lineaarinen optimointitehtävä tarkalla haarautumis- ja rajaushakumenetelmällä ja tutki kaikki hakupuun solmut. Ratkaisua kutsutaan todistetusti optimaaliseksi vasta, kun koko puu on käyty läpi.
Kokonaislukutehtävässä saa olla enintään 4 000 merkkiä ja 40 riviä, 8 muuttujaa sekä 8 vähintään kaksi muuttujaa sisältävää rajoitetta. Solmuraja on 1–5 000, ja haku pysähtyy myös 3 000 000 tarkan laskutoimituksen jälkeen. Kaikki lasketaan laitteellasi taustatyöntekijässä enintään 15 sekunnin ajan. Lataukset ovat JSON-raportti ja solmujen CSV-tiedosto. Ensimmäisellä rivillä: maximize tai minimize ja tavoitefunktio. Kirjoita sen jälkeen kukin rajoite omalle rivilleen. Enintään 4 000 merkkiä. Tarkista asetukset ennen suorittamista.
Tuloksesi
Kokonaislukuoptimoinnin kokeiluympäristö
- Kirjoita tavoitefunktio ensimmäiselle riville, esimerkiksi maximize 5x + 4y.
- Lisää yksi rajoite riville, kuten x, y >= 0. Voit lisätä myös esimerkiksi rivit integer x tai binary z.
- Aseta solmuraja ja käynnistä haku.
- Lue tila, tähänastinen paras ratkaisu, paras raja ja niiden ero. Lataa sitten JSON-raportti tai solmujen CSV-tiedosto.
Mitä on hyvä tietää
Kokonaislukutehtävässä saa olla enintään 4 000 merkkiä ja 40 riviä, 8 muuttujaa sekä 8 vähintään kaksi muuttujaa sisältävää rajoitetta. Solmuraja on 1–5 000, ja haku pysähtyy myös 3 000 000 tarkan laskutoimituksen jälkeen. Kaikki lasketaan laitteellasi taustatyöntekijässä enintään 15 sekunnin ajan. Lataukset ovat JSON-raportti ja solmujen CSV-tiedosto.
Haarautuminen ja rajaus
Jokaisessa solmussa lineaarinen relaksaatio ratkaistaan tarkasti simplex-menetelmällä. Murtolukuarvoinen kokonaislukumuuttuja jaetaan kahteen haaraan: x <= floor ja x >= ceiling. Solmut karsitaan, jos relaksaatio on mahdoton tai ei voi voittaa parasta löydettyä kokonaislukupistettä. Menetelmä: Wolsey, Integer Programming, 2. painos, luku 7 (2020).
Mitä todistettu tarkoittaa
Kun kaikki solmut on ratkaistu tai karsittu tarkan rajan perusteella, tähänastisen parhaan ratkaisun optimaalisuus on todistettu tai tehtävä on todistetusti mahdoton. Jos solmuraja tai laskentavaiheiden raja keskeyttää haun aiemmin, tähänastinen paras ratkaisu on vain paras löydetty piste. Raportissa ilmoitetaan paras raja ja niiden välinen ero.
Syötteen säännöt
Muuttujat ovat kokonaislukumuuttujia, ellei joitakin niistä ilmoiteta kokonaislukumuuttujiksi esimerkiksi rivillä integer x, y; tällöin muut muuttujat ovat jatkuvia. Yhden muuttujan rajoitteista tulee muuttujien rajoja. Jos relaksaatio on rajoittamaton, haku pysähtyy, sillä kokonaislukutehtävä voi silloin olla rajoittamaton tai vailla ratkaisua.