Operaatiotutkimus ja kupera optimointi on soveltavan matematiikan ala, joka on löytänyt monenlaisia ​​kaupallisia sovelluksia vuosien varrella. Kun laskentatehosta tuli edullisempaa ja laajasti saatavilla, tutkijat alkoivat rakentaa yhä kehittyneempiä optimointialgoritmeja auttamaan heitä tekemään parempia päätöksiä. Nykyään toimintatutkimuksen käyttämät sovellukset tehostavat kaikkea reitityksestä globaalissa logistiikassa sähköntuotannon tasoittamiseen energiateollisuudessa.

Kun taustalla olevan tekniikan monimutkaisuus kasvoi, on luotu uusi työkalusarja, joka auttaa tutkijoita ja kehittäjiä työskentelemään tuottavammin. Näiden työkalujen, kuten AMPL, CVXPY ja PuLP, avulla kehittäjät voivat nopeasti määritellä, rakentaa ja suorittaa optimointialgoritmeja ja rajapintoja monenlaisten ratkaisijoiden kanssa.

Vaikka optimointitekniikat ja liiketoimintatarpeet kasvavat edelleen hienostuneisuudessa, suurin osa näistä työkaluista on pysynyt suunnilleen ennallaan eivätkä kehittyneet tarpeeksi nopeasti vastaamaan teollisuuden tarpeita. Tämän seurauksena näiden algoritmien kehittäminen, hallinta, virheenkorjaus ja viritys vaatii usein paljon kognitiivisia yleiskustannuksia etenkin nopeasti muuttuvassa liiketoimintaympäristössä.

Tänään haluaisin esitellä HorusLP , Python-optimointikirjasto joka auttaa algoritmien kehittämisen työnkulkujen arkkitehtuurissa. Puhumme ongelmista, jotka työkalu on suunniteltu ratkaisemaan, annamme sitten nopean yleiskuvan Python-kirjastosta ja rakennamme joitain esimerkkejä optimointialgoritmeista.

Optimointialgoritmikehittäjien ongelmat

Yksi useimpien kehittäjien kohtaamista monivuotisista ongelmista on tasapaino ylläpidettävän, tehokkaan, idiomaattisen ohjelmiston rakentamisen ja tuotteen toimittamisen välillä projektin aikarajoissa. Olitpa tekemässä selainpohjaista sovellusta, verkkosovellusliittymää tai käyttäjän todennuksen mikropalvelua, tavoitteiden saavuttamisen välillä on usein kompromissi 'oikean' ja 'nopean' tavan välillä. Tämä luontainen kompromissi tulee näkyvämmäksi tuotteen monimutkaisuuden kasvaessa.

Useimmilla tieteenaloilla kehittäjä voi lievittää tätä ongelmaa valitsemalla arkkitehtuuria auttavan kehyksen tai kirjaston. Verkkoalustassa monet kehittäjät valitsevat React tai Angular; API-kehityksen maailmassa ohjelmistosuunnittelijat voivat valita muun muassa Djangon, ASP.NET MVC: n tai Playn. Nöyrän optimointialgoritmikehittäjän kohdalla on kuitenkin hyvin vähän arkkitehtuurityökaluja, jotka auttavat hallitsemaan arkkitehtonista monimutkaisuutta. Kehittäjällä on yksin mahdollisuus hallita muuttujia, rajoituksia ja erilaisia ​​tavoitteita. Lisäksi toimintatutkimuksen algoritmeja on yleensä vaikea tutkia, mikä pahentaa ongelmaa.

HorusLP: n päätarkoitus on tarjota arkkitehtoninen kehys optimointialgoritmien kehittämiselle. Tarjoamalla rakenteellisen johdonmukaisuuden kehys tekee organisaatiosta helpompaa ja antaa kehittäjien keskittyä parhaaseensa: algoritmien rakentamiseen.

Tyypilliset optimoinnin työnkulun haasteet

TAI-algoritmeja kehitettäessä on useita tärkeitä monimutkaisuuden lähteitä:

Muuttujien monimutkaisuus

• Muuttujia on usein lisättävä vastaamaan liiketoiminnan lisävaatimuksia, eikä niitä ole helppo seurata käytettäväksi mallimääritelmissä ja myöhemmin raportoinnissa.
• Aiheeseen liittyvät muuttujat on ryhmiteltävä ja seurattava, eikä niiden hallitsemiselle ole selvää tapaa.

Monimutkaisuus rajoituksista

• Rajoitukset on lisättävä ja poistettava eri skenaarioiden tukemiseksi ja virheenkorjauksen suorittamiseksi, mutta rajoitusten lisäämiseen tai poistamiseen ei ole selvää paikkaa.
• Rajoitukset ovat usein yhteydessä toisiinsa / riippuvaisia ​​toisistaan, eikä ole luonnollista tapaa ilmaista heidän suhteitaan.

Monimutkaisuus tavoitteista

• Objektiiviset ilmaisut voivat tulla hankaliksi, jos niillä on useita komponentteja. Tämä voi pahentua, jos eri komponentit painotetaan ja painot on mukautettava liiketoiminnan tarpeiden mukaan.

Virheenkorjauksen monimutkaisuus

• Ei ole helppoa tapaa nähdä mallin tuloksia kehityksen aikana. Kehittäjän on tulostettava selkeästi uudet muuttujat ja rajoitusarvot nähdäksesi tulokset. Tämä johtaa päällekkäiseen koodiin ja hitaampaan kehitykseen.
• Kun rajoitteen lisääminen saa mallin tulemaan mahdottomaksi, ei välttämättä ole selvää, miksi rajoitus aiheutti mallin mahdottomuuden. Yleensä kehittäjien on otettava erilaisia ​​rajoituksia ja etsittävä yhteensopimattomuutta kokeilemalla ja erehdyksellä

HorusLP toivoo tekevänsä näistä haasteista helpommin hallittavissa tarjoamalla rakennetta, työkaluja, parhaita käytäntöjä kehittäjien tuottavuuden ja tuotteiden ylläpidettävyyden parantamiseksi.

