整数线性规划的一种新的割平面法

本文提出了一种新的求解整数线性规划的割平面思路 .它利用目标函数等值面的移动来切割与(IL P)相应的 (SL P)可行域的“无用”部分 ,再通过扩大与 (SL P)最优基相应的非基变量的取值来压缩 (SL P)的可行域 ,由此求得整数线性规划的最优解 .     

用调整优值法求最优整数解

“线性规划问题”的最优整数解是《简单的线性规划》一节中的一个难点 .现以教科书 (试验本 )第二册 (上 )第 6 5页习题 7.4的第四题为例说明如何用调整优值法来求“线性规划问题”的最优整数解 .(题目略 )本题的线性约束条件为1 8ｘ + 1 5 ｙ≤ 1 80 ,1 0 0 0ｘ + 6 0 0 ｙ≤ 80 0 0 ,ｘ∈Ｎ ,ｙ∈Ｎ , 6ｘ + 5 ｙ≤ 6 0 ,5ｘ + 3ｙ≤ 40 ,ｘ∈Ｎ ,ｙ∈Ｎ .线性目标函数为ｚ =2 0 0ｘ + 1 5 0 ｙ ,其中ｘ、ｙ分别表示大、小房间的间数 .作出可行域如图 1 .图 1为求ｚ的最大值 ,先将目标函数化为ｙ =-43ｘ + ｚ1 5 0 ,易知当该直线ｌ在ｙ轴…     

线性规划标准型和整数线性规划最优解的两个注记

本文研究线性规划标准型的基本假设所蕴含的一些性质,并探讨整数线性规划最优解和其松弛问题最优解的关系.首先,分别讨论四种情形下线性规划最优解的性质,即无约束线性规划问题、仅有非负约束的线性规划问题、仅有等式约束的线性规划问题,以及标准线性规划问题系数矩阵的列向量有为零的情形等.然后,构造两族二维整数线性规划,其松弛问题的最优解与其(整数)最优解"相距甚远".     

凸整数规划最优点的判定条件

本文得到判别已知可行整值点为凸整数规划最优解的一个充分条件,此条件只涉及目标函数在该整值点为中心的边长为2的超立方体上的性态.     

求整数最优解的方法

在“线性规划”教材中,求目标函数的最优 解,是通过平移直线的方法得出的,但平移直 线得出的最优解往往不是整数,而在实际的线 性规划问题中,经常要求的最优解是整数．人 教版《数学》第二册(上)63页例4在解答过程 中给出了求整数最优解的概念和答案,但没有 给出详细求法及理由,因此多数学生对此类问 题的求解感到无从下手．本文通过一道例题介 绍五种求整数最优解的方法及详细解答过程, 供大家参考．     

对整数线性规划问题求解方法的探究

<正>高中数学必修五(人民教育出版社2007年第三版)曾提出了整数线性规划问题,如第89—91页的例6和例7,例6是一个目标函数最小化问题,例7是一个目标函数最大化问题[1].关于如何较为方便、快捷且准确地找到整数最优解,教材对此并没有讨论和解答,需要加以补充说明.     

求解一个整数方程的新解法

ni=1aixi =p是一个由实验数据问题抽象而出的整数方程求非负整数解的数学模型 .为了使该问题实现计算机求解的可能 ,本文首先将原问题转化为讨论一类整数规划最优解问题 .从对应松弛规划问题的目标函数值为 0的最优解出发 ,根据舍入凑整法原则 ,再次将问题转化为另一简化后的整数方程 ,这样大大缩小了解的范围 ,及进一步迅速降低了方程右端的 p值 ,使其在计算机上求解的运算量大大降低而能得以实现     

缩小可行域求线性规划的整数最优解

新教材中添加了"简单的线性规划"一节.在求最优解的问题中,如果所求的不是整数最优解,通过平移直线的方法得出最优解,学生能够理解,也容易掌握.但如果要求整数最优解,讲解的时候利用多媒体演示学生也能理解,但在学生做作业的时候就出现了问题,学生不知从何下手.如果同样利用平移的方法,由于此时的可行域为不连续的点,很难得到最优解.这时我们可以采用缩小可行域的方法解决求整数最优解的问题.     

关于存在多组最优解的整数线性规划问题的割平面法的研究

利用割平面法求解具有多组最优解情形的整数线性规划问题时,会出现不能求出全部最优解的现象,这是割平面法的一个缺陷.针对割平面法的这种缺陷,基于构造非线性标量化函数时引入凸锥的思想,提出了一种割平面一线性交叉搜索方法,这种割平面一线性交叉搜索方法可以解决利用割平面法求解整数线性规划问题时出现的缺陷.最后,通过数值例验证了割平面一线性交叉搜索方法的可行性与有效性.     

广义几何规划的全局优化算法

对许多工程设计中常用的广义几何规划问题(GGP)提出一种确定性全局优化算法,该算法利用目标和约束函数的线性下界估计,建立GGP的松弛线性规划(RLP),从而将原来非凸问题(GGP)的求解过程转化为求解一系列线性规划问题(RLP).通过可行域的连续细分以及一系列线性规划的解,提出的分枝定界算法收敛到GGP的全局最优解,且数值例子表明了算法的可行性.     

Enhanced-interval linear programming

An enhanced-interval linear programming (EILP) model and its solution algorithm have been developed that incorporate enhanced-interval uncertainty (e.g., A^±, B^± and C^±) in a linear optimization framework. As a new extension of linear programming, the EILP model has the following advantages. Its solution space is absolutely feasible compared to that of interval linear programming (ILP), which helps to achieve insight into the expected-value-oriented trade-off between system benefits and risks of constraint violations. The degree of uncertainty of its enhanced-interval objective function (EIOF) would be lower than that of ILP model when the solution space is absolutely feasible, and the EIOF’s expected value could be used as a criterion for generating the appropriate alternatives, which help decision-makers obtain non-extreme decisions. Moreover, because it can be decomposed into two submodels, EILP’s computational requirement is lower than that of stochastic and fuzzy LP models. The results of a numeric example further indicated the feasibility and effectiveness of EILP model. In addition, EI nonlinear programming models, hybrid stochastic or fuzzy EILP models as well as risk-based trade-off analysis for EI uncertainty within decision process can be further developed to improve its applicability.     

An objective hyperplane search procedure for solving the general all-integer linear programming (ILP) problem

We describe an objective hyperplane search method for solving a class of integer linear programming (ILP) problems. We formulate the search as a bounded knapsack problem and develop requisite theory for formulating knapsack problems with composite constraints and composite objective functions that facilitate convergence to an ILP solution. A heuristic solution algorithm was developed and used to solve a variety of test problems found in the literature. The method obtains optimal or near-optimal solutions in acceptable ranges of computational effort.     

Discrete right hand side parametrization for linear integer programs

A procedure is presented which allows for discrete parametric analysis of the right hand side of an integer linear programming problem (ILP). The ILP must be solved using Gomor cuts, and certain information about these cuts must be saved. When the right hand side of the ILP is shifted, these cuts shift too. The corresponding shifts can be computed without performing additional cuts or pivots. These shifts are used to calculate a new solution which, if feasible is optimal. If the solution is not optimal, additional cuts may be required. The procedure is illustrated with example.     

Finding multiple solutions to general integer linear programs

Integer linear programming (ILP) problems occur frequently in many applications. In practice, alternative optima are useful since they allow the decision maker to choose from multiple solutions without experiencing any deterioration in the objective function. This study proposes a general integer cut to exclude the previous solution and presents an algorithm to identify all alternative optimal solutions of an ILP problem. Numerical examples in real applications are presented to demonstrate the usefulness of the proposed method.     

A column generation approach to train timetabling on a corridor

We propose heuristic and exact algorithms for the (periodic and non-periodic) train timetabling problem on a corridor that are based on the solution of the LP relaxation of an ILP formulation in which each variable corresponds to a full timetable for a train. This is in contrast with previous approaches to the same problem, which were based on ILP formulations in which each variable is associated with a departure and/or arrival of a train at a specific station in a specific time instant, whose LP relaxation is too expensive to be solved exactly. Experimental results on real-world instances of the problem show that the proposed approach is capable of producing heuristic solutions of better quality than those obtained by these previous approaches, and of solving some small-size instances to proven optimality.      

Optimal techniques for class-dependent attribute discretization

Preprocessing of raw data has been shown to improve performance of knowledge discovery processes. Discretization of quantitative attributes is a key component of preprocessing and has the potential to greatly impact the efficiency of the process and the quality of its outcomes. In attribute discretization, the value domain of an attribute is partitioned into a finite set of intervals so that the attribute can be described using a small number of discrete representations. Discretization therefore involves two decisions, on the number of intervals and the placement of interval boundaries. Previous approaches for quantitative attribute discretization have used heuristic algorithms to identify partitions of the attribute value domain. Therefore, these approaches cannot be guaranteed to provide the optimal solution for the given discretization criterion and number of intervals. In this paper, we use linear programming (LP) methods to formulate the attribute discretization problem. The LP formulation allows the discretization criterion and the number of intervals to be integral considerations of the problem. We conduct experiments and identify optimal solutions for various discretization criteria and numbers of intervals.     

Cyclic scheduling via integer programs with circular ones

A fundamental problem of cyclic staffing is to size and schedule a minimum-cost workforce so that sufficient workers are on duty during each time period. This may be modeled as an integer linear program with a cyclically structured 0-1 constraint matrix. We identify a large class of such problems for which special structure permits the ILP to be solved parametrically as a bounded series of network flow problems. Moreover, an alternative solution technique is shown in which the continuous-valued LP is solved and the result rounded in a special way to yield an optimum solution to the ILP.     

An integer linear programming approach for a class of bilinear integer programs

We propose an Integer Linear Programming (ILP) approach for solving integer programs with bilinear objectives and linear constraints. Our approach is based on finding upper and lower bounds for the integer ensembles in the bilinear objective function, and using the bounds to obtain a tight ILP reformulation of the original problem, which can then be solved efficiently. Numerical experiments suggest that the proposed approach outperforms a latest iterative ILP approach, with notable reductions in the average solution time.     

Numerical solutions comparison for interval linear programming problems based on coverage and validity rates

In this paper, two-step method (TSM), alternative solution method (SOM-2) and best-worst case (BWC) method are introduced to solve a type of interval linear programming (ILP) problem. To compare the performance of the methods, Monte Carlo simulation is also used to solve the same ILP problem, whose solutions are assumed to be real solutions. In the comparison, two scenarios corresponding with two assumptions of distribution functions are considered: (i) all the input parameters obey normal distribution; (ii) all the input parameters obey uniform distribution. Based on the simulation results, coverage rate (CR) and validity rate (VR) are proposed as new indicators to measure the quality of the numerical solutions obtained from the methods. Results from a numerical case study indicate that the TSM and SOM-2 solutions can cover the majority of valid values (CR > 50%, VR > 50%), compared to the conventional BWC method. In addition, from the point of CR, TSM is more applicable since the solutions of TSM can identify more feasible solutions. However, from the point of VR, SOM-2 is preferred since it can exclude more baseless solutions (this means more feasible solutions are contained in the SOM-2 solutions). In general, TSM would be preferred when only the range of the system objective needs to be determined, while SOM-2 would be much useful in identifying the effective values of the objective.