2025-11-13T13:58:10.839999

Proximity results in convex mixed-integer programming

Kocuk, Ramirez

We study proximity (resp. integrality gap), that is, the distance (resp. difference) between the optimal solutions (resp. optimal values) of convex integer programs (IP) and the optimal solutions (resp. optimal values) of their continuous relaxations. We show that these values can be upper bounded in terms of the recession cone of the feasible region of the continuous relaxation when the recession cone is full-dimensional. If the recession cone is not full-dimensional we give sufficient conditions to obtain a finite integrality gap. We then specialize our analysis to second-order conic IPs. In the case the feasible region is defined by a single Lorentz cone constraint, we give upper bounds on proximity and integrality gap in terms of the data of the problem (the objective function vector, the matrix defining the conic constraint, the right-hand side, and the covering radius of a related lattice). We also give conditions for these bounds to be independent of the right-hand side, akin to the linear IP case. Finally, in the case the feasible region is defined by multiple Lorentz cone constraints, we show that, in general, we cannot give bounds that are independent of the corresponding right-hand side. Although our results are presented for the integer lattice $\mathbb{Z}^n$, the bounds can be easily adapted to work for any general lattice, including the usual mixed-integer lattice $\mathbb{Z}^{n_1}\times\mathbb{R}^{n_2}$, by considering the appropriate covering radius when needed.

academic

উত্তল মিশ্র-পূর্ণসংখ্যা প্রোগ্রামিংয়ে সান্নিধ্য ফলাফল

মৌলিক তথ্য

পেপার আইডি: 2501.00638
শিরোনাম: উত্তল মিশ্র-পূর্ণসংখ্যা প্রোগ্রামিংয়ে সান্নিধ্য ফলাফল
লেখক: বুরাক কোকুক (সাবানসি বিশ্ববিদ্যালয়), ডিয়েগো এ. মোরান আর. (রেনসেলার পলিটেকনিক ইনস্টিটিউট)
শ্রেণীবিভাগ: math.OC (অপ্টিমাইজেশন এবং নিয়ন্ত্রণ)
প্রকাশনার সময়: ২০২৪ সালের ৩১ ডিসেম্বর
পেপার লিঙ্ক: https://arxiv.org/abs/2501.00638

সারসংক্ষেপ

এই পেপারটি উত্তল পূর্ণসংখ্যা প্রোগ্রামিং (IP) এবং এর ক্রমাগত শিথিলকরণের মধ্যে সান্নিধ্য (proximity) এবং পূর্ণসংখ্যা ফাঁক (integrality gap) সমস্যা অধ্যয়ন করে। লেখকরা প্রমাণ করেছেন যে যখন ক্রমাগত শিথিলকরণ সম্ভাব্য অঞ্চলের recession cone সম্পূর্ণ মাত্রার হয়, তখন এই মানগুলি recession cone এর পরামিতি দ্বারা উপরের সীমা নির্ধারণ করা যায়। অ-সম্পূর্ণ মাত্রার recession cone এর ক্ষেত্রে, সীমিত পূর্ণসংখ্যা ফাঁক অর্জনের জন্য যথেষ্ট শর্ত প্রদান করা হয়েছে। নিবন্ধটি বিশেষভাবে দ্বিতীয় ক্রম শঙ্কু পূর্ণসংখ্যা প্রোগ্রামিং বিশ্লেষণ করে, একক Lorentz শঙ্কু সীমাবদ্ধতার ক্ষেত্রে, সমস্যা ডেটা দ্বারা সান্নিধ্য এবং পূর্ণসংখ্যা ফাঁকের উপরের সীমা প্রদান করে এবং এই সীমাগুলি ডান দিকের আইটেমের সাথে স্বাধীন হওয়ার শর্ত প্রদান করে।

গবেষণা পটভূমি এবং প্রেরণা

সমস্যা সংজ্ঞা এবং গুরুত্ব