HorusLP-opetusohjelma: Optimointialgoritmi ja yleiskatsaus sovellusliittymään

Sukellamme sisään ilman lisäkysymyksiä ja katsotaan, mitä HorusLP-kirjasto voi tehdä sinulle!

Koska HorusLP perustuu Pythoniin ja PuLP: hen, haluamme asentaa ne käyttämällä pip. Suorita seuraava komentorivillä:

Pip install horuslp pulp

Kun asennus on valmis, siirry eteenpäin ja avaa Python-tiedosto. Toteutamme reppu ongelma minun aikaisempi artikkeli operaatiotutkimuksesta .

HorusLP-kirjastossa on hyvin yksinkertainen selittävä sovellusliittymä ja hyvin pieni kattilalevy. Aloitetaan tuomalla tarvittavat luokat ja muuttujat:

from horuslp.core.Variables import BinaryVariable # we will be using binary variables, so we will import the BinaryVariable class from horuslp.core import Constraint, VariableManager, Problem, ObjectiveComponent # We will also need to import the constraint class, variable manager class, the main problem class, and the objective class to define the objective. from horuslp.core.constants import MAXIMIZE # since we're maximizing the resulting value, we want to import this constant

Kun kaikki muuttujat on tuotu, määritellään muuttujat, joita tarvitsemme tähän ongelmaan. Teemme tämän luomalla muuttujien hallinta-aliluokan ja täyttämällä sen binäärimuuttujilla:

