Många verkliga problem, t.ex. Personalplanering och transportplanering, kan modelleras naturligt som Restricted Shortest Path Problems (CSPPs), dvs. som Shortest Path Problems med ytterligare begränsningar. Ett väl studerat problem i denna klass är Resurskonstruerade Kortaste Path Problem. Reduktionstekniker är viktiga beståndsdelar i lösare för CSPP, som ofta är NP-hårda, beroende på arten av de ytterligare begränsningarna. Sedd som heurist har dessa tekniker inte studerats teoretiskt med avseende på deras effektivitet, d.v.s. med avseende på förhållandet mellan filtreringskraft och körtid. Med hjälp av koncepten för begränsningsprogrammering ger vi en teoretisk studie av kostnadsbaserad filtrering för kortare vägbegränsningar på acykliska, på oriktade, och på riktade grafer som inte innehåller negativa cykler. Vi visar sedan empiriskt hur resonemang om väg-substrukturer i kombination med CP-baserad Lagrangian avslappning kan bidra till att avsevärt förbättra över tidigare utvecklade problem-skräddarsydda filtreringsalgoritmer för resursen begränsas kortaste vägen problem och undersöka effekterna av nödvändig-kant detektering, oriktad kontra riktad filtrering, och valet av algoritm optimera den Lagrangian dubbla.
Ett exempel på den senare situationen är den kortaste vägrestriktionen, som är optimeringsversionen av vägrestriktionen REF.
Cost-based Filtering for Shorter Path Constraints
{'venue': 'Constraints', 'journal': 'Constraints', 'mag_field_of_study': ['Computer Science', 'Mathematics']}