মূল সমস্যা: উত্তল পূর্ণসংখ্যা প্রোগ্রামিং $\min\{\alpha^T x : x \in S \cap \mathbb{Z}^n\}$ এবং এর ক্রমাগত শিথিলকরণ $\min\{\alpha^T x : x \in S\}$ এর মধ্যে দূরত্ব সম্পর্ক অধ্যয়ন করা, যেখানে $S \subseteq \mathbb{R}^n$ একটি উত্তল সেট।
দুটি মূল ধারণা:
- সান্নিধ্য (Proximity): ক্রমাগত শিথিলকরণ সর্বোত্তম সমাধান থেকে নিকটতম পূর্ণসংখ্যা সম্ভাব্য সমাধানের দূরত্ব
- পূর্ণসংখ্যা ফাঁক (Integrality gap): পূর্ণসংখ্যা প্রোগ্রামিং সর্বোত্তম মান এবং ক্রমাগত শিথিলকরণ সর্বোত্তম মানের পার্থক্য
গবেষণার তাৎপর্য:
- শিথিলকরণ গুণমান পরিমাপ করা, অ্যালগরিদম ডিজাইনের জন্য তাত্ত্বিক ভিত্তি প্রদান করা
- উত্তল দ্বিতীয় ক্রম খেলা এবং অন্যান্য প্রয়োগে গুরুত্বপূর্ণ মূল্য রাখা
- রৈখিক পূর্ণসংখ্যা প্রোগ্রামিংয়ের ক্লাসিক ফলাফলগুলি অ-রৈখিক ক্ষেত্রে প্রসারিত করা

বিদ্যমান গবেষণার সীমাবদ্ধতা

রৈখিক ক্ষেত্রে সম্পূর্ণ ফলাফল রয়েছে: কুক এবং অন্যরা রৈখিক IP এর সান্নিধ্য সীমা ডান দিকের আইটেমের সাথে স্বাধীন প্রমাণ করেছেন
অ-রৈখিক ক্ষেত্রে সীমিত গবেষণা: শুধুমাত্র বিভাজ্য উত্তল ফাংশন বা বিভাজ্য দ্বিতীয় ক্রম ফাংশনের বিশেষ ক্ষেত্রে সীমাবদ্ধ
সাধারণ কাঠামোর অভাব: সাধারণ উত্তল সীমাবদ্ধতা সেট পরিচালনার জন্য সিস্টেমেটিক পদ্ধতির অভাব

মূল অবদান

সাধারণ উত্তল IP এর সান্নিধ্য ফলাফল: যখন recession cone সম্পূর্ণ মাত্রার হয়, সর্বোত্তম সমাধানের সাথে স্বাধীন সান্নিধ্য এবং পূর্ণসংখ্যা ফাঁক উপরের সীমা প্রদান করা
দ্বিতীয় ক্রম শঙ্কু IP এর বিশেষ বিশ্লেষণ: সাধারণ দ্বিতীয় ক্রম শঙ্কু সেটের জন্য কাঠামোগত ফলাফল এবং সান্নিধ্য সীমা প্রদান করা
ডান দিকের আইটেম নির্ভরতা বিশ্লেষণ: প্রমাণ করা যে বহু-Lorentz শঙ্কু সীমাবদ্ধতার ক্ষেত্রে, সীমা সাধারণত ডান দিকের আইটেমের সাথে স্বাধীন হতে পারে না
মিশ্র পূর্ণসংখ্যা জালক সাধারণীকরণ: ফলাফলগুলি সাধারণ জালক $\mathbb{Z}^{n_1} \times \mathbb{R}^{n_2}$ এ প্রসারিত করা যায়
প্রতিউদাহরণ নির্মাণ: নির্দিষ্ট উদাহরণের মাধ্যমে অ-রৈখিক ক্ষেত্রের জটিলতা প্রদর্শন করা

পদ্ধতির বিস্তারিত বর্ণনা

তাত্ত্বিক কাঠামো

