Кіріспе
Дуальды мәселе – бастапқы мәселенің әрбір шектеуін айнымалы ретінде көрсететін шектеулерді қанағаттандыру мәселесінің қайта формулировкасы. Дуальды мәселелерде тек екілік шектеулер ғана болады, сондықтан оларды осындай мәселелерге арналған алгоритмдермен шешуге болады. Шектеулерді қанағаттандыру мәселесінің қосылу графиктері мен қосылу ағаштары – оның дуальды мәселесін немесе дуальды мәселеден кейбір артық шектеулерді жойғаннан кейін алынған мәселені көрсететін графиктер.
Екілік проблема
Қиындықты қанағаттандыру мәселесінің дуалды проблемасы бастапқы проблеманың әрбір шектеуі үшін бір айнымалыны қамтиды. Оның домендері мен шектеулері бастапқы проблемаға эквиваленттілікті қамтамасыз ету үшін құрылған. Атап айтқанда, дуалды проблеманың айнымалысының доменінде сәйкес бастапқы шектеуді қанағаттандыратын әрбір топтама үшін бір элемент бар. Осылайша, дуалды айнымалы тек қана сәйкес келетін бастапқы шектеуді сәйкес келетін топтама қанағаттандырса ғана мән ала алады. Дуалды проблеманың шектеулері екі үйлесімсіз топтамаға сәйкес келетін екі дуалды айнымалының мәндерін алуына тыйым салады. Бұл шектеулер болмаса, бір дуалды айнымалы топтамаға сәйкес келетін мәнді алса, ал екінші дуалды айнымалы басқа мәнді тағайындайтын топтамаға сәйкес келетін мәнді алуы мүмкін. Жалпы алғанда, дуалды проблеманың шектеулері екі шектеудің ортақ айнымалылары үшін бірдей мәндерді қамтамасыз етеді. Егер екі дуалды айнымалы кейбір айнымалыларды бөлісетін шектеулерге сәйкес келсе, дуалды проблемада олардың арасындағы шектеу болады, ол барлық ортақ айнымалылардың теңдігін қамтамасыз етеді. Дуалды айнымалылар – бастапқы проблеманың шектеулері. Әрбір дуалды айнымалының домені – сәйкес бастапқы шектеудің топтамаларының жиынтығы. Дуалды шектеулер дуалды айнымалыларды (бастапқы шектеулерді) бастапқы айнымалылардың тең мәндерін қамтитын мәндерге (топтамаларға) ие болуға мәжбүрлейді. Бұл мысалда, бастапқы шектеулер мен ортақ айнымалыға ие, дуалды проблемада айнымалылар мен мәндерге ие болуға рұқсат етіледі, себебі бұл мәндер келіседі. Дуалды проблемадағы барлық шектеулер екілік. Олардың барлығы бір немесе бірнеше бастапқы айнымалылар бойынша келісу үшін екі мәнді, яғни топтамаларды, қамтамасыз етеді. Дуалды граф – дуалды проблемада айнымалылардың қалай шектелетінін көрсететін график. Нақтырақ айтқанда, дуалды графта әр дуалды айнымалы үшін түйін және олардың арасындағы әрбір шектеу үшін жиек бар. Сонымен қатар, екі айнымалы арасындағы жиек осы екі дуалды айнымалы арасында теңдік күштелген бастапқы айнымалылармен таңбаланады. Дуалды графты тікелей бастапқы проблемадан құрастыруға болады: онда әр шектеу үшін түйін және әр екі шектеудің ортақ айнымалылары арасында жиек бар; мұндай жиек осы ортақ айнымалылармен таңбаланады. Дуалды граф. Екі шектеудің арасындағы жиек олардың ортақ айнымалыларының теңдігін қамтамасыз ететін дуалды шектеуге сәйкес келеді. Мысалы, және арасындағы жиек, дуалды проблемада және арасында шектеу бар екенін көрсетеді және бұл шектеу мәндерді (топтамаларды) күштеп қолданады, олар бойынша келіседі.
More generally, the constraints of the dual problem enforce the same values for all variables shared by two constraints. If two dual variables correspond to constraints sharing some variables, the dual problem contains a constraint between them, enforcing equality of all shared variables. The dual variables are the constraints of the original problem. The domain of each dual variable is the set of tuples of the corresponding original constraint. The dual constraints enforce the dual variables (original constraints) to have values (original tuples) that contain equal values of the original variables. In this example, the original constraints and share the variable In the dual problem, the variables and are allowed to have values and because these values agree on
In the dual problem, all constraints are binary. They all enforce two values, which are tuples, to agree on one or more original variables. The dual graph is a representation of how variables are constrained in the dual problem. More precisely, the dual graph contains a node for each dual variable and an edge for every constraint between them. In addition, the edge between two variables is labeled by the original variables that are enforced equal between these two dual variables. The dual graph can be built directly from the original problem: it contains a vertex for each constraint, and an edge between every two constraints sharing variables; such an edge is labeled by these shared variables. A dual graph. An edge between two constraints corresponds to a dual constraint enforcing equality of their shared variables. For example, the edge labeled between and indicates that the dual problem contains a constraint between and , and this constraint enforces values (tuples) that match on and .
Ұзартулар
Барлық шектеулерді қанағаттандыру проблемаларының бірігу ағашы болмайды. Дегенмен, проблемаларды бірігу ағашын алу үшін өзгертуге болады. Бірігу ағашын кластерлеу – проблемаларды осылай өзгертудің нақты бір әдісі, нәтижесінде бірігу ағашы пайда болады. Бұл шектеулерді біріктіру арқылы іске асырылады, бұл әдетте проблеманың мөлшерін ұлғайтады; алайда, осыдан кейін туындаған проблеманы шешу оңай, себебі барлық бірігу ағашы бар проблемаларды оңай шешуге болады. Декомпозиция әдістері бірігу ағашын кластерлеуді жалпылайды, соның нәтижесінде пайда болған проблемада бірігу ағашы болады. Декомпозиция әдістері проблемалармен тікелей байланысты ағаш құрады; осы ағаштың түйіндері бастапқы проблеманың айнымалылары және/немесе шектеулері болып табылады. Осы ағашқа сүйене отырып шектеулерді біріктіру арқылы бірігу ағашына ие проблема жасауға болады, ал бұл бірігу ағашын декомпозиция ағашынан оңай алуға болады. Балама ретінде, декомпозиция ағашынан тікелей екілік ациклді проблеманы құруға болады.