การสร้างคอลัมน์หรือการสร้างคอลัมน์แบบหน่วงเวลาเป็นอัลกอริทึมที่มีประสิทธิภาพสำหรับการแก้ปัญหาโปรแกรมเชิงเส้นขนาด ใหญ่ ^{[ 1 ]}

แนวคิดหลักคือ โปรแกรมเชิงเส้นจำนวนมากมีขนาดใหญ่เกินกว่าที่จะพิจารณาตัวแปรทั้งหมดอย่างชัดเจน ดังนั้นจึงเริ่มต้นด้วยการแก้โปรแกรมที่พิจารณาโดยใช้เพียงตัวแปรย่อย จากนั้นจึงเพิ่มตัวแปรที่มีศักยภาพในการปรับปรุงฟังก์ชันเป้าหมายเข้าไปในโปรแกรมทีละขั้นตอน เมื่อสามารถแสดงให้เห็นได้ว่าการเพิ่มตัวแปรใหม่จะไม่ปรับปรุงค่าของฟังก์ชันเป้าหมายอีกต่อไป กระบวนการก็จะหยุดลง ความหวังในการใช้อัลกอริธึมการสร้างคอลัมน์คือ จะมีการสร้างตัวแปรเพียงส่วนน้อยมากเท่านั้น ความหวังนี้ได้รับการสนับสนุนจากข้อเท็จจริงที่ว่า ในคำตอบที่เหมาะสมที่สุดตัวแปรส่วนใหญ่จะไม่ใช่ตัวแปรพื้นฐานและมีค่าเป็นศูนย์ ดังนั้นจึงสามารถหาคำตอบที่เหมาะสมที่สุดได้โดยไม่ต้องใช้ตัวแปรเหล่านั้น

ในหลายกรณี วิธีนี้ช่วยให้สามารถแก้ปัญหาโปรแกรมเชิงเส้นขนาดใหญ่ที่ยากต่อการแก้ไขได้ด้วยวิธีอื่น ตัวอย่างคลาสสิกของปัญหาที่ใช้วิธีนี้ได้อย่างประสบความสำเร็จคือปัญหาการตัดสต็อกเทคนิคเฉพาะอย่างหนึ่งในโปรแกรมเชิงเส้นที่ใช้วิธีการนี้คือ อัลกอริทึม การแยกส่วน Dantzig–Wolfeนอกจากนี้ การสร้างคอลัมน์ยังถูกนำไปใช้กับปัญหาต่างๆ มากมาย เช่นการจัดตารางเวลาลูกเรือการกำหนดเส้นทางยานพาหนะและ ปัญหา p-median ที่ มีขีดจำกัดความจุ

อัลกอริทึมนี้พิจารณาสองปัญหา ได้แก่ ปัญหาหลักและปัญหาย่อย ปัญหาหลักคือปัญหาเดิมที่มีตัวแปรเพียงบางส่วนเท่านั้นที่ถูกนำมาพิจารณา ส่วนปัญหาย่อยคือปัญหาใหม่ที่สร้างขึ้นเพื่อระบุตัวแปรที่ช่วยปรับปรุง ( กล่าวคือตัวแปรที่สามารถปรับปรุงฟังก์ชันเป้าหมายของปัญหาหลักได้)

จากนั้นอัลกอริทึมจะดำเนินการดังต่อไปนี้:

1. เริ่มต้นปัญหาหลักและปัญหาย่อย
2. แก้ปัญหาหลัก
3. ค้นหาตัวแปรปรับปรุงในปัญหาย่อย
4. หากพบตัวแปรที่ช่วยปรับปรุงผลลัพธ์ ให้เพิ่มตัวแปรนั้นลงในปัญหาหลัก แล้วไปที่ขั้นตอนที่ 2
5. มิเช่นนั้น: วิธีแก้ปัญหาหลักนั้นเหมาะสมที่สุดแล้ว หยุดการทำงาน

ส่วนที่ยากที่สุดของกระบวนการนี้คือการหาตัวแปรที่สามารถปรับปรุงฟังก์ชันเป้าหมายของปัญหาหลักได้ ซึ่งสามารถทำได้โดยการหาตัวแปรที่มีต้นทุนลดลง ติดลบมากที่สุด (โดยสมมติโดยไม่เสียความเป็นทั่วไปว่าปัญหาคือปัญหาการหาค่าต่ำสุด) หากไม่มีตัวแปรใดมีต้นทุนลดลงติดลบ แสดงว่าคำตอบปัจจุบันของปัญหาหลักนั้นเหมาะสมที่สุดแล้ว