class KnapsackVariables(VariableManager): vars = [ BinaryVariable('camera'), # the first argument is the name of the variable BinaryVariable('figurine'), BinaryVariable('cider'), BinaryVariable('horn') ]

Nyt kun muuttujat on määritelty, määritellään rajoitteet. Luomme rajoituksia luokittelemalla päärajoitusluokan ja toteuttamalla sen 'määritä' -funktion.

class SizeConstraint(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

Definition-funktiossa voit pyytää vaadittuja muuttujia nimen mukaan. Kehys etsii muuttujan muuttujanhallinnasta ja siirtää sen määrittävään toimintoon.

Kun rajoitus on pantu täytäntöön, voimme toteuttaa tavoitteen. Koska se on yksinkertainen tavoite, käytämme ObjectiveComponent:

class ValueObjective(ObjectiveComponent): def define(self, camera, figurine, cider, horn): return 5 * camera + 7 * figurine + 2 * cider + 10 * horn

Definition-funktiolla on hyvin samanlainen asetus kuin rajoitusluokan define-funktiolla. Rajoituksen lausekkeen palauttamisen sijaan palautamme kuitenkin affiinisen lausekkeen.

Nyt kun muuttujat, rajoitukset ja tavoitteet on määritelty, määritellään malli:

class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [SizeConstraint] sense = MAXIMIZE

Mallin rakentamiseksi luomme luokan, joka on ongelma-luokan alaluokka, ja määritämme muuttujat, tavoitteet, rajoitukset ja merkityksen. Määritetyn ongelman avulla voimme ratkaista ongelman:

prob = KnapsackProblem() prob.solve()

Ratkaisun jälkeen voimme tulostaa tulokset ongelmaluokan print_results avulla toiminto. Voimme myös käyttää tiettyjen muuttujien arvoa tarkastelemalla result_variables luokassa.

prob.print_results() print(prob.result_variables)

Suorita komentosarja, ja sinun pitäisi nähdä seuraava tulos:

KnapsackProblem: Optimal camera 0.0 figurine 1.0 cider 0.0 horn 1.0 ValueObjective: 17.00 SizeConstraint: 14.00 {'camera': 0.0, 'figurine': 1.0, 'cider': 0.0, 'horn': 1.0}

Sinun pitäisi nähdä ongelman tila, muuttujien lopullinen arvo, tavoitearvo ja rajoituslausekkeen arvo. Näemme myös muuttujien tuloksena olevat arvot sanakirjana.

Ja meillä on se, ensimmäinen HorusLP-ongelmamme noin 35 rivillä!

Tulevissa esimerkeissä tutkimme HorusLP-kirjaston hienostuneempia ominaisuuksia.

VariableGroups-sovelluksen käyttäminen

Joskus muuttujat liittyvät toisiinsa ja kuuluvat loogiseen ryhmään. Selkäreppuongelman tapauksessa kaikki muuttujat voidaan sijoittaa objektiryhmään. Voimme muuttaa koodia muuttujaryhmän käyttämiseksi. Varmista, että tallennat edellisen osan koodin, koska viittaamme siihen seuraavissa opetusohjelmissa!

Muuta tuontilausekkeita seuraavasti:

from horuslp.core.Variables import BinaryVariableGroup from horuslp.core import Constraint, VariableManager, Problem, ObjectiveComponent from horuslp.core.constants import MAXIMIZE

Nyt meidän on myös muutettava reppumuuttujan ilmoituksia näin:

class KnapsackVariables(VariableManager): vars = [ BinaryVariableGroup('objects', [ 'camera', 'figurine', 'cider', 'horn' ]) ]

Ensimmäinen argumentti on muuttujaryhmän nimi, toinen muuttuja on luettelo ryhmän muuttujien nimistä.

Nyt meidän on muutettava rajoituksia ja objektiivisia määritelmiä. Yksittäisten nimien kyselemisen sijaan käytämme muuttujaryhmää, joka välitetään sanakirjana, jossa avaimet ovat nimiä ja arvot ovat muuttujia. Muuta rajoitusta ja objektiivisia määritelmiä näin:

class SizeConstraint(Constraint): def define(self, objects): return 2 * objects['camera'] + 4 * objects['figurine'] + 7 * objects['cider'] + 10 * objects['horn'] <= 15 class ValueObjective(ObjectiveComponent): def define(self, objects): return 5 * objects['camera'] + 7 * objects['figurine'] + 2 * objects['cider'] + 10 * objects['horn']

Nyt voimme käyttää samaa ongelman määrittelyä ja suorittaa komentoja:

class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [SizeConstraint] sense = MAXIMIZE prob = KnapsackProblem() prob.solve() prob.print_results() print(prob.result_variables)

Sinun pitäisi nähdä tämä tulosteessasi:

KnapsackProblem: Optimal objects[camera] 0.0 objects[figurine] 1.0 objects[cider] 0.0 objects[horn] 1.0 ValueObjective: 17.00 SizeConstraint: 14.00 {'objects': {'camera': 0.0, 'figuring': 1.0, 'cider': 0.0, 'horn': 1.0}}

Useiden rajoitusten hallinta

Mallit, joilla on yksi rajoitus, ovat suhteellisen harvinaisia. Kun työskentelet useilla rajoituksilla, on hyvä, että kaikki rajoitukset ovat yhdessä paikassa, jotta niitä voidaan seurata ja hallita helposti. HorusLP tekee siitä luonnollisen.

Oletetaan esimerkiksi, että halusimme nähdä, kuinka tulokset muuttuvat, jos pakotamme mallin lisäämään kameran reppuusi. Otamme käyttöön lisärajoituksen ja lisäämme sen ongelman määrittelyyn.

Palaa malliin, jonka otimme käyttöön ensimmäisessä opetusohjelmassa. Lisää seuraava rajoitus:

class MustHaveItemConstraint(Constraint): def define(self, camera): return camera >= 1

Rajoituksen lisäämiseksi malliin meidän on vain lisättävä se ongelman määrittelyyn näin:

class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [ SizeConstraint, MustHaveItemConstraint # just add this line :) ] sense = MAXIMIZE

Suorita ongelma, ja sinun pitäisi nähdä seuraava tulos:

KnapsackProblem: Optimal camera 1.0 figurine 0.0 cider 0.0 horn 1.0 ValueObjective: 15.00 SizeConstraint: 12.00 MustHaveItemConstraint: 1.00

Sinun pitäisi nähdä uusi rajoitus tulostettavana vakiona ja muuttuneet optimaalisen muuttujan arvot.

Riippuvien rajoitusten ja rajoiteryhmien hallinta

Rajoitukset liittyvät usein toisiinsa joko siksi, että ne ovat riippuvaisia ​​toisistaan, tai siksi, että ne kuuluvat loogisesti samaan ryhmään.

Jos esimerkiksi haluat asettaa rajoituksen muuttujien joukon absoluuttisen arvon summan rajoittamiseksi, sinun on ensin määriteltävä rajoitukset ilmaisemaan aiottujen muuttujien absoluuttiset arvosuhteet ja määritettävä sitten absoluuttiset arvorajat. Joskus sinun on sovellettava samanlaisia ​​rajoituksia muuttujaryhmään ilmaisemaan muuttujien välinen tietty suhde.

Näiden ryhmittelyjen ilmaisemiseksi voimme käyttää rajoitusten määrittelyjen riippuvaisia ​​rajoituksia. Tarkastele SizeConstraint -merkkiä nähdäksesi, kuinka riippuvaisen rajoitteen ominaisuutta voidaan käyttää edellisen ongelman kaltaiset:

class SizeConstraint(Constraint): dependent_constraints = [MustHaveItemConstraint] def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

Ja nyt testataksemme, että riippuvat rajoitteet toteutetaan automaattisesti, ottakaamme MustHaveItemConstraint pois ongelman määritelmästä:

class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [ SizeConstraint, ] sense = MAXIMIZE

Suorita koodi uudelleen, ja sinun pitäisi nähdä seuraava stdout:

KnapsackProblem: Optimal camera 1.0 figurine 0.0 cider 0.0 horn 1.0 ValueObjective: 15.00 SizeConstraint: 12.00 MustHaveItemConstraint: 1.00

Näyttää siltä, ​​että MustHaveItemConstraint on toteutettu! Katso monimutkaisempi esimerkki siitä, miten riippuvaisia ​​rajoituksia voidaan käyttää, tutustumalla opetusohjelman lopussa olevaan henkilöstöesimerkkiin.

Useiden painotettujen tavoitteiden hallinta

Usein, kun kehitämme optimointialgoritmeja, kohtaamme objektiivisen lausekkeen, joka koostuu useista osista. Osana kokeilua voimme muuttaa erilaisten objektiivisten komponenttien punnituksen siten, että algoritmi kohdistuu haluttuun lopputulokseen. CombinedObjective tarjoaa puhtaan ja yksinkertaisen tavan ilmaista tämä.

Oletetaan, että halusimme painottaa algoritmia valitsemaan hahmo ja siideri. Refraktoidaan edellisen osan koodi käyttää CombinedObjective.

Tuo ensin CombinedObjective luokka kuten:

from horuslp.core import CombinedObjective

Voimme toteuttaa itsenäisen objektiivisen komponentin, kuten:

class ILoveCiderFigurineObjectiveComponent(ObjectiveComponent): def define(self, figurine, cider): return figurine + cider

Nyt voimme yhdistää arvotavoitteen ja siiderin / hahmotavoitteen toteuttamalla CombinedObjective

class Combined(CombinedObjective): objectives = [ (ILoveCiderFigurineObjectiveComponent, 2), # first argument is the objective, second argument is the weight (ValueObjectiveComponent, 1) ]

Muutetaan nyt ongelman määritelmää näin:

class KnapsackProblem(Problem): variables = KnapsackVariables objective = Combined constraints = [SizeConstraint] sense = MAXIMIZE

Suorita ongelma, ja sinun pitäisi nähdä seuraava tulos:

KnapsackProblem: Optimal camera 1.0 figurine 1.0 cider 1.0 horn 0.0 Combined: 18.00 ILoveCiderFigurineObjectiveComponent: 2.00 * 2 ValueObjectiveComponent: 14.00 * 1 SizeConstraint: 13.00 MustHaveItemConstraint: 1.00

Tuloksessa hahmotellaan yhdistetty tavoitearvo, kunkin objektiivisen komponentin arvo, paino ja tietysti kaikkien rajoitusten arvo.

Yhteensopimattomien rajoitusten löytäminen

Algoritmeja kehitettäessä törmäämme usein mahdottomiin malleihin. Jos malli on monimutkainen, voi olla haastavaa määrittää, miksi malli on yhtäkkiä mahdoton. HorusLP: llä on kätevä työkalu, joka auttaa sinua näissä tapauksissa.

Oletetaan, että lisäsimme rajoituksia ja päädyimme seuraaviin rajoituksiin:

class SizeConstraint(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15 class SizeConstraint2(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn = 1 class IncompatibleConstraint1(Constraint): def define(self, camera): return camera>= 1 class IncompatibleConstraint2(Constraint): def define(self, camera): return camera <= 0

Meillä on pari rajoitusta repun esineiden kokonaiskokoon, rajoitus, joka edellyttää, että siiderin on oltava repussa, ja yhteensopimaton joukko rajoituksia, jotka edellyttävät kameran olevan sekä repussa että sen ulkopuolella. (Tietysti tosielämän algoritmissa rajoitukset eivät yleensä ole yhtä ilmeisiä ja sisältävät monimutkaisia ​​muuttujasuhteita ja rajoituksia.)

Oletetaan myös, että rajoitukset on ryhmitelty seuraavalla tavalla, mikä ehkä vaikeuttaa havaitsemista:

class CombinedConstraints1(Constraint): dependent_constraints = [SizeConstraint2, IncompatibleConstraint1] class CombinedConstraints2(Constraint): dependent_constraints = [SizeConstraint, IncompatibleConstraint2] # MustHaveItemConstraint will be included in the problem definition independently

Tässä on ongelman määrittely:

class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [CombinedConstraints1, CombinedConstraints2, MustHaveItemConstraint] sense = MAXIMIZE

Suorita ongelma, ja sinun pitäisi nähdä seuraava tulos:

KnapsackProblem: Infeasible

Voi ei! Mitä me teemme? Jos käytämme suurinta osaa työkaluista, meidän on aloitettava vaikea virheenkorjausistunto, jossa kavennamme mahdollisesti ristiriitaisia ​​rajoituksia yksi kerrallaan. Onneksi HorusLP: llä on yhteensopimattomuushaun ominaisuus, joka auttaa sinua supistamaan yhteensopimattomia rajoituksia nopeammin. Yksinkertaisin tapa käyttää yhteensopimattomuushakutoimintoa on muuttaa print_results soita näin:

prob.print_results(find_infeasible=True)

Niinkin yksinkertaista! Suorita koodi, ja nyt sinun pitäisi nähdä seuraava lähtö:

KnapsackProblem: Infeasible Finding incompatible constraints... Incompatible Constraints: ('CombinedConstraints1', 'CombinedConstraints2')

Loistava! Nyt olemme todenneet, että MustHaveItemConstraint ei ole syy toteutumattomuuteen ja että ongelma johtuu CombinedConstraints1 ja CombinedConstraints2.

Tämä antaa meille jonkin verran tietoa, mutta yhdistettyjen rajoitusten välillä on neljä riippuvaa rajoitusta. Voimmeko tunnistaa, mitkä neljästä rajoituksesta ovat yhteensopimattomia? No kyllä. Muokkaa print_results soita näin:

prob.print_results(find_infeasible=True, deep_infeasibility_search=True)

Tällöin sietokyvyttömyyshaku laajentaa riippuvia rajoituksia niin, että saamme paljon yksityiskohtaisemman kuvan siitä, mikä aiheuttaa sietämättömyyden. Suorita tämä ja sinun pitäisi nähdä seuraava tulos:

KnapsackProblem: Infeasible Finding incompatible constraints... Incompatible Constraints: ('IncompatibleConstraint1', 'IncompatibleConstraint2')

Vaikka on houkuttelevaa suorittaa syvä sietokyvyttömyyshaku joka kerta, realististen ongelmien varalta, joissa on paljon kokonaisrajoituksia, syvä kykenemättömyyshaku voi tulla hyvin resursseja vieväksi ja aikaa vieväksi. Siksi on parasta suorittaa perushautautumattomuushaku mahdollisuuden kaventamiseksi ja suorittaa syväkatsomattomuushaku pienemmällä osajoukolla manuaalisen tutkimuksen jälkeen.

Algoritmien rakentaminen datatiedostoista

Rakennettaessa malleja meillä on harvoin ylellisyyttä koodata jokainen rajoitus ja muuttuja. Usein ohjelmamme on oltava riittävän joustava vaihtamaan mallia syötetiedoista riippuen. Oletetaan, että kovakoodatun syötteen sijasta halusimme rakentaa reppuongelmamme seuraavasta JSON: sta:

{ 'items': [ {'name': 'camera', 'value': 5, 'weight': 2}, {'name': 'figurine', 'value': 7, 'weight': 4}, {'name': 'apple', 'value': 2, 'weight': 7}, {'name': 'horn', 'value': 10, 'weight': 10}, {'name': 'banana', 'value': 9, 'weight': 2} ], 'capacity': 15 }

Voimme tehdä tämän tukeutumalla kwargsin tukeen 'määritä' -toiminnolle, jonka toteutamme rajoitusten ja tavoitteiden saavuttamiseksi.

Muokkaamme koodia yksinkertaisesta reppuongelmasta (ongelma, jonka toteutimme opetusohjelman osassa 1). Laitetaan ensin JSON-merkkijono tiedostoon. Luemme tietysti normaalisti sen ulkoisesta lähteestä, mutta säilytetään yksinkertaisuuden vuoksi kaikki yhdessä tiedostossa. Lisää seuraava koodiisi:

JSON = ''' { 'items': [ {'name': 'camera', 'value': 5, 'weight': 2}, {'name': 'figurine', 'value': 7, 'weight': 4}, {'name': 'apple', 'value': 2, 'weight': 7}, {'name': 'horn', 'value': 10, 'weight': 10}, {'name': 'banana', 'value': 9, 'weight': 2} ], 'capacity': 15 } '''

Varmista myös, että ohjelmamme pystyy jäsentämään sen. Lisää seuraava tuontilausekkeisiin:

Import json

Muutetaan muuttujan asetuskoodia näin:

mip_cfg = json.loads(JSON) class KnapsackVariables(VariableManager): vars = [ BinaryVariable(i['name']) for i in mip_cfg['items'] ]

Tämä määrittelee muuttujan jokaiselle JSON-tuotteelle ja nimeää sen asianmukaisesti.

Muutetaan rajoituksia ja objektiivisia määritelmiä näin:

class CapacityConstraint(Constraint): def define(self, **kwargs): item_dict = {i['name']: i['weight'] for i in mip_cfg['items']} return sum(kwargs[name] * item_dict[name] for name in kwargs) <= mip_cfg['capacity'] class ValueObjective(ObjectiveComponent): def define(self, **kwargs): item_dict = {i['name']: i['value'] for i in mip_cfg['items']} return sum(kwargs[name] * item_dict[name] for name in kwargs)

Pyytämällä **kwargs tiettyjen muuttujien sijaan define function saa sanakirjan, joka sisältää kaikki muuttujat nimen mukaan. Rajoituksen määritystoiminto voi sitten käyttää muuttujia sanakirjasta.

Huomautus: Muuttujaryhmille se on sisäkkäinen sanakirja, jossa ensimmäinen taso on ryhmän nimi ja toinen taso muuttujan nimi.

Loput ovat melko suoraviivaisia:

class KnapsackProblem(Problem): variables = KnapsackVariables constraints = [CapacityConstraint] objective = ValueObjective sense = MAXIMIZE prob = KnapsackProblem() prob.solve() prob.print_results()

Suorita tämä ohjelma ja sinun pitäisi nähdä seuraava tulos:

KnapsackProblem: Optimal camera 1.0 figurine 0.0 apple 0.0 horn 1.0 banana 1.0 ValueObjective: 24.00 CapacityConstraint: 14.00

Mukautettujen tietojen määrittäminen HorusLP: ssä

Joskus sekä virheenkorjausta että raportointia varten rakennamme mukautettuja mittareita, joita ei ilmaista suoraan tavoitteessa tai rajoituksena. HorusLP: ssä on ominaisuus, joka tekee mukautettujen mittareiden määrittämisestä helppoa.

Oletetaan, että halusimme seurata, kuinka monta hedelmää edellisen osan mallimme laittaa reppuun. Tämän seuraamiseksi voimme määrittää mukautetun muuttujan. Aloitetaan tuomalla Metrics-perusluokka:

From horuslp.core import Metric

Määritellään nyt oma muuttuja:

class NumFruits(Metric): name = 'Number of Fruits' def define(self, apple, banana): return apple + banana

Kuten näette, määritetty käyttöliittymä näyttää hyvin samanlaiselta kuin rajoitus- ja objektiivikomponenttiluokan. Jos olet tähän mennessä seurannut opetusohjelmaa, sen pitäisi olla sinulle melko tuttu.

Nyt meidän on lisättävä metriikka ongelman määrittelyyn. Tässäkin käyttöliittymä on jälleen hyvin samanlainen kuin rajoituksen määritelmä:

class KnapsackProblem(Problem): variables = KnapsackVariables constraints = [CapacityConstraint] objective = ValueObjective metrics = [NumFruits] sense = MAXIMIZE

Suorita tämä ja sinun pitäisi nähdä seuraava tulos:

KnapsackProblem: Optimal camera 1.0 figurine 0.0 apple 0.0 horn 1.0 banana 1.0 ValueObjective: 24.00 CapacityConstraint: 14.00 Number of Fruits: 1.00

Alareunassa näkyy tulostettujen hedelmien määrä.

Monimutkaisemman ongelman ratkaiseminen: Kaksi reppua

Selvitetään hieman monimutkaisempi esimerkki. Oletetaan, että yhden repun sijaan meillä on laukku ja matkalaukku. Meillä on myös kaksi luokkaa esineitä, kestäviä ja hauraita. Suojaavampaan matkalaukkuun mahtuu sekä hauraita että kestäviä tavaroita. Laukku toisaalta mahtuu vain kestotavaroita. Oletetaan myös, että kohteiden tiedot annetaan seuraavassa JSON: ssa:

{ 'fragile': [ {'name': 'camera', 'value': 5, 'weight': 2}, {'name': 'glasses', 'value': 3, 'weight': 4}, {'name': 'apple', 'value': 2, 'weight': 7}, {'name': 'pear', 'value': 5, 'weight': 3}, {'name': 'banana', 'value': 9, 'weight': 2} ], 'durable': [ {'name': 'figurine', 'value': 7, 'weight': 4}, {'name': 'horn', 'value': 10, 'weight': 10}, {'name': 'leatherman', 'value': 10, 'weight': 3} ], 'suitcase_capacity': 15, 'bag_capacity': 20 }

Katsotaanpa, miten tämä muuttaa mallia. Aloitetaan tyhjällä taululla, koska malli on melko erilainen. Aloita ongelman määrityksellä:

import json from horuslp.core.Variables import BinaryVariableGroup from horuslp.core import Constraint, VariableManager, Problem, Metric, ObjectiveComponent from horuslp.core.constants import MAXIMIZE JSON = ''' { 'fragile': [ {'name': 'camera', 'value': 5, 'weight': 2}, {'name': 'glasses', 'value': 3, 'weight': 4}, {'name': 'apple', 'value': 2, 'weight': 7}, {'name': 'pear', 'value': 5, 'weight': 3}, {'name': 'banana', 'value': 9, 'weight': 2} ], 'durable': [ {'name': 'figurine', 'value': 7, 'weight': 4}, {'name': 'horn', 'value': 10, 'weight': 10}, {'name': 'leatherman', 'value': 10, 'weight': 3} ], 'suitcase_capacity': 15, 'bag_capacity': 20 } ''' mip_cfg = json.loads(JSON)

Määritetään nyt muuttujat. Perustamme binaarimuuttujan jokaiselle mahdolliselle tuote / säilöyhdistelmälle.

class KnapsackVariables(VariableManager): vars = [ # suitcase can hold both fragile and durable goods BinaryVariableGroup('suitcase_f', [i['name'] for i in mip_cfg['fragile']]), BinaryVariableGroup('suitcase_d', [i['name'] for i in mip_cfg['durable']]), # bag can only hold durable goods. BinaryVariableGroup('bag_d', [i['name'] for i in mip_cfg['durable']]) ]

Nyt haluamme toteuttaa painorajoitukset sekä matkalaukulle että laukulle.

class SuitcaseCapacityConstraint(Constraint): def define(self, suitcase_d, suitcase_f): fragile_weight = sum([suitcase_f[i['name']] * i['weight'] for i in mip_cfg['fragile']]) durable_weight = sum([suitcase_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) return fragile_weight + durable_weight <= mip_cfg['suitcase_capacity'] class BagCapacityConstraint(Constraint): def define(self, bag_d): durable_weight = sum([bag_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) return durable_weight <= mip_cfg['bag_capacity']

Nyt meidän on pantava täytäntöön hieman monimutkaisempi rajoitus - rajoitus, jolla varmistetaan, että esine ei mene sekä matkalaukkuun että laukkuun - eli jos muuttuja 'matkalaukussa' on 1, niin 'pussissa' muuttujan on oltava nolla, ja päinvastoin. Tietenkin haluamme varmistaa, että sallitaan tapaukset, joissa kohde päätyy myöskään kumpaankin konttiin.

Tämän rajoituksen lisäämiseksi meidän on toistettava kaikki kestävät tuotteet, löydettävä muuttuja ”matkalaukussa” ja ”pussissa” ja väitettävä, että näiden muuttujien summa on alle 1.

Voimme määritellä riippuvaiset rajoitukset dynaamisesti melko helposti HorusLP: ssä:

class UniquenessConstraints(Constraint): def __init__(self): super(UniquenessConstraints, self).__init__() # call the dependent constraint builder function for every durable item, and push them into dependent constraints. dependent_constraints = [self.define_uniqueness_constraint(item) for item in mip_cfg['durable']] self.dependent_constraints = dependent_constraints def define_uniqueness_constraint(self, item): # classes are first-class objects in python, so we can define a class within this function and return it class UQConstraint(Constraint): # we name the constraint based on the item this is for, so that debugging is easier. name = 'Uniqueness_%s' % item['name'] def define(self, suitcase_d, bag_d): # the define function can access the variables much in the same way as other functions return suitcase_d[item['name']] + bag_d[item['name']] <= 1 return UQConstraint

Nyt kun rajoitteet on määritelty, rakennetaan tavoite. Tavoite on yksinkertainen kaikkien arvojen summa, jonka saamme kaikista esineistä, jotka ovat säiliöissä. Täten:

class TotalValueObjective(ObjectiveComponent): def define(self, suitcase_f, suitcase_d, bag_d): fragile_value = sum([suitcase_f[i['name']] * i['weight'] for i in mip_cfg['fragile']]) durable_value_s = sum([suitcase_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) durable_value_d = sum([bag_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) return fragile_value + durable_value_s + durable_value_d

Määritellään myös joitain mukautettuja mittareita, jotta voimme nähdä yhdellä silmäyksellä, kuinka paljon painoa laukkuun ja matkalaukkuun pantiin, samoin kuin kuinka paljon matkalaukun painosta oli kestotavaroita ja hauraita tavaroita:

class SuitcaseFragileWeightMetric(Metric): def define(self, suitcase_f): return sum([suitcase_f[i['name']] * i['weight'] for i in mip_cfg['fragile']]) class SuitcaseDurableWeightMetric(Metric): def define(self, suitcase_d): return sum([suitcase_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) class BagWeightMetric(Metric): def define(self, bag_d): return sum([bag_d[i['name']] * i['weight'] for i in mip_cfg['durable']])

Nyt kaikki kappaleet ovat valmiit, tehostetaan ongelma ja ajetaan malli:

class KnapsackProblem(Problem): variables = KnapsackVariables constraints = [SuitcaseCapacityConstraint, BagCapacityConstraint, UniquenessConstraints] objective = TotalValueObjective metrics = [SuitcaseDurableValueMetric, SuitcaseFragileValueMetric, BagValueMetric] sense = MAXIMIZE prob = KnapsackProblem() prob.solve() prob.print_results()

Suorita tämä, ja sinun pitäisi nähdä seuraava lähtö lähdekoodissasi:

KnapsackProblem: Optimal suitcase_f[camera] 1.0 suitcase_f[glasses] 1.0 suitcase_f[apple] 1.0 suitcase_f[pear] 0.0 suitcase_f[banana] 1.0 suitcase_d[figurine] 0.0 suitcase_d[horn] 0.0 suitcase_d[leatherman] 0.0 bag_d[figurine] 1.0 bag_d[horn] 1.0 bag_d[leatherman] 1.0 TotalValueObjective: 32.00 SuitcaseCapacityConstraint: 15.00 BagCapacityConstraint: 17.00 Uniqueness_figurine: 1.00 Uniqueness_horn: 1.00 Uniqueness_leatherman: 1.00 SuitcaseDurableWeightMetric: 0.00 SuitcaseFragileWeightMetric: 15.00 BagWeightMetric: 17.00

Joten kamera, lasit, omena ja banaani menevät matkalaukkuun yhteensä 15 painoyksikköä, hahmo, sarvi ja nahkamies menevät pussiin yhteensä 17 painoa. Tavaroiden kokonaisarvo tulee 32 arvoyksikköön. Mielenkiintoista on, että mikään kestotavarasta ei pääty matkalaukkuun, todennäköisesti siksi, että laukussa oli riittävästi kapasiteettia kaikkien kestotavaroiden säilyttämiseen.

Suurempi ja realistisempi skenaario: henkilöstöongelma

Jos olet päässyt tähän mennessä HorusLP-opetusohjelmassa, onnittelut! Sinulla on nyt hyvä idea kuinka käyttää HorusLP: tä.

Kaikki työskentelemämme esimerkit ovat kuitenkin toistaiseksi olleet reppuongelman muunnelmia, ja jotkut vaatimukset ja parametrit ovat hieman epärealistisia. Selvitetään vielä yksi ongelma yhdessä nähdäksesi, kuinka HorusLP pystyy ratkaisemaan realistisemman ongelman. Selvitämme vuoden toisella puoliskolla hahmoteltu henkilöstöongelma edellinen ApeeScape-artikkelini .

Ajan vuoksi etenemme suoraan mallin lopullisesta versiosta (henkilökohtaisten ristiriitojen, työsäännösten ja työntekijöiden korvausten kanssa), mutta alkuperäisen yksinkertaisemman mallin toteutus on saatavana myös GitHubissa.

Aloitetaan siis ongelman asettamisesta:

from horuslp.core.Variables import BinaryVariableGroup, IntegerVariableGroup from horuslp.core import Constraint, VariableManager, Problem, ObjectiveComponent, CombinedObjective from horuslp.core.constants import MINIMIZE shift_requirements = [1, 4, 3, 5, 2] # the number of workers we need to staff for each shift # the availability and pay rates of each of the employees workers = { 'Melisandre': { 'availability': [0, 1, 4], 'cost': 20 }, 'Bran': { 'availability': [1, 2, 3, 4], 'cost': 15 }, 'Cersei': { 'availability': [2, 3], 'cost': 35 }, 'Daenerys': { 'availability': [3, 4], 'cost': 35 }, 'Theon': { 'availability': [1, 3, 4], 'cost': 10 }, 'Jon': { 'availability': [0, 2, 4], 'cost': 25 }, 'Tyrion': { 'availability': [1, 3, 4], 'cost': 30 }, 'Jaime': { 'availability': [1, 2, 4], 'cost': 20 }, 'Arya': { 'availability': [0, 1, 3], 'cost': 20 } } # the following people can't work together, sadly. ban_list = { ('Daenerys', 'Jaime'), ('Daenerys', 'Cersei'), ('Jon', 'Jaime'), ('Jon', 'Cersei'), ('Arya', 'Jaime'), ('Arya', 'Cersei'), ('Arya', 'Melisandre'), ('Jaime', 'Cersei') } # Dothraki Staffing Corp will provide us with expensive temp workers DOTHRAKI_MAX = 10 DOTHRAKI_COST = 45

Määritellään nyt muuttujat, jotka tässä tapauksessa olisivat binäärimuuttujia, jotka määrittävät, pitäisikö työntekijän työskennellä vuorossaan, ja kokonaislukumuuttujat, jotka määrittävät, kuinka monta dothrakia palkkaamme kullekin työlle:

class StaffingVariables(VariableManager): vars = [] def __init__(self): # like dependent constraints, we can dynamically define variables in the init function super(StaffingVariables, self).__init__() # regular workers varkeys = [] for employee, availability_info in workers.items(): for shift in availability_info['availability']: varkeys.append((employee, shift)) self.vars.append(BinaryVariableGroup('employee_shifts', varkeys)) # dothrakis dothraki_keys = [i for i in range(len(shift_requirements))] self.vars.append(IntegerVariableGroup('dothraki_workers', dothraki_keys, 0, DOTHRAKI_COST))

Toteutetaan nyt rajoitus, joka vaatii meitä henkilöstöä riittävästi jokaiseen vuoroon:

class SufficientStaffingConstraint(Constraint): # we need to staff people sufficiently dependent_constraints = [] def __init__(self): super(SufficientStaffingConstraint, self).__init__() for shift_num, shift_req in enumerate(shift_requirements): self.dependent_constraints.append(self.build_shift_constraint(shift_num, shift_req)) def build_shift_constraint(self, sn, sr): class ShiftConstraint(Constraint): name = 'shift_requirement_%d' % sn def define(self, employee_shifts, dothraki_workers): variables = [val for key, val in employee_shifts.items() if key[1] == sn] variables.append(dothraki_workers[sn]) return sum(variables) >= sr return ShiftConstraint

Nyt meidän on pantava täytäntöön rajoitukset, jotka estävät tiettyjä ihmisiä työskentelemästä keskenään:

class PersonalConflictsConstraint(Constraint): # some people can't work together dependent_constraints = [] def __init__(self): super(PersonalConflictsConstraint, self).__init__() for person_1, person_2 in ban_list: for shift in range(len(shift_requirements)): self.dependent_constraints.append(self.build_conflict_constraint(person_1, person_2, shift)) def build_conflict_constraint(self, p1, p2, s): class ConflictConstraint(Constraint): name = 'Conflict_%s_%s_%d' % (p1, p2, s) def define(self, employee_shifts): if (p1, s) in employee_shifts and (p2, s) in employee_shifts: return employee_shifts[p1, s] + employee_shifts[p2, s] <= 1 return True # returning true will make the constraint do nothing return ConflictConstraint

Ja lopuksi työnormien rajoitus. Toteutamme tämän hieman eri tavalla esittelytarkoituksiin:

class LaborStandardsConstraint(Constraint): # we can make someone work more than two shifts a day. dependent_constraints = [] def __init__(self): super(LaborStandardsConstraint, self).__init__() for worker in workers.keys(): # we don't need a constraint builder function, but in those circumstances # we need to set the needed values as class variables and refer to them # via the self keyword due to how python's closure system works class LaborConstraint(Constraint): # we can't use worker directly! wk = worker name = 'labor_standard_%s' % worker def define(self, employee_shifts): # we need to access the worker using self. Change self.wk to worker to see # why we need to do this worker_vars = [var for key, var in employee_shifts.items() if key[0] == self.wk] return sum(worker_vars) <= 2 self.dependent_constraints.append(LaborConstraint)

Ja nyt asetetaan tavoitteet. Dothrakin kustannukset ja säännölliset työntekijäkustannukset lasketaan hyvin eri tavalla, joten laitamme ne erillisiin objektiivisiin osiin:

class CostObjective(ObjectiveComponent): # this is the cost function for all the named workers def define(self, employee_shifts, dothraki_workers): costs = [ workers[key[0]]['cost'] * var for key, var in employee_shifts.items() ] return sum(costs) class DothrakiCostObjective(ObjectiveComponent): # don't forget the Dothrakis def define(self, dothraki_workers): dothraki_costs = [ dothraki_workers[sn] * DOTHRAKI_COST for sn in dothraki_workers ] return sum(dothraki_costs) class TotalCostObjective(CombinedObjective): objectives = [ (CostObjective, 1), (DothrakiCostObjective, 1) ]

Ja nyt voimme määritellä ja suorittaa ongelman:

class StaffingProblem(Problem): variables = StaffingVariables objective = TotalCostObjective constraints = [SufficientStaffingConstraint, PersonalConflictsConstraint, LaborStandardsConstraint] sense = MINIMIZE # we're minimizing this time, not maximizing. if __name__ == '__main__': prob = StaffingProblem() prob.solve() prob.print_results()

Suorita komentosarja ja sinun pitäisi nähdä seuraava:

StaffingProblem: Optimal employee_shifts[('Melisandre', 0)] 0.0 employee_shifts[('Melisandre', 1)] 1.0 employee_shifts[('Melisandre', 4)] 1.0 employee_shifts[('Bran', 1)] 0.0 employee_shifts[('Bran', 2)] 1.0 employee_shifts[('Bran', 3)] 1.0 employee_shifts[('Bran', 4)] 0.0 employee_shifts[('Cersei', 2)] 0.0 employee_shifts[('Cersei', 3)] 0.0 employee_shifts[('Daenerys', 3)] 1.0 employee_shifts[('Daenerys', 4)] 0.0 employee_shifts[('Theon', 1)] 1.0 employee_shifts[('Theon', 3)] 1.0 employee_shifts[('Theon', 4)] 0.0 employee_shifts[('Jon', 0)] 0.0 employee_shifts[('Jon', 2)] 1.0 employee_shifts[('Jon', 4)] 0.0 employee_shifts[('Tyrion', 1)] 1.0 employee_shifts[('Tyrion', 3)] 1.0 employee_shifts[('Tyrion', 4)] 0.0 employee_shifts[('Jaime', 1)] 1.0 employee_shifts[('Jaime', 2)] 0.0 employee_shifts[('Jaime', 4)] 1.0 employee_shifts[('Arya', 0)] 1.0 employee_shifts[('Arya', 1)] 0.0 employee_shifts[('Arya', 3)] 1.0 dothraki_workers[0] 0.0 dothraki_workers[1] 0.0 dothraki_workers[2] 1.0 dothraki_workers[3] 0.0 dothraki_workers[4] 0.0 TotalCostObjective: 335.00 CostObjective: 290.00 * 1 DothrakiCostObjective: 45.00 * 1 shift_requirement_0: 1.00 shift_requirement_1: 4.00 shift_requirement_2: 3.00 shift_requirement_3: 5.00 shift_requirement_4: 2.00 Conflict_Jon_Cersei_2: 1.00 Conflict_Jon_Jaime_2: 1.00 Conflict_Jon_Jaime_4: 1.00 Conflict_Daenerys_Cersei_3: 1.00 Conflict_Daenerys_Jaime_4: 1.00 Conflict_Arya_Jaime_1: 1.00 Conflict_Arya_Cersei_3: 1.00 Conflict_Arya_Melisandre_0: 1.00 Conflict_Arya_Melisandre_1: 1.00 Conflict_Jaime_Cersei_2: 0.00 labor_standard_Melisandre: 2.00 labor_standard_Bran: 2.00 labor_standard_Cersei: 0.00 labor_standard_Daenerys: 1.00 labor_standard_Theon: 2.00 labor_standard_Jon: 1.00 labor_standard_Tyrion: 2.00 labor_standard_Jaime: 2.00 labor_standard_Arya: 2.00

Jos verrataan tätä ongelmaan, jonka toteutimme edellisessä opetusohjelmassa, sinun pitäisi nähdä, että tulokset vastaavat.

Käärimistä

Onnittelut ensimmäisen HorusLP-opetusohjelmamme suorittamisesta! Olet nyt osaava HorusLP-harjoittaja.

Toivon, että tämä artikkeli vakuutti sinut oman arkkitehtuurisi eduista MIP-mallit ja että käytät HorusLP: tä tulevissa projekteissasi. Löydät HorusLP-lähdekoodin sekä kaikkien opetusohjelmien koodin GitHub . Lisä HorusLP-dokumentaatio ja opastussivu lisätään GitHubiin hyvin pian.

Koska HorusLP on melko uusi projekti, haluaisimme kuulla sinusta ja sisällyttää siihen panoksesi. Jos sinulla on kysyttävää, kommentteja tai ehdotuksia, pudota minulle rivi joko ApeeScapen kautta tai käyttämällä GitHubissa olevia yhteystietoja. Toivon kuulevani sinusta pian!

Perustietojen ymmärtäminen

Mikä on HorusLP?

HorusLP on Python-optimointikirjasto, joka on suunniteltu auttamaan sinua algoritmikehityksen työnkulkujen suunnittelussa. Sillä on yksinkertainen, selkeä sovellusliittymä ja hyvin vähän kattilaa.

Mikä on Knapsnack-ongelma?

Knapsnack-ongelma on optimointiongelma, joka keskittyy kombinatoriseen optimointiin. Esitettynä joukko eriä, joilla on erilainen paino ja arvo, tavoitteena on 'sovittaa' niin moni niistä reppuun, joka on rajoitettu eikä muutu.