کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
1141705 957085 2008 17 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A generalization of the integer linear infeasibility problem
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات کنترل و بهینه سازی
پیش نمایش صفحه اول مقاله
A generalization of the integer linear infeasibility problem
چکیده انگلیسی

Does a given system of linear equations Ax=b have a non-negative integer solution? This is a fundamental question in many areas, such as operations research, number theory, and statistics. In terms of optimization, this is called an integer feasibility problem. A generalized integer feasibility problem   is to find b such that there does not exist a non-negative integral solution in the system with a given AA. One such problem is the well-known Frobenius problem  . In this paper we study the generalized integer feasibility problem and also the multi-dimensional Frobenius problem. To study a family of systems with no non-negative integer solution, we focus on a commutative semigroup generated by a finite subset of ZdZd and its saturation. An element in the difference between the semigroup and its saturation is called a “hole”. We show the necessary and sufficient conditions for the finiteness of the set of holes. Also we define fundamental holes and saturation points of a commutative semigroup. Then, we show the simultaneous finiteness of the set of holes, the set of non-saturation points, and the set of generators for saturation points. As examples we consider some three- and four-way contingency tables from statistics and apply our results to them. Then we discuss the time complexities of our algorithms.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 5, Issue 1, February 2008, Pages 36–52
نویسندگان
, ,