เมื่อจำนวนตัวแปรมีมาก การหาตัวแปรที่ทำให้ผลลัพธ์ดีขึ้นโดยการคำนวณต้นทุนที่ลดลงทั้งหมดและเลือกตัวแปรที่มีต้นทุนที่ลดลงเป็นลบนั้นเป็นไปไม่ได้ ดังนั้น แนวคิดคือการคำนวณเฉพาะตัวแปรที่มีต้นทุนที่ลดลงน้อยที่สุด ซึ่งสามารถทำได้โดยใช้ปัญหาการหาค่าเหมาะสมที่สุดที่เรียกว่าปัญหาย่อยด้านการกำหนดราคา ซึ่งขึ้นอยู่กับโครงสร้างของปัญหาดั้งเดิมอย่างมาก ฟังก์ชันเป้าหมายของปัญหาย่อยคือต้นทุนที่ลดลงของตัวแปรที่กำลังค้นหาเมื่อเทียบกับตัวแปรคู่ปัจจุบัน และข้อจำกัดกำหนดให้ตัวแปรต้องเป็นไปตามข้อจำกัดที่เกิดขึ้นตามธรรมชาติ วิธีการสร้างคอลัมน์มีประสิทธิภาพเป็นพิเศษเมื่อโครงสร้างนี้ทำให้สามารถแก้ปัญหาย่อยด้วยอัลกอริทึมที่มีประสิทธิภาพ ซึ่งโดยทั่วไปคืออัลกอริทึมเชิง ผสมเฉพาะ ทาง

ต่อไปนี้เราจะอธิบายรายละเอียดเกี่ยวกับวิธีการและเหตุผลในการคำนวณต้นทุนที่ลดลงของตัวแปรต่างๆ พิจารณาโปรแกรมเชิงเส้นต่อไปนี้ในรูปแบบมาตรฐาน:

${\displaystyle {\begin{aligned}&\min _{x}c^{T}x\\&{\text{subject to}}\\&Ax=b\\&x\in \mathbb {R} ^{+}\end{aligned}}}$

ซึ่งเราจะเรียกว่าปัญหาหลัก (primal problem)รวมถึงโปรแกรมเชิงเส้นคู่ขนาน (dual linear program) ด้วย :

${\displaystyle {\begin{aligned}&\max _{u}u^{T}b\\&{\text{subject to}}\\&u^{T}A\leq c\\&u\in \mathbb {R} \end{aligned}}}$

นอกจากนี้ ให้และเป็นคำตอบที่เหมาะสมที่สุดสำหรับปัญหาทั้งสองนี้ ซึ่งสามารถหาได้จากตัวแก้เชิงเส้นใดๆ คำตอบเหล่านี้ตรวจสอบข้อจำกัดของโปรแกรมเชิงเส้น และโดยหลักการคู่ขนานจะมีค่าฟังก์ชันเป้าหมาย ( ) เท่ากัน ซึ่งเราจะเรียกว่าค่าที่เหมาะสมที่สุดนี้เป็นฟังก์ชันของสัมประสิทธิ์ต่างๆ ของปัญหาหลัก: โปรดทราบว่ามีตัวแปรคู่ขนานสำหรับแต่ละข้อจำกัดของแบบจำลองเชิงเส้นหลัก เป็นไปได้ที่จะแสดงให้เห็นว่าตัวแปรคู่ขนานที่เหมาะสมที่สุดสามารถตีความได้ว่าเป็นอนุพันธ์ย่อยของค่าที่เหมาะสมที่สุดของฟังก์ชันเป้าหมายเทียบกับสัมประสิทธิ์ของด้านขวามือของข้อจำกัด: หรือในทางกลับกัน กล่าว อย่างง่ายๆ คือบ่งชี้ว่าค่าที่เหมาะสมที่สุดของฟังก์ชันเป้าหมายเพิ่มขึ้นเท่าใดในบริเวณนั้น เมื่อสัมประสิทธิ์เพิ่มขึ้นหนึ่งหน่วย ${\displaystyle x^{*}}$${\displaystyle u^{*}}$${\displaystyle c^{T}x^{*}=u^{*T}b}$${\displaystyle z^{*}}$${\displaystyle z^{*}=z^{*}(c,A,b)}$${\displaystyle u_{i}^{*}}$${\displaystyle u_{i}^{*}}$${\displaystyle z^{*}}$${\displaystyle b_{i}}$${\displaystyle u_{i}^{*}={\frac {\partial z^{*}}{\partial b_{i}}}}$${\displaystyle u^{*}={\frac {\partial z^{*}}{\partial b}}}$${\displaystyle u_{i}^{*}}$${\displaystyle b_{i}}$

