Mixed-Integer Linear Programming Formulations for the Software Clustering Problem

The clustering problem has an important application in software engineering, which usually deals with large software systems with complex structures. To facilitate the work of software maintainers, components of the system are divided into groups in such a way that the groups formed contain highly-interdependent modules and the independent modules are placed in different groups. The measure used to analyze the quality of the system partition is called Modularization Quality (MQ). Designers represent the software system as a graph where modules are represented by nodes and relationships between modules are represented by edges. This graph is referred in the literature as Module Dependency Graph (MDG). The Software Clustering Problem (SCP) consists in finding the partition of the MDG that maximizes the MQ. In this paper we present three new mathematical programming formulations for the SCP. Firstly, we formulate the SCP as a sum of linear fractional functions problem and then we apply two different linearization procedures to reformulate the problem as Mixed-Integer Linear Programming (MILP) problems. We discuss a preprocessing technique that reduces the size of the original problem and develop valid inequalities that have been shown to be very effective in tightening the formulations. We present numerical results that compare the formulations proposed and compare our results with the solutions obtained by the exhaustive algorithm supported by the freely available Bunch clustering tool, for benchmark problems.     

Solutions to the Constrained Flowshop Sequencing Problem

If the flowshop sequencing problem is constrained so that job profiles are maintained independently of other work on the shop, then a range of new problem solutions are possible. Using geometrical relationships between the cumulative process times, a slope matching method has been devised which generally provides better results than Palmer's method and Gupta's algorithm. Secondly, it has been possible to reformulate the flowshop sequencing problem in terms of the travelling salesman problem. This has enabled the performance of the slope matching, Palmer and Gupta methods to be compared against a non-heuristic solution. Finally, provided that expressing a job in terms of the slopes of the cumulative start and end times is satisfactory, this enables in n-job, M-machine flowshop to be converted into an equivalent n-job 2 machine flowshop to which the use of Johnson's method will provide optimal sequences.     

A Mixed-Integer Programming Model for Gas Purchase and Transportation

The natural gas supply chain involves three main agents: producers, transportation companies, and local distribution companies (LDCs). We present a MIP model that is the basis for a decision support system developed for a Chilean LDC. This model takes into account many of the complexities of the purchasing and transportation contracts to help optimize daily purchase and transportation decisions in the absence of local storage facilities. The model was solved to optimality within a reasonable time. We show how the model handles several contractual issues and give some insights for the case when demand scenarios are used to deal with uncertainty.     

On Analyses of the Solution to a Linear Programming Problem

Many complex problem situations in various contexts have been represented in recent years by the linear programming model. The simplex method can then be used to give the optimal values of the variables corresponding to a given set of values of the parameters. However, in many situations it is useful to have the solution to many other related problems which differ from the original problem only in the values of some of the parameters. This paper presents procedures by which the solutions to the changed problems can be derived from the simplex solution tableau corresponding to the original problem. The method will be illustrated by means of an example problem, and it will be shown how quantitative information obtained from such analyses can aid management in decision making.     

On Linear Fractional Programming Problem and its Computation Using a Neural Network Model

In this paper we consider linear fractional programming problem and look at its linear complementarity formulation. In the literature, uniqueness of solution of a linear fractional programming problem is characterized through strong quasiconvexity. We present another characterization of uniqueness through complementarity approach and show that the solution set of a fractional programming problem is convex. Finally we formulate the complementarity condition as a set of dynamical equations and prove certain results involving the neural network model. A computational experience is also reported.      

有整数限制的运输问题

经典的运输问题是一个线性规划模型。本文讨论了把产地运输到销地的物资数量限制为非负整数时的运输问题,从理论上证明了这种有整数限制的运输问题模型可以转化为相应的线性规划模型来求解,有效地降低了计算难度。     

Scheduling of a Constellation of Satellites: Creating a Mixed-Integer Linear Model

Journal of Optimization Theory and Applications - The purpose of this paper is to provide a new scheduling model of a large constellation of imaging satellites that does not use a heuristic solving...     

Adaptive Control Model and Algorithms for the Dynamic Flowshop Scheduling Problem

1.IntroductionProductionschedulingcanbedefinedgenerallyastheallocationoftheresourcesinaproductionsystemovertimetoperformtheoperationsneededtotransformrawmaterialsilltoproducts.Aneffectiveandefficientschedulingsystemisnecessarytowellachievethepotentialsofaproductionfacility.Productionschedulingproblemsareextremelycomplex.Thecomplexityismainlyduetothefollowingtwofeaturesoftheproblem(Liu,1995).InterconnectedDecisions:Thecomponentsofaproductionsystem,e.g.,machines,ma-tenalhandlingdevicesandstora…     

混合整数规划的精确罚函数

