Sveikaskaičio programavimo bandymų aplinka
Išspręskite nedidelį sveikaskaitį tiesinį uždavinį tiksliu šakų ir ribų metodu ir peržiūrėkite visus paieškos mazgus. Geriausias taškas pateikiamas kaip įrodytai optimalus tik tada, kai išnagrinėtas visas medis.
Programa gali būti iki 4 000 simbolių ir 40 eilučių, turėti iki 8 kintamųjų ir iki 8 apribojimų su dviem ar daugiau kintamųjų; mazgų riba – nuo 1 iki 5 000, o paieška taip pat sustabdoma po 3 000 000 tiksliosios aritmetikos žingsnių. Viskas skaičiuojama jūsų įrenginyje foniniame procese, kuriam skirta 15 sekundžių. Atsisiųsti galima JSON ataskaitą ir mazgų CSV failą. Pirmoje eilutėje nurodykite, ar reikia maksimizuoti, ar minimizuoti, ir įrašykite tikslo funkciją. Toliau kiekvienoje eilutėje pateikite po vieną apribojimą. Iki 4 000 simbolių. Prieš vykdydami peržiūrėkite nustatymus.
Jūsų rezultatas
Sveikaskaičio programavimo bandymų aplinka
- Tikslo funkciją įrašykite pirmoje eilutėje, pavyzdžiui, maximize 5x + 4y.
- Kiekvienoje eilutėje įrašykite po vieną apribojimą: ribas, pavyzdžiui, x, y >= 0, ir pasirinktinai eilutes, tokias kaip integer x arba binary z.
- Nustatykite mazgų ribą ir paleiskite paiešką.
- Peržiūrėkite būseną, geriausią iki šiol rastą sprendinį, geriausią ribą ir tarpą, tada atsisiųskite JSON ataskaitą arba mazgų CSV failą.
Ką verta žinoti
Programa gali būti iki 4 000 simbolių ir 40 eilučių, turėti iki 8 kintamųjų ir iki 8 apribojimų su dviem ar daugiau kintamųjų; mazgų riba – nuo 1 iki 5 000, o paieška taip pat sustabdoma po 3 000 000 tiksliosios aritmetikos žingsnių. Viskas skaičiuojama jūsų įrenginyje foniniame procese, kuriam skirta 15 sekundžių. Atsisiųsti galima JSON ataskaitą ir mazgų CSV failą.
Šakų ir ribų metodas
Kiekviename mazge tiesinis atpalaiduotas uždavinys tiksliai sprendžiamas simplekso metodu. Sveikasis kintamasis, įgijęs trupmeninę reikšmę, padalijamas į dvi šakas: x <= floor ir x >= ceiling. Mazgai atmetami, jei atpalaiduotas uždavinys neįmanomas arba negali pagerinti geriausio rasto sveikaskaitinio sprendinio. Metodas: Wolsey, Integer Programming, 2-asis leidimas, 7 skyrius (2020).
Ką reiškia „įrodyta“
Kai kiekvienas mazgas išspręstas arba atmestas pagal tikslią ribą, įrodoma, kad geriausias rastas sprendinys yra optimalus, arba įrodoma, kad uždavinys neįmanomas. Jei paiešką anksčiau sustabdo mazgų riba arba žingsnių biudžetas, geriausias rastas sprendinys tėra iki šiol geriausias taškas; ataskaitoje pateikiama geriausia riba ir tarpas tarp jų.
Įvesties taisyklės
Pagal numatymą visi kintamieji yra sveikieji. Jei kai kuriuos deklaruojate, pavyzdžiui, eilutėje integer x, y, sveikieji lieka tik deklaruoti kintamieji, o kiti laikomi tolydžiaisiais. Vieno kintamojo apribojimai tampa ribomis. Jei atpalaiduotas uždavinys neaprėžtas, paieška sustabdoma, nes sveikaskaitis uždavinys gali būti neaprėžtas arba neįmanomas.