ลองพิจารณาดูว่าตัวแปรหนึ่งไม่ได้ถูกนำมาพิจารณาในปัญหาหลักจนถึงตอนนี้ โปรดทราบว่านี่เทียบเท่ากับการกล่าวว่าตัวแปรนั้นมีอยู่ในแบบจำลอง แต่มีค่าเป็นศูนย์ ต่อไปนี้เราจะสังเกตผลกระทบต่อปัญหาหลักของการเปลี่ยนค่าของจากเป็นถ้าและเป็นสัมประสิทธิ์ที่เกี่ยวข้องกับตัวแปรในฟังก์ชันเป้าหมายและในข้อจำกัดตามลำดับ โปรแกรมเชิงเส้นจะถูกแก้ไขดังนี้: ${\displaystyle y}$${\displaystyle y}$${\displaystyle y}$${\displaystyle 0}$${\displaystyle {\hat {y}}}$${\displaystyle c_{y}}$${\displaystyle A_{y}}$${\displaystyle y}$

${\displaystyle {\begin{aligned}&\min _{x}c^{T}x+c_{y}{\hat {y}}\\&{\text{subject to}}\\&Ax=b-A_{y}{\hat {y}}\\&x\in \mathbb {R} ^{+}\end{aligned}}}$

เพื่อให้ทราบว่าการเพิ่มตัวแปรเข้าไปในปัญหา ( กล่าวคือการให้ตัวแปรมีค่าไม่เป็นศูนย์) นั้นน่าสนใจหรือไม่ เราต้องการทราบว่าค่าของฟังก์ชันเป้าหมายของปัญหาใหม่นี้ลดลงหรือไม่เมื่อค่าของตัวแปรเพิ่มขึ้น กล่าวอีกนัยหนึ่ง เราต้องการทราบว่า เป็นอย่างไรในการทำเช่นนี้ โปรดสังเกตว่าสามารถแสดงได้ตามค่าของฟังก์ชันเป้าหมายของปัญหาหลักเริ่มต้น: จากนั้นเราสามารถคำนวณอนุพันธ์ที่เราสนใจได้: ${\displaystyle y}$${\displaystyle z_{\hat {y}}^{*}}$${\displaystyle {\hat {y}}}$${\displaystyle y}$${\displaystyle {\frac {\partial z_{\hat {y}}^{*}}{\partial {\hat {y}}}}}$${\displaystyle z_{\hat {y}}^{*}}$${\displaystyle z_{\hat {y}}^{*}=c_{y}{\hat {y}}+z^{*}(c,A,b-A_{y}{\hat {y}})}$

${\displaystyle {\begin{aligned}{\frac {\partial z_{\hat {y}}^{*}}{\partial {\hat {y}}}}&~=~&&c_{y}+{\frac {\partial z^{*}}{\partial {\hat {y}}}}\\&~=~&&c_{y}+{\frac {\partial z^{*}}{\partial c}}{\frac {dc}{d{\hat {y}}}}+{\frac {\partial z^{*}}{\partial A}}{\frac {dA}{d{\hat {y}}}}+{\frac {\partial z^{*}}{\partial b}}{\frac {db}{d{\hat {y}}}}\\&~=~&&c_{y}+{\frac {\partial z^{*}}{\partial b}}{\frac {db}{d{\hat {y}}}}\\&~=~&&c_{y}+u^{*}(-A_{y})\\&~=~&&c_{y}-u^{*}A_{y}\end{aligned}}}$

กล่าวอีกนัยหนึ่ง ผลกระทบของการเปลี่ยนแปลงค่าต่อค่าจะแปลออกมาเป็นสองส่วน ส่วนแรก การเปลี่ยนแปลงนี้ส่งผลกระทบโดยตรงต่อฟังก์ชันเป้าหมาย และส่วนที่สอง ด้านขวามือของข้อจำกัดจะถูกแก้ไข ซึ่งส่งผลกระทบต่อตัวแปรที่เหมาะสมที่สุด โดยขนาดของ ตัวแปรจะวัดโดยใช้ตัวแปรคู่ อนุพันธ์โดยทั่วไปเรียกว่าต้นทุนที่ลดลงของตัวแปรและจะใช้สัญลักษณ์ แทนในที่นี้ ${\displaystyle {\hat {y}}}$${\displaystyle z_{\hat {y}}^{*}}$${\displaystyle x^{*}}$${\displaystyle u^{*}}$${\displaystyle {\frac {\partial z_{\hat {y}}^{*}}{\partial {\hat {y}}}}}$${\displaystyle y}$${\displaystyle cr_{y}}$