Configuration linear program
உள்ளமைவு நேரியல் நிரல் (உள்ளமைவு-எல்பி) என்பது ஒருங்கிணைந்த உகப்பாக்கம் சிக்கல்களைத் தீர்க்கப் பயன்படுத்தப்படும் ஒரு நேரியல் நிரலாக்க நுட்பமாகும். பங்கு குறைப்பு பிரச்சினையின் பின்னணியில் இது அறிமுகப்படுத்தப்பட்டது. பின்னர், இது தொட்டி பேக்கிங் மற்றும் வேலை திட்டமிடல் சிக்கல்களுக்கு பயன்படுத்தப்பட்டுள்ளது. உள்ளமைவு-எல். பி. யில், ஒவ்வொரு சாத்தியமான உள்ளமைவுக்கும் ஒரு மாறி உள்ளது-ஒவ்வொரு சாத்தியமான பல தொகுப்பு உருப்படிகளும் ஒரு தொட்டியில் பொருந்தக்கூடியவை (இந்த உள்ளமைவுகள் வடிவங்கள் என்றும் அழைக்கப்படுகின்றன). வழக்கமாக, உள்ளமைவுகளின் எண்ணிக்கை சிக்கல் அளவில் அதிவேகமாக இருக்கும், ஆனால் சில சந்தர்ப்பங்களில் ஒரு பல்லுறுப்புக்கோவை எண்ணிக்கையிலான உள்ளமைவுகளை மட்டுமே பயன்படுத்தி தோராயமான தீர்வுகளை அடைய முடியும். பின் பேக்கிங்கில் ஒருங்கிணைந்த எல். பி. பின் பேக்கிங் சிக்கலில், வெவ்வேறு அளவுகளைக் கொண்ட n உருப்படிகள் உள்ளன. பொருட்களை குறைந்தபட்ச எண்ணிக்கையிலான தொட்டிகளில் அடைப்பதே குறிக்கோள், அங்கு ஒவ்வொரு தொட்டியிலும் அதிகபட்சமாக பி இருக்க முடியும். ஒரு சாத்தியமான உள்ளமைவு என்பது அதிகபட்சம் B இன் கூட்டுத்தொகையுடன் கூடிய அளவுகளின் தொகுப்பாகும். எடுத்துக்காட்டுஃ உருப்படி அளவுகள் 3,3,3,3,3,4,4,4,4,4, மற்றும் B = 12 என்று வைத்துக்கொள்வோம். பின்னர் சாத்தியமான உள்ளமைவுகள்ஃ 3333; 333; 33,334,344; 4,44,444. எங்களிடம் அளவு 3 இன் மூன்று உருப்படிகள் மட்டுமே இருந்தால், 3333 உள்ளமைவைப் பயன்படுத்த முடியாது. வெவ்வேறு அளவுகளின் தொகுப்பை (மற்றும் அவற்றின் எண்) S ஆல் குறிக்கவும். வெவ்வேறு உள்ளமைவுகளின் தொகுப்பை (மற்றும் அவற்றின் எண்) சி மூலம் குறிக்கவும். S இல் உள்ள ஒவ்வொரு அளவு s மற்றும் C இல் உள்ளமைவுக்கும், குறிக்கவும்ஃ NS-அளவு s இன் உருப்படிகளின் எண்ணிக்கை. என, c-உள்ளமைவில் உள்ள அளவு s இன் நிகழ்வுகளின் எண்ணிக்கை c. xc-உள்ளமைவுடன் தொட்டிகளின் எண்ணிக்கையைக் குறிக்கும் ஒரு மாறி c. பின்னர், பின்-பேக்கிங்கின் உள்ளமைவு LP: S இல் உள்ள அனைத்து s களுக்கும் (-அளவு s இன் அனைத்து ns உருப்படிகளும் நிரம்பியுள்ளன). C இல் உள்ள அனைத்து c க்கும் (-ஒட்டுமொத்தமாக அதிகபட்சம் n தொட்டிகள் உள்ளன, எனவே ஒவ்வொரு தனிப்பட்ட உள்ளமைவிலும் அதிகபட்சம் n). உள்ளமைவு LP ஒரு முழு எண் நேரியல் நிரலாகும், எனவே பொதுவாக இது NP-கடினமானது. மேலும், சிக்கல் கூட பொதுவாக மிகப் பெரியதுஃ இது சி மாறிகள் மற்றும் எஸ் கட்டுப்பாடுகளைக் கொண்டுள்ளது. மிகச்சிறிய உருப்படி அளவு eB ஆக இருந்தால் (சில பின்னம் e இல் (0,1)), ஒவ்வொரு தொட்டியிலும் 1/e உருப்படிகள் வரை இருக்கலாம், எனவே உள்ளமைவுகளின் எண்ணிக்கை C ~ S1/e, இது e சிறியதாக இருந்தால் மிகப் பெரியதாக இருக்கலாம் (e ஒரு மாறிலி என்று கருதப்பட்டால், முழு எண் LP ஐ முழுமையான தேடல் மூலம் தீர்க்க முடியும்ஃ அதிகபட்ச S1/e உள்ளமைவுகள் உள்ளன, மேலும் ஒவ்வொரு உள்ளமைவிற்கும் அதிகபட்சம் n சாத்தியமான மதிப்புகள் உள்ளன, எனவே சரிபார்க்க பெரும்பாலான சேர்க்கைகள் உள்ளன. ஒவ்வொரு கலவையிலும், நாம் S கட்டுப்பாடுகளை சரிபார்க்க வேண்டும், எனவே ரன்-டைம், இது S, e நிலையானதாக இருக்கும்போது n இல் பல்லுறுப்புக்கோவை). இருப்பினும், இந்த ஐஎல்பி பல தோராயமான வழிமுறைகளுக்கு ஒரு அடிப்படையாக செயல்படுகிறது. இந்த வழிமுறைகளின் முக்கிய யோசனை அசல் நிகழ்வை ஒரு புதிய நிகழ்வாகக் குறைப்பதாகும், இதில் S சிறியது மற்றும் e பெரியது, எனவே C ஒப்பீட்டளவில் சிறியது. பின்னர், ஐஎல்பியை முழுமையான தேடல் மூலம் தீர்க்க முடியும் (எஸ், சி போதுமான அளவு சிறியதாக இருந்தால்), அல்லது அதை ஒரு பகுதியளவு எல்பியாக தளர்த்துவதன் மூலம். பின்ன எல். பி. என்பது பின்-பேக்கிங்கின் பின்ன உள்ளமைவு எல். பி. இது மேலே உள்ள ஐஎல்பியின் நேரியல் நிரலாக்க தளர்வு ஆகும். இது கடைசி தடையை கட்டுப்பாட்டுடன் மாற்றுகிறது. வேறு வார்த்தைகளில் கூறுவதானால், ஒவ்வொரு உள்ளமைவையும் ஒரு பின்ன எண்ணிக்கையிலான முறை பயன்படுத்தலாம். இந்த தளர்வு முதலில் கில்மோர் மற்றும் கோமரி ஆகியோரால் வழங்கப்பட்டது, மேலும் இது பெரும்பாலும் கில்மோர்-கோமரி நேரியல் திட்டம் என்று அழைக்கப்படுகிறது. எடுத்துக்காட்டுஃ அளவு 3 கொண்ட 31 உருப்படிகளும் அளவு 4 கொண்ட 7 உருப்படிகளும் உள்ளன என்று வைத்துக்கொள்வோம், தொட்டி அளவு 10 ஆகும். கட்டமைப்புகள்ஃ 4,44,34,334,3,33,333. கட்டுப்பாடுகள் [0,0,1,2,1,2,3] * x = 31 மற்றும் [1,2,1,1,0,0,0] * x = 7 ஆகும். பின்ன LP க்கு உகந்த தீர்வு [0,0,0,7,0,0,17/3] அதாவதுஃ உள்ளமைவு 334 மற்றும் உள்ளமைவு 333 இன் 7 தொட்டிகள் உள்ளன. இரண்டு வெவ்வேறு உள்ளமைவுகள் மட்டுமே தேவை என்பதை நினைவில் கொள்க. சுருக்கமாக, பின்ன LP ஐ பின்வருமாறு எழுதலாம்ஃ 1 என்பது C அளவின் திசையன் (1,., 1), A என்பது S-by-C மேட்ரிக்ஸ் ஆகும், இதில் ஒவ்வொரு நெடுவரிசையும் ஒற்றை உள்ளமைவைக் குறிக்கிறது, மேலும் n என்பது திசையன் (n1,., nS). பின்ன எல். பி. யைத் தீர்ப்பது ஒருங்கிணைப்பு கட்டுப்பாடுகள் இல்லாத ஒரு நேரியல் நிரலை மாறிகள் மற்றும் கட்டுப்பாடுகளின் எண்ணிக்கையில் நேர பல்லுறுப்புக்கோவையில் தீர்க்க முடியும். சிக்கல் என்னவென்றால், பின்ன உள்ளமைவு LP இல் உள்ள மாறிகளின் எண்ணிக்கை சாத்தியமான உள்ளமைவுகளின் எண்ணிக்கைக்கு சமம், இது மிகப்பெரியதாக இருக்கலாம். கர்மார்கர் மற்றும் கார்ப் இந்த சிக்கலை சமாளிக்கும் ஒரு வழிமுறையை முன்வைக்கின்றனர். முதலில், அவர்கள் பின்ன LP இன் இரட்டை நேரியல் நிரலை உருவாக்குகிறார்கள்ஃ இது S மாறிகள் y1,., yS, மற்றும் C கட்டுப்பாடுகளைக் கொண்டுள்ளதுஃ ஒவ்வொரு உள்ளமைவுக்கும் c, ஒரு கட்டுப்பாடு உள்ளது, அங்கு உள்ளமைவைக் குறிக்கும் A இன் நெடுவரிசை c. 3 இது பின்வரும் பொருளாதார விளக்கத்தைக் கொண்டுள்ளது. ஒவ்வொரு அளவு s க்கும், ஒரு எதிர்மறை அல்லாத விலையை நாம் தீர்மானிக்க வேண்டும். நமது லாபம் என்பது அனைத்து பொருட்களின் மொத்த விலையாகும். ஒவ்வொரு கட்டமைப்பிலும் உள்ள பொருட்களின் மொத்த விலை அதிகபட்சம் 1 என்ற வரம்புகளுக்கு உட்பட்டு லாபத்தை அதிகரிக்க விரும்புகிறோம். இரண்டாவதாக, அவை நீள்வட்ட முறையின் ஒரு மாறுபாட்டைப் பயன்படுத்துகின்றன, இது அனைத்து கட்டுப்பாடுகளையும் பட்டியலிடத் தேவையில்லை-அதற்கு ஒரு பிரிப்பு ஆரக்கிள் தேவைப்படுகிறது. ஒரு பிரிப்பு ஆரக்கிள் என்பது ஒரு வழிமுறை ஆகும், இது ஒரு திசையன் y கொடுக்கப்பட்டால், அது சாத்தியமானது என்று வலியுறுத்துகிறது, அல்லது அது மீறும் ஒரு தடையைக் கண்டறிகிறது. இரட்டை LP க்கான பிரிப்பு ஆரக்கிள் அளவு s மற்றும் மதிப்புகள் y உடன் நாப்சாக் சிக்கலைத் தீர்ப்பதன் மூலம் செயல்படுத்தப்படலாம்ஃ நாப்சாக் சிக்கலின் உகந்த தீர்வு அதிகபட்சம் 1 ஆக இருந்தால், y சாத்தியமானது; அது 1 ஐ விட பெரியதாக இருந்தால், y ஐ விட சாத்தியமில்லை, மேலும் நாப்சாக் சிக்கலின் உகந்த தீர்வு கட்டுப்பாடு மீறப்பட்ட ஒரு உள்ளமைவை அடையாளம் காட்டுகிறது. மூன்றாவதாக, நாப்ஸாக் சிக்கலுக்கான தோராயமான தீர்வுடன், இரட்டை எல்பிக்கு ஒரு தோராயமான தீர்வைப் பெற முடியும் என்பதை அவர்கள் காட்டுகிறார்கள், இதிலிருந்து, முதன்மையான எல்பிக்கு தோராயமான தீர்வு கிடைக்கும்; கர்மார்கர்-கார்ப் பின் பேக்கிங் வழிமுறைகளைப் பார்க்கவும். மொத்தத்தில், எந்தவொரு சகிப்புத்தன்மை காரணிக்கும் h, அதிகபட்ச LOPT (I) + h இல் ஒரு அடிப்படை சாத்தியமான தீர்வைக் கண்டறிந்து, சரியான நேரத்தில் இயங்குகிறதுஃ, இதில் S என்பது வெவ்வேறு அளவுகளின் எண்ணிக்கை, n என்பது வெவ்வேறு பொருட்களின் எண்ணிக்கை, மற்றும் மிகச்சிறிய பொருளின் அளவு eB ஆகும். குறிப்பாக, e ±1/n மற்றும் h = 1 என்றால், வழிமுறை அதிகபட்சமாக LOPT + 1 தொட்டிகளுடன் ஒரு தீர்வைக் காண்கிறதுஃ இந்த வழிமுறையின் சீரற்ற மாறுபாடு எதிர்பார்க்கப்பட்ட நேரத்தில் இயங்குகிறதுஃ பின்ன எல்பி கர்மார்கர் மற்றும் கார்ப் ஆகியோர் பின்ன எல்பி-யை ஒருங்கிணைந்த எல்பி-க்கு தோராயமான தீர்வாக சுற்றுவதற்கான வழியை மேலும் உருவாக்கினர்; கர்மார்கர்-கார்ப் பின் பேக்கிங் வழிமுறைகளைப் பார்க்கவும். இந்த LP இன் சேர்க்கை ஒருங்கிணைப்பு இடைவெளி O (log2 (n)) இல் உள்ளது என்பதை அவற்றின் ஆதாரம் காட்டுகிறது. பின்னர், ஹோபர்க் மற்றும் ரோத்வாஸ் ஆகியோர் தங்கள் முடிவை மேம்படுத்தி, ஒருங்கிணைப்பு இடைவெளி O (log (n)) இல் இருப்பதை நிரூபித்தனர். ஒருங்கிணைப்பு இடைவெளியில் நன்கு அறியப்பட்ட கீழ் வரம்பு ஒரு மாறிலி ω (1) ஆகும். சரியான ஒருங்கிணைப்பு இடைவெளியைக் கண்டறிவது ஒரு திறந்த பிரச்சினை. தொட்டி மூடுதலில் தொட்டி மூடுதல் சிக்கலில், வெவ்வேறு அளவுகளில் n உருப்படிகள் உள்ளன. பொருட்களை அதிகபட்ச எண்ணிக்கையிலான தொட்டிகளில் அடைப்பதே குறிக்கோள், அங்கு ஒவ்வொரு தொட்டியிலும் குறைந்தபட்சம் பி இருக்க வேண்டும். இந்த சிக்கலுக்கான ஒரு இயற்கையான உள்ளமைவு LP ஆக இருக்கலாம்ஃ குறைந்தபட்சம் B கூட்டுத்தொகையுடன் உருப்படிகளின் அனைத்து உள்ளமைவுகளையும் A குறிக்கிறது (ஒருவர் சேர்ப்பு-குறைந்தபட்ச உள்ளமைவுகளை மட்டுமே எடுக்க முடியும்). இந்த எல். பி. யின் சிக்கல் என்னவென்றால், தொட்டி மூடுதல் சிக்கலில், சிறிய பொருட்களைக் கையாள்வது சிக்கலானது, ஏனெனில் உகந்த தீர்வுக்கு சிறிய பொருட்கள் அவசியமாக இருக்கலாம். சிறிய உருப்படிகள் அனுமதிக்கப்பட்டால், கர்மார்கர் மற்றும் கார்ப் நுட்பத்திற்கு கூட உள்ளமைவுகளின் எண்ணிக்கை மிகப் பெரியதாக இருக்கலாம். சிரிக், ஜான்சன் மற்றும் கென்யன் ஆகியோர் ஒரு மாற்று எல்பி வழங்குகிறார்கள். முதலில், அவை சிறியவை என்று அழைக்கப்படும் பொருட்களின் தொகுப்பை வரையறுக்கின்றன. T என்பது அனைத்து சிறிய பொருட்களின் மொத்த அளவாக இருக்கட்டும். பின்னர், அவர்கள் கூட்டுத்தொகை <2 உடன் அனைத்து உள்ளமைவுகளையும் குறிக்கும் ஒரு மேட்ரிக்ஸ் A ஐ உருவாக்குகிறார்கள். பின்னர், அவர்கள் மேலே உள்ள எல். பி. யை ஒரு கூடுதல் தடையுடன் கருதுகிறார்கள்ஃ தொட்டிகளில் உள்ள "காலியாக உள்ள இடத்தை" சிறிய பொருட்களால் நிரப்ப முடியும் என்பதற்கு கூடுதல் கட்டுப்பாடு உத்தரவாதம் அளிக்கிறது. இந்த எல். பி. யின் இரட்டை மிகவும் சிக்கலானது மற்றும் ஒரு எளிய நாப்சாக்-சிக்கல் பிரிப்பு ஆரக்கிள் மூலம் தீர்க்க முடியாது. சிரிக், ஜான்சன் மற்றும் கென்யன் ஆகியோர் 1/எப்சிலானில் தோராயமாக நேர அதிவேகத்தில் தீர்க்க ஒரு வித்தியாசமான முறையை முன்வைக்கின்றனர். ஜான்சென் மற்றும் சோலிஸ்-ஓபா ஆகியோர் 1/எப்சிலனில் தோராயமாக நேர அதிவேகத்தில் தீர்க்க ஒரு மேம்பட்ட முறையை முன்வைக்கின்றனர். இயந்திர திட்டமிடுதலில் தொடர்பில்லாத-இயந்திரங்கள் திட்டமிடுதலின் சிக்கலில், சில வெவ்வேறு இயந்திரங்கள் உள்ளன, அவை சில வெவ்வேறு வேலைகளை செயலாக்க வேண்டும். இயந்திரம் i வேலை j ஐ செயலாக்கும்போது, அது நேரம் எடுக்கும் பை, ஜே. ஒரு இயந்திரத்தின் அதிகபட்ச நிறைவு நேரம் முடிந்தவரை சிறியதாக இருக்கும் வகையில் இயந்திரங்களுக்கு இடையில் வேலைகளைப் பிரிப்பதே குறிக்கோள். இந்த சிக்கலின் முடிவு பதிப்பு பின்வருமாறுஃ கொடுக்கப்பட்ட நேரம் T, அனைத்து இயந்திரங்களின் நிறைவு நேரமும் அதிகபட்சம் T ஆக இருக்கும் ஒரு பகிர்வு உள்ளதா? ஒவ்வொரு இயந்திரத்திற்கும் i, இயந்திரத்தால் அதிகபட்சம் T நேரத்தில் செயலாக்கக்கூடிய வேலைகளின் வரையறுக்கப்பட்ட பல துணைக்குழுக்கள் உள்ளன. அத்தகைய ஒவ்வொரு துணைக்குழுவும் இயந்திரத்திற்கான உள்ளமைவு என்று அழைக்கப்படுகிறது i. Ci (T) இயந்திரத்திற்கான அனைத்து உள்ளமைவுகளின் தொகுப்பு, கொடுக்கப்பட்ட நேரம் T. Ci (T) இல் உள்ள ஒவ்வொரு இயந்திரத்திற்கும் i மற்றும் உள்ளமைவு c க்கு, ஒரு மாறியை வரையறுக்கவும், இது இயந்திரத்தில் பயன்படுத்தப்படும் உண்மையான உள்ளமைவு i என்பது c மற்றும் 0 க்கு சமம். பின்னர், LP கட்டுப்பாடுகள் பின்வருமாறுஃ 1,., m இல் உள்ள ஒவ்வொரு இயந்திரத்திற்கும்; 1,., n இல் உள்ள ஒவ்வொரு வேலைக்கும்; ஒவ்வொரு i, j க்கும். பண்புகள் தொடர்பில்லாத இயந்திரங்கள் திட்டமிடலுக்கான உள்ளமைவு-LP இன் ஒருங்கிணைந்த இடைவெளி 2 ஆகும். மேலும் காண்கஃ உயர் பெருக்கம் தொட்டி பொதி குறிப்புகள் தொட்டி பொதி எண் பகிர்வு வேலை திட்டமிடல் நேரியல் நிரலாக்கம்