১. সাধারণ উত্তল সেটের সান্নিধ্য বিশ্লেষণ

উপপাদ্য ২ (সম্পূর্ণ মাত্রার recession cone ক্ষেত্রে): $S$ একটি উত্তল সেট হোক, যার recession cone $K := \text{rec.cone}(S)$ নিয়মিত। $x̂ \in S$ এর জন্য, আমাদের আছে:

$\text{Prox}_{x̂}(S) := \min_{x \in S \cap \mathbb{Z}^n} \|x - x̂\|_2 \leq \frac{\sqrt{n}}{2}\left(\frac{1}{\Psi_{K,\|\cdot\|_2}} + 1\right)$

যেখানে $\Psi_{K,\|\cdot\|}$ শঙ্কু $K$ এর মূল পরামিতি:

$\Psi_{K,\|\cdot\|} := \max_{d \in K} \left\{\min_{f \in K^*} \{f^T d : \|f\|_* = 1\} : \|d\| = 1\right\}$

২. মিশ্র পূর্ণসংখ্যা জালকের আবরণ ব্যাসার্ধ

সংজ্ঞা ৪: সম্পূর্ণ মাত্রার মিশ্র পূর্ণসংখ্যা জালক $L(E,F) = \{Ez + Fy : z \in \mathbb{Z}^{n_1}, y \in \mathbb{R}^{n_2}\}$ এর আবরণ ব্যাসার্ধ:

$\mu(E,F) = \max_x \left\{\min_{x'} \{\|x - x'\|_2 : x' \in L(E,F)\} : x \in \mathbb{R}^n\right\}$

মূল বৈশিষ্ট্য (তথ্য ১): অর্থোগোনাল প্রতিনিধিত্বের জন্য, $\mu(E,F) = \mu(E)$ , অর্থাৎ আবরণ ব্যাসার্ধ শুধুমাত্র পূর্ণসংখ্যা উপাদানের উপর নির্ভর করে।

দ্বিতীয় ক্রম শঙ্কু প্রোগ্রামিংয়ের বিশেষ পদ্ধতি

১. দ্বিতীয় ক্রম সেটের কাঠামো বিশ্লেষণ

দ্বিতীয় ক্রম সেট $Q = \{x \in \mathbb{R}^n : x^T M x - 2\beta^T x + \gamma \leq 0\}$ এর জন্য, ম্যাট্রিক্স $M$ এর eigenvalue অনুযায়ী শ্রেণীবিভাগ:

উপবৃত্তাকার: $M \succ 0$
প্যারাবোলয়েড: $M \succeq 0$ , $\lambda_n = 0$
হাইপারবোলয়েড/স্থানান্তরিত শঙ্কু: $M$ এর নেতিবাচক eigenvalue রয়েছে

২. দুটি বিশ্লেষণ পদ্ধতি

পদ্ধতি ১: সান্নিধ্য চালিত

সীমানা বিন্দু $x̂$ দেওয়া, পূর্ণসংখ্যা বিন্দু ধারণকারী যথেষ্ট বড় উপবৃত্তাকার খুঁজে বের করা
অভ্যন্তরীণ অনুমান কৌশল এবং আবরণ ব্যাসার্ধ তত্ত্ব ব্যবহার করা

পদ্ধতি ২: পূর্ণসংখ্যা ফাঁক চালিত

স্তর সেট বিশ্লেষণের মাধ্যমে $S_\delta = \{x \in S : x_n = \delta\}$
যথেষ্ট বড় ব্যাসার্ধের উপবৃত্তাকার অংশ খুঁজে বের করা

প্রযুক্তিগত উদ্ভাবনী বিন্দু

শঙ্কু পরামিতি $\Psi_K$ এর গণনা: Lorentz শঙ্কুর জন্য, প্রমাণ করা হয়েছে যে $\Psi_{L^n,\|\cdot\|_2} = 1$
বড় গোলক অন্তর্ভুক্তি বৈশিষ্ট্য: প্রমাণ করা হয়েছে যে অসীম দ্বিতীয় ক্রম সেট যেকোনো বড় সম্পূর্ণ মাত্রার গোলক অন্তর্ভুক্ত করে
উপবৃত্তাকার অভ্যন্তরীণ অনুমান: দ্বিতীয় ক্রম সেটের উপবৃত্তাকার অভ্যন্তরীণ অনুমান নির্মাণ, সান্নিধ্য বিশ্লেষণের জন্য ব্যবহৃত

পরীক্ষামূলক সেটআপ

তাত্ত্বিক যাচাইকরণ উদাহরণ

উদাহরণ ৫ (প্যারাবোলয়েড ক্ষেত্রে)

দ্বিতীয় ক্রম শঙ্কু IP বিবেচনা করুন: $\inf_{x \in \mathbb{Z}^2} \left\{\alpha_1 x_1 + \alpha_2 x_2 : \left\|\begin{bmatrix} x_1 - b_1 \\ \frac{1}{2}x_2 - b_2 \end{bmatrix}\right\|_2 \leq \frac{1}{2}x_2 - d\right\}$

পরামিতি নির্বাচনের মাধ্যমে $\alpha = [1,1]^T$ , $b = [4N+\frac{1}{2}, 4N]^T$ , $d = 4N - \frac{1}{4N}$ , পূর্ণসংখ্যা ফাঁক পাওয়া যায়: $IG(N) = N + \frac{5}{16N} - \frac{1}{2}$

উদাহরণ ৬ (উপবৃত্তাকার এবং অর্ধ-স্থান ছেদ)

$\inf_{x \in \mathbb{Z}^2} \{x_2 : x_1^2 + x_2^2 \leq (N+1)^2, x_1 \geq \frac{1}{2}\}$

পূর্ণসংখ্যা ফাঁক $IG(N) = \sqrt{N + \frac{3}{4}}$ , ডান দিকের আইটেমের সাথে নির্ভরতা প্রদর্শন করে।

পরীক্ষামূলক ফলাফল

প্রধান তাত্ত্বিক ফলাফল

১. উপবৃত্তাকার ক্ষেত্রে (প্রস্তাব ৬)

উপবৃত্তাকার $S = \{x : \|Qx - p\|_2 \leq r\}$ এর জন্য: $\text{Prox}_{x̂}(S) \leq 2\|Q(Q^TQ)^{-1}\|_2 \mu(Q)$ $IG(S) \leq 2\|Q(Q^TQ)^{-1}\alpha\|_2 \mu(Q)$

২. প্যারাবোলয়েড ক্ষেত্রে (প্রস্তাব ৮)

$\text{Prox}_{x̂}(S) \leq \frac{\sqrt{n}}{2} + \Gamma_{x̂}\left(M, \beta, \gamma, \frac{\sqrt{n}}{2}\right)$

যেখানে $\Gamma$ অর্ধ-নির্ধারিত প্রোগ্রামিংয়ের মাধ্যমে সমাধান করা হয়।

३. পূর্ণসংখ্যা ফাঁক চালিত পদ্ধতির সীমা

উপবৃত্তাকার (প্রস্তাব ১३):

ক্ষেত্র ১: $IG(S) \leq \sqrt{\frac{q_1^2 - 4q_2q_0}{-q_2}} \leq 2\sqrt{\frac{\mu(\bar{Q})^2}{-q_2} + \frac{1}{4}}$
ক্ষেত্র २: $IG(S) \leq \frac{\mu(\bar{Q})}{\sqrt{-q_2}} + 1$

প্যারাবোলয়েড (প্রস্তাব १४): $IG(S) \leq \frac{\mu(\bar{Q})^2}{q_1} + 1$

সীমার তুলনা এবং কঠোরতা

উদাহরণ ८-९ বিভিন্ন পদ্ধতির প্রাপ্ত সীমা যাচাই করে:

ডান দিকের আইটেম সম্পর্কিত সীমা: প্রকৃত পূর্ণসংখ্যা ফাঁকের সাথে নিখুঁত মিল
ডান দিকের আইটেম স্বাধীন সীমা: অ্যাসিম্পটোটিক মিল, ব্যবহারিক উপরের সীমা অনুমান প্রদান করে

উপসংহার এবং আলোচনা

প্রধান উপসংহার

সম্পূর্ণ মাত্রার recession cone: সমস্যা ডেটার সাথে স্বাধীন সান্নিধ্য সীমা পাওয়া যায়
সাধারণ দ্বিতীয় ক্রম শঙ্কু সেট: নির্দিষ্ট শর্তে ডান দিকের আইটেমের সাথে স্বাধীন সীমা পাওয়া যায়
বহু-শঙ্কু সীমাবদ্ধতা: সাধারণ ক্ষেত্রে সীমা অবশ্যই ডান দিকের আইটেমের উপর নির্ভর করে
পদ্ধতিগত: দুটি পরিপূরক বিশ্লেষণ কাঠামো প্রদান করা

সীমাবদ্ধতা

গণনামূলক জটিলতা: নির্দিষ্ট সীমার গণনার জন্য অর্ধ-নির্ধারিত প্রোগ্রামিং সমাধান প্রয়োজন
কঠোরতা: কিছু সীমা যথেষ্ট কঠোর নাও হতে পারে, উন্নতির অবকাশ রয়েছে
প্রয়োগের পরিধি: প্রধানত দ্বিতীয় ক্রম শঙ্কু সীমাবদ্ধতার জন্য, অন্যান্য শঙ্কু প্রকারের জন্য আরও গবেষণা প্রয়োজন
ব্যবহারিক প্রয়োগ: তাত্ত্বিক ফলাফল থেকে ব্যবহারিক অ্যালগরিদমে রূপান্তর আরও কাজের প্রয়োজন

ভবিষ্যত দিকনির্দেশনা

অন্যান্য শঙ্কু প্রকার: অর্ধ-নির্ধারিত শঙ্কু, সূচকীয় শঙ্কু ইত্যাদিতে প্রসারিত করা
অ্যালগরিদম ডিজাইন: সান্নিধ্য ফলাফলের উপর ভিত্তি করে দক্ষ অ্যালগরিদম ডিজাইন করা
সীমার উন্নতি: আরও কঠোর সীমা খুঁজে বের করা, বিশেষত ধ্রুবক ফ্যাক্টরের উন্নতি
গণনামূলক পদ্ধতি: আবরণ ব্যাসার্ধ এবং শঙ্কু পরামিতি গণনার জন্য দক্ষ পদ্ধতি বিকাশ করা

গভীর মূল্যায়ন

সুবিধা

উল্লেখযোগ্য তাত্ত্বিক অবদান: উত্তল পূর্ণসংখ্যা প্রোগ্রামিংয়ের সান্নিধ্য সমস্যার প্রথম সিস্টেমেটিক বিশ্লেষণ
পদ্ধতিগত উদ্ভাবন: দুটি পরিপূরক বিশ্লেষণ কাঠামো প্রস্তাব করা
সম্পূর্ণ ফলাফল: একাধিক গুরুত্বপূর্ণ জ্যামিতিক বস্তু অন্তর্ভুক্ত করা (উপবৃত্তাকার, প্যারাবোলয়েড, হাইপারবোলয়েড)
প্রযুক্তিগত গভীরতা: উত্তল বিশ্লেষণ, জালক তত্ত্ব এবং শঙ্কু অপ্টিমাইজেশন দক্ষতার সাথে সমন্বয় করা
প্রতিউদাহরণ নির্মাণ: নির্দিষ্ট উদাহরণের মাধ্যমে অ-রৈখিক ক্ষেত্রের মূল অসুবিধা স্পষ্টভাবে প্রদর্শন করা

অসুবিধা

গণনামূলক সম্ভাব্যতা: কিছু ফলাফলের জন্য অর্ধ-নির্ধারিত প্রোগ্রামিং সমাধান প্রয়োজন, গণনা খরচ বেশি
সীমার কঠোরতা: নির্দিষ্ট ক্ষেত্রে সীমা অত্যন্ত রক্ষণশীল হতে পারে
ব্যবহারিকতা: তাত্ত্বিক ফলাফল এবং ব্যবহারিক অ্যালগরিদম ডিজাইনের মধ্যে বড় দূরত্ব
কভারেজ পরিধি: প্রধানত দ্বিতীয় ক্রম শঙ্কুতে ফোকাস, অন্যান্য গুরুত্বপূর্ণ শঙ্কু প্রকারের কভারেজ অপর্যাপ্ত

প্রভাব

তাত্ত্বিক প্রভাব: উত্তল পূর্ণসংখ্যা প্রোগ্রামিং তত্ত্বের জন্য গুরুত্বপূর্ণ ভিত্তি স্থাপন করা
পদ্ধতিগত মূল্য: বিশ্লেষণ কাঠামো অন্যান্য সমস্যায় সাধারণীকরণ করা যায়
ব্যবহারিক সম্ভাবনা: অ্যালগরিদম ডিজাইনের জন্য তাত্ত্বিক নির্দেশনা প্রদান করা
শৃঙ্খলা অতিক্রম: অপ্টিমাইজেশন তত্ত্ব, জ্যামিতি এবং সংখ্যা তত্ত্ব সংযুক্ত করা

প্রযোজ্য পরিস্থিতি

অ্যালগরিদম বিশ্লেষণ: হিউরিস্টিক অ্যালগরিদমের কর্মক্ষমতা সীমা মূল্যায়ন করা
সমস্যা মডেলিং: উত্তল পূর্ণসংখ্যা প্রোগ্রামিং মডেলিং পছন্দ নির্দেশনা দেওয়া
তাত্ত্বিক গবেষণা: আরও তাত্ত্বিক উন্নয়নের জন্য ভিত্তি প্রদান করা
প্রয়োগ ক্ষেত্র: ইনভেন্টরি ম্যানেজমেন্ট, বিদ্যুৎ ব্যবস্থা, প্রকৌশল ডিজাইন ইত্যাদি নির্দিষ্ট প্রয়োগ

তথ্যসূত্র

পেপারটি ২९টি গুরুত্বপূর্ণ তথ্যসূত্র উদ্ধৃত করে, প্রধানত অন্তর্ভুক্ত:

কুক, ডব্লিউ. এবং অন্যরা (१९८६) - রৈখিক IP সান্নিধ্যের ক্লাসিক ফলাফল
বেলোট্টি, পি. এবং অন্যরা (२०१३, २०१७) - দ্বিতীয় ক্রম পৃষ্ঠের বৈশিষ্ট্যকরণ তত্ত্ব
বেন-তাল, এ. এবং নেমিরোভস্কি, এ. (२००१) - আধুনিক উত্তল অপ্টিমাইজেশন তত্ত্ব
বার্টসিমাস, ডি. এবং ওয়াইসম্যান্টেল, আর. (२००५) - পূর্ণসংখ্যা অপ্টিমাইজেশন মৌলিক তত্ত্ব
পাট, জে. এবং অন্যরা (२०२०) - মিশ্র পূর্ণসংখ্যা প্রোগ্রামিংয়ের সাম্প্রতিক অগ্রগতি

এই পেপারটি উত্তল পূর্ণসংখ্যা প্রোগ্রামিংয়ের সান্নিধ্য বিশ্লেষণে গুরুত্বপূর্ণ তাত্ত্বিক অবদান করে, এই গুরুত্বপূর্ণ সমস্যার জন্য একটি সিস্টেমেটিক বিশ্লেষণ কাঠামো প্রদান করে এবং উচ্চ একাডেমিক মূল্য এবং সম্ভাব্য প্রয়োগ সম্ভাবনা রাখে।