本文讨论了混合整数规划的精确罚函数，并给出了原规划的解和其相应的罚问题解的等价性的几个充分条件。此外，我们提出了线性混合整数规划情况下相应的K－K－T条件。     

Classical Cuts for Mixed-Integer Programming and Branch-and-Cut

We review classical valid linear inequalities for mixed-integer programming, i.e., Gomory's fractional and mixed-integer cuts, and discuss their use in branch-and-cut. In particular, a generalization of the recent mixed-integer rounding (MIR) inequality and a sufficient condition for the global validity of classical cuts after branching has occurred are derived. Work supported in part by a grant from the Office of Naval Research (N00014-96-0327). Reprinted from Math. Meth. Oper. Res. (2001) 53, 173–203.     

Bounds for an Optimization Problem with a Linear Programming Structure

The problem of estimating the value of a quadratic cost indexminimized with respect to a linear system constraint arisesin many design studies in control theory and regression analysis.In particular, the assessment of several choices of system inputscould lead to inefficient procedures based on the executionof an optimization routine for each input subset. To avoid suchpitfalls, a set of bounds on the optimal cost have been constructedusing information resident in a set of system moments. The momentsare easily calculated for systems in weighting function formand the bounds obtained from explicit formulae. The derivationof these bounds is presented in some detail using Hilbert spaceanalysis to obtain a canonical form, and randomized solutionsto give the subsequent bound formulae. A simple example is presentedto illustrate the results.     

Primal Newton Method for the Linear Cone Programming Problem

A linear cone programming problem containing among the constraints a second-order cone is considered. For solving this problem, a primal Newton method which is constructed with the help of the optimality conditions is proposed. Local convergence of this method is proven.     

Improved Linear Programming Formulations for the Multi-group Discriminant Problem

This paper sets out to solve the multi (more than two)-group classification problem, and develops a new linear programming model which simultaneously determines the cut-off values for the different classification functions. Instead of decomposing the content in the multi-group problem to facilitate computation of the cut-off values, this new model aggregates information contained in the multi-group problem which, intuitively, should provide better estimates of the group boundaries. Furthermore, this new model, one existing LP model, and a statistical approach will be tested by using real-life data.     

求解二层线性规划问题的一种算法

对下层含有约束的二层线性规划问题,提出了求全局最优解的一种算法.首先由该算法求出约束凸集的全部极点,再对极点进行可行性检验,从而得到了二层线性规划问题的全局最优解,最后以实例验证了算法的有效性.     

解决医院病床安排问题的线性规划方法

本文研究了医院病床安排问题,在综合考虑病人等待入院和等待手术期间产生费用的前提下,建立了病床安排问题的线性规划模型。利用该模型,可以得到使病人平均等待费用最低的入院顺序。通过实例计算显示,利用本文模型得到的结果与利用传统的先到先服务原则安排的结果相比,病人等待手术的平均时间大约缩短了50%,等待费用大约降低了50%。     

线性分式规划问题的最优性条件

本文讨论了线性分式规划问题ｍｉｎ以及它的最优性条件．证明了它的局布最优解一定是整体最优解，并且局布最优解正定在约束条件的基本可行解处达到．     

A Branch-and-Bound Approach for a Two-machine Flowshop Scheduling Problem

In this paper, we present a branch-and-bound approach for solving a two-machine flow shop scheduling problem, in which the objective is to minimize a weighted combination of job flowtime and schedule makespan. Experimental results show that the algorithm works very well for certain special cases and moderately well for others. In fact, it is able to produce optimal schedules for 500-job problems in which the second machine dominates the first machine. It is also shown that the algorithm developed to provide an upper bound for the branch-and-bound is optimal when processing times for jobs are the same on both machines. The primary reason for developing the branch-and-bound approach is that its results can be used to guide other heuristic techniques, such as simulated annealing, tabu search and genetic algorithms, in their search for optimal solutions for larger problems.     

基金最佳使用计划的线性规划模型

给出了基金存款策略的线性规划模型 .对基金 M使用 n年的情形 ,只需比较银行存款税后年利率 ,初步确定 n年内的一切可能有的基金存款方式及其到期本利率 ,通过基金流转分析 ,即可建立以最大奖金数为目标的线性规划模型 ( LP1 ) n;问题二则需先分析 n年内一切可行的存款和购国库卷的组合方式及其到期的最佳本利率 ,然后调整模型 ( LP1 ) .中有关的系数 ,即可得到模型 ( LP2 ) n,调整模型 ( LP1 ) n与 ( LP2 ) n中第三年的奖金 y的系数 ,即可得到问题三的线性规划模型 .本文用 SAS/OR软件求解上述模型 ,得到在 n=1 0 ,M=5 0 0 0的情形下 ,使每年奖金数为最大的各种问题的基金的最佳使用策略 .