Search

In this paper, we propose a method for linear programming with the property that, starting from an initial non-central point, it generates iterates that simultaneously get closer to optimality and closer to centrality. The iterates follow paths that in the limit are tangential to the central path. Together with the convergence analysis, we provide a general framework which enables us to analyze various primal-dual algorithms in the literature in a short and uniform way. [ABSTRACT FROM AUTHOR]

Mehrotra's predictor-corrector algorithm [3] is currently considered to be one of the most practically efficient interior-point methods for linear programming. Recently, Zhang and Zhang [18] studied the global convergence properties of the Mehrotra-type predictor-corrector approach and established polynomial complexity bounds for two interior-point algorithms that use the Mehrotra predictor-corrector approach. In this paper, we study the asymptotic convergence rate for the Mehrotra-type predictor-corrector interior-point algorithms. In particular, we construct an infeasible-interior-point algorithm based on the second algorithm proposed in [18] and show that while retaining a complexity bound of O(n1.5t)-iterations, under certain conditions the algorithm also possesses a Q-subquadratic convergence, i.e., a convergence of Q-order 2 with an unbounded Q-factor. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm for solving a linear program LP (to a given tolerance) from a given prespecified starting point. As such, the algorithm does not depend on any "big M" initialization assumption. The complexity of the algorithm is sensitive to and is dependent on the quality of the starting point, as assessed by suitable measures of the extent of infeasibility and the extent of nonoptimality of the starting point. Two new measures of the extent of infeasibility and of nonoptimality of a starting point are developed. We then present an algorithm for solving LP whose complexity depends explicitly and only on how close the starting point is to the set of LP feasible and optimal solutions (using these and other standard measures), and also on n (the number of inequalities). The complexity results using these measures of infeasibility and nonoptimality appear to be consistent with the observed practical sensitivity of interior-point algorithms to certain types of starting points. The starting point can be any pair of primal and dual vectors that may or may not be primal and/or dual feasible, and that satisfies a simple condition that typically arises in practice or is easy to coerce. [ABSTRACT FROM AUTHOR]

In this paper, we provide an easily satisfied relaxation condition for the primal-dual interior path-following algorithm to solve linear programming problems. It is shown that the relaxed algorithm preserves the property of polynomial-time convergence. The computational results obtained by implementing two versions of the relaxed algorithm with slight modifications clearly demonstrate the potential in reducing computational efforts. [ABSTRACT FROM AUTHOR]

Finding optimal decisions often involves the consideration of certain random or unknown parameters. A standard approach is to replace the random parameters by the expectations and to solve a deterministic mathematical program. A second approach is to consider possible future scenarios and the decision that would be best under each of these scenarios. The question then becomes how to choose among these alternatives. Both approaches may produce solutions that are far from optimal in the stochastic programming model that explicitly includes the random parameters. In this paper, we illustrate this advantage of a stochastic program model through two examples that are representative of the range of problems considered in stochastic programming. The paper focuses on the relative value of the stochastic program solution over a deterministic problem solution. [ABSTRACT FROM AUTHOR]

In this paper, we are concerned with an algorithm which combines the generalized linear programming technique proposed by Dantzig and Wolfe with the stochastic quasi-gradient method in order to solve stochastic programs with recourse. In this way, we overcome the difficulties arising in finding the exact values of the objective function of recourse problems by replacing them with the statistical estimates of the function. We present the basic steps of the proposed algorithm focusing our attention on its implementation alternatives aimed at improving both the convergence and computational performances. The main application areas are mentioned and some computational experience in the validation of our approach is reported. Finally, we discuss the possibilities of parallelization of the proposed algorithmic schemes. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of packing Steiner trees in a graph. This problem arises during the global routing phase of circuit layout design. We consider various integer programming formulations and rank them according to lower bounds they provide as LP-relaxations. We discuss a solution procedure to obtain both lower and upper bounds using one of the LP-relaxations. Computational results to test the effectiveness of our procedures are provided. [ABSTRACT FROM AUTHOR]

In this paper an algorithm is developed to generate all nondominated extreme points and edges of the set of objective values of a multiple objective linear program. The approach uses simplex tableaux but avoids generating unnecessary extreme points or bases of extreme points. The procedure is based on, and improves, an algorithm Dauer and Liu developed for this problem. Essential to this approach is the work of Gal and Kruse on the neighborhood problem of determining all extreme points of a convex polytope that are adjacent to a given (degenerate) extreme point of the set. The algorithm will incorporate Gal's degeneracy graph approach to the neighborhood problem with Dauer's objective space analysis of multiple objective linear programs. [ABSTRACT FROM AUTHOR]

This paper presents a two-stage multi-period decision model for allocation of the individual's savings into several investment plans. Although the U.S. economy is used as the background, the modelling methods are general enough to accommodate any tax law. The first stage of the model uses an asset-allocation method based on the single-index model. Because this method is static and does not provide for tax considerations and other constraints, it alone is not enough. The output of this optimal selection is used as exogenous parameters and controls for the second stage of the model which is an integer program. The IP includes fixed charges, statutory and budgetary constraints, a discount rate, and the risk level. We provide an example of this approach to illustrate how an individual can achieve his goals of terminal accumulations while maintaining the risk level, measured by the aggregate beta, he prefers. A linear programming relaxation of the IP model is utilized for sensitivity analysis to examine whether future adjustments in investment strategies are required. The model remains tractable enough for implementation by individuals who may not be experts in mathematical programming and financial planning. [ABSTRACT FROM AUTHOR]

In this paper, we discuss an SLCP algorithm for the solution of Bilevel Linear Programs (BLP) which consists of solving a sequence of Linear Complementarity Problems (LCP) by using a hybrid enumerative method. This latter algorithm incorporates a number of procedures that reduce substantially the search for a solution of the LCP or for showing that the LCP has no solution. Computational experience with the SLCP algorithm shows that it performs quite well for the solution of small- and medium-scale BLPs with sparse structure. Furthermore, the algorithm is shown to be more efficient than a branch-and-bound method for solving the same problems. [ABSTRACT FROM AUTHOR]

Three possible approaches to stochastic programming problems defined in time (so that they contain random processes) are described in this paper: (1) an application of the extremal theory of random processes; (2) an exponential penalty model approach related to scenario analysis; (3) a modification of the entropic penalty approach. Explicit results are derived for some special cases. [ABSTRACT FROM AUTHOR]

Economists have found a need to model agents who behave in ways that are not consistent with the traditional notions of rational behavior under uncertainty but that are oriented in some looser manner toward achieving ‘good’ outcomes. Adaptation over time in a myopic manner, rather that forward-looking optimization, has been proposed as one such model of behavior that displays bounded rationality. This paper investigates the relationship between adaptation as a model of behavior and as an algorithmic approach that has been used in computing solutions to optimization problems. It describes a specific adaptive model of behavior in discrete choice problems, one that is closely related to adaptive algorithms for optimization, and shows that this model can be fruitfully applied in studying several economic issues. [ABSTRACT FROM AUTHOR]

This paper presents a model for the optimization of productivity in a steel plant comprised of four arc furnaces and three continuous casting machines and subject to a global limitation on the power supplied to the furnaces. The furnaces produce in batch mode and require a given amount of energy at each fusion phase in a production cycle. The problem is lo define the starting time and duration of each phase for each production cycle, in combination with a power schedule which meets the energy requirements of the different furnaces and a global power supply limit for the whole plant, in order to minimize the due date of the last production cycle. This scheduling problem is formulated as a nonstandard optimization problem, combining an optimal control problem and a mathematical programming problem. A two-level algorithm is proposed, which yields a suboptimal solution through a sequence of linear programming problems. The optimality of solutions produced with the approach is established in the cases of one cycle and for steady-state operations. [ABSTRACT FROM AUTHOR]

In this paper, we present parallel bundle-based decomposition algorithms to solve a class of structured large-scale convex optimization problems. An example in this class of problems is the block-angular linear programming problem. By dualizing, we transform the original problem to an unconstrained nonsmooth concave optimization problem which is in turn solved by using a modified bundle method. Further, this dual problem consists of a collection of smaller independent subproblems which give rise to the parallel algorithms. We discuss the implementation on the CRYSTAL multi-computer. Finally, we present computational experience with block-angular linear programming problems and observe that more than 70% efficiency can be obtained using up to eleven processors for one group of test problems, and more than 60% efficiency can be obtained for relatively smaller problems using up to five processors for another group of problems. [ABSTRACT FROM AUTHOR]

This paper concerns the problem of locating a central facility on a connected network N. The network, N, could be representative of a transport system, while the central facility takes the form of a connected subgraph of N. The problem is to locate a central facility of minimum length so that each of several demand points on N is covered by the central facility a demand point at vi in N is covered by the central facility if the shortest path distance between vi and the closest point in the central facility does not exceed a parameter ri. This location problem is NP-hard, but for certain special cases, efficient solution methods are available. [ABSTRACT FROM AUTHOR]

This paper presents a parallelization of the simplex method for linear programming. Current implementations of the simplex method on sequential computers are based on a triangular factorization of the inverse of the current basis. An alternative decomposition designed for parallel computation, called the quadrant interlocking factorization, has previously been proposed for solving linear systems of equations. This research presents the theoretical justification and algorithms required to implement this new factorization in a simplex-based linear programming system. [ABSTRACT FROM AUTHOR]

In location-routing problems, the objective is to locate one or many depots within a set of sites (representing customer locations or cities) and to construct delivery routes from the selected depot or depots to the remaining sites at least system cost. The objective function is the sum of depot operating costs, vehicle acquisition costs and routing costs. This paper considers one such problem m which a weight is assigned to each site and where sites are to be visited by vehicles having a given capacity. The solution must be such that the sum of the weights of sites visited on any given route does not exceed the capacity of the visiting vehicle. The formulation of an integer linear program for this problem involves degree constraints generalized subtour elimination constraints, and chain baring constraints. An exact algorithm, using initial relaxation of most of the problem constraints, is presented which is capable of solving problems with up to twenty sites within a reasonable number of iterations. [ABSTRACT FROM AUTHOR]

In this paper, an interactive paired comparison simplex based method for multiple objective linear programming (MOLP) problems is developed and compared to other interactive MOLP methods. The decision maker (DM)'s utility function is assumed to be unknown, but is an additive function of his known linearized objective functions. A test for ‘utility efficiency’ for MOLP problems is developed to reduce the number of efficient extreme points generated and the number of questions posed to the DM. The notion of ‘strength of preference’ is developed for the assessment of the DM's unknown utility function where he can express his preference for a pair of extreme points as ‘strong’, ‘weak’, or ‘almost indifferent’. The problem of ‘inconsistency of the DM’ is formalized and its resolution is discussed. An example of the method and detailed computational results comparing it with other interactive MOLP methods are presented. Several performance measures for comparative evaluations of interactive multiple objective programming methods are also discussed. [ABSTRACT FROM AUTHOR]

In this paper, an algorithm is presented for the transshipment problem that is an adaption of the method used by Jones, Saigal, and Schneider for solving single-commodity, spatial-equilibrium problems. The approach uses a variable-dimension strategy in which a sequence of subproblems is formed by solving the problem ‘one-node-at-a-time’. The algorithm is tested on uncapacitated transportation problems. Although the computational results are not directly comparable to other methods (since the algorithm is implemented in C under UNIX), the results show that the method is very effective and may be competitive with the best available algorithms for linear network problems. [ABSTRACT FROM AUTHOR]

Linear programming is applied to measurement of whole life insurance to obtain a functional relationship between interest adjusted cost of insurance protection and rate of return on policy equity. For comparative purposes, policy differences related to premium rates, dividends and cash-values are controlled by maintaining identical insurance requirements and constant levels of wealth for the insured. Marginal discount factors, obtained from the dual variables for the wealth constraints, demonstrate the importance of policy holder wealth. The interest adjusted cost measure currently used by the insurance industry is shown to be a special case when the linear programming approach is used. The method used in this paper is sufficiently flexible to incorporate different patterns of time preference for insurance. Finally, it is demonstrated that the trade-off between interest adjusted cost of insurance and rate of return on policy equity is sensitive to the external rate of return. [ABSTRACT FROM AUTHOR]

In this paper we consider a certain aggregate production planning model. This model permits regular and overtime production and allows for backordering of goods for a number of periods. Although the discussed model can be formulated as a linear programming problem a special (noniterative) method is developed. First the optimal level of each mode of production is determined for each period. Then the complete solution is immediately constructed. This procedure is so simple that it can be also implemented via pencil and paper. Several computational improvements as well as problem variations are discussed. [ABSTRACT FROM AUTHOR]

Traditional sensitivity analysis of linear programming objective function coefficients concerns itself with variations in single parameters. In a recent book, Gal developed a theoretical framework to determine the effect of mutliple variations in the parameters. In this paper, we develop a methodology to implement and extend the theoretical results in the earlier work for interval variations of objective function coefficients. This methodology uses necessary and sufficient conditions to determine all optimal solutions to the linear programming problem for objective function coefficients within given intervals. The resulting procedure has been coded for computer use and tested on various types of test problems. Computational results and an example are presented. [ABSTRACT FROM AUTHOR]

Planning the allocation of scarce resources to competing activities over multiple time periods is one of the most important problems facing decision makers in modern organizations. Much of the previous research in this area has concentrated on the use of linear programming procedures and has assumed that the technology through which scarce resource inputs are transformed into competing activity outputs is fixed. A more realistic assumption in many situations is that certain technology coefficients are likely to vary over the planning horizon as a function of activity levels in previous periods. In this paper, a multiperiod resource allocation model with variable technology is formulated. Enriching a more traditional fixed technology model to include variable technology results in a nonlinear model which is more realistic, but is also more difficult to solve. A heuristic procedure that is both straightforward and intuitively appealing is developed for obtaining good feasible solutions to the variable technology model. The solution procedure requires little additional computational effort beyond solving the associated, less realistic fixed technology model. [ABSTRACT FROM AUTHOR]

Successive Linear Programming (SLP), which is also known as the Method of Approximation Programming, solves nonlinear optimization problems via a sequence of linear programs. This paper reports on promising computational results with SLP that contrast with the poor performance indicated by previously published comparative tests. The paper provides a detailed description of an efficient, reliable SLP algorithm along with a convergence theorem for linearly constrained problems and extensive computational results. It also discusses several alternative strategies for implementing SLP. The computational results show that SLP compares favorably with the Generalized Reduced Gradient Code GRG2 and with MINOS/GRG. It appears that SLP will be meat successful when applied to large problems with low degrees of freedom. [ABSTRACT FROM AUTHOR]

This paper presents a simplex-based solution procedure for the multiple objective linear fractional programming problem. By (1) departing slightly from the traditional notion of efficiency and (2) augmenting the feasible region as in goal programming, the solution procedure solves for all weakly efficient vertices of the augmented feasible region. The article discusses the difficulties that must be addressed in multiple objective linear fractional programming and motivates the solution algorithm that is developed. [ABSTRACT FROM AUTHOR]

A model for measuring the efficiency of Decision Making Units (= DMU's) is presented, along with related methods of implementation and interpretation. The term DMU is intended to emphasize an orientation toward managed entities in the public and/or not-for-profit sectors. The proposed approach is applicable to the multiple outputs and designated inputs which are common for such DMU's. A priori weights, or imputations of a market-price-value character are not required. A mathematical programming model applied to observational data provides a new way of obtaining empirical estimates of extremal relations -- such as the production functions and/or efficient production possibility surfaces that are a cornerstone of modern economics. The resulting extremal relations are used to envelop the observations in order to obtain the efficiency measures that form a focus of the present paper. An illustrative application utilizes data from Program Follow Through (= PFT). A large scale social experiment in public school education, it was designed to test the advantages of PFT relative to designated NFT (= Non-Follow Through) counterparts in various parts of the U.S. It is possible that the resulting observations are contaminated with inefficiencies due to the way DMU's were managed en route to assessing whether PFT (as a program) is superior to its NFT alternative. A further mathematical programming development is therefore undertaken to distinguish between "management efficiency" and "program efficiency." This is done via procedures referred to as Data Envelopment Analysis (= DEA) in which one first obtains boundaries or envelopes from the data for PFT and NFT, respectively. These boundaries provide a basis for estimating the relative efficiency of the DMU's operating under these programs. These DMU's are then adjusted up to their program boundaries, after which a new inter-program envelope is obtained for evaluating the PFT and NFT programs with the estimated managerial inefficiencies eliminated. The claimed superiority of PFT fails to be validated in this illustrative application. Our DEA approach, however, suggests the additional possibility of new approaches obtained from PFT-NFT combinations which may be superior to either of them alone. Validating such possibilities cannot be done only by statistical or other modelings. It requires recourse to field studies, including audits (e.g., of a U.S. General Accounting Office variety) and therefore ways in which the results of a DEA approach may be used to guide such further studies (or audits) are also indicated. [ABSTRACT FROM AUTHOR]

In a previous paper Kunreuther and Morton examined a single product production planning problem in which demand in each of a finite number of periods is known with certainty, and there are linear costs for holding inventory and for adjusting production levels between periods. This paper reexamines the problem, taking advantage of it being a linear program. In particular, the dual problem has considerable structure, and the patterns of variables in dual feasible solutions have interesting geometric properties that afford a great deal of intuition. The requirement of dual feasibility is a more formal approach to the "marginal cost balancing" notion of Kunreuther and Morton and provides some extension and strengthening of the earlier results. A proof with simplified logical structure for the Kunreuther-Morton planning horizon is indicated. Then a different kind of planning horizon result is given. These, in contrast to the K-M planning horizons, occur when future demands increase, such as at the bottom of a seasonal cycle. [ABSTRACT FROM AUTHOR]

More than twenty years after the publication of the Linear Decision Rule (LDR) of Holt, Modigliani, Muth, and Simon (HMMS), the LDR remains an implementation failure. No company is reported to be using it. This paper hypothesizes that the reason for this failure may be a very simple one: the incremental benefit of aggregate planning (i.e., the coordinated optimization of aggregate work force, production, and inventory) over improved aggregate inventory management alone may be quite small. To demonstrate our hypothesis we reexamine the original paint company cost comparisons presented by HMMS, and show that virtually all of the LDR' s reported saving over paint company management could have been obtained with a one time adjustment in management's aggregate buffer inventory level. We conclude that although the LDR might provide significantly larger savings than improved aggregate inventory management alone, published empirical results fail to demonstrate that potential. The implications of our hypothesis and conclusions are discussed. [ABSTRACT FROM AUTHOR]

This paper examines the performance of three heuristic methods (Senju-Toyoda, Kochenberger et al., and Hillier) when applied to the 0-1 linear programming problem with nonnegative coefficients. Their effectiveness, measured in terms of computing time, error and relative error, is evaluated on a set of problems from the literature and randomly generated 0-1 test problems with nonnegative coefficients. Analysis of variance and stepwise regressions are employed to study the effect of the number of variables, number of constraints and degree of constraint slackness. The methods exhibited some similarities but also marked differences in their behavior. Interestingly enough, the larger the number of variables the better the accuracy of each method. Error differences among the three methods were significant (1:0.8:0.2) yet small (less than 2% on the average) for many practical situations. Hillier's algorithm was the most accurate but much slower and more core demanding than the other two, which makes it difficult or impossible to use for solving large 0-1 problems. Kochenberger's et al. heuristic was the fastest (most accurate) of the three in tightly (loosely) constrained problems. In general the Senju-Toyoda algorithm was the fastest, but least accurate on small and medium size problems. Suggestions are made for selecting the "best" heuristic based on the problem characteristics. [ABSTRACT FROM AUTHOR]

The dilemma of when to cease analysis of a subproblem and go on to the next subproblem in convex programming is an especially difficult one. This paper views convex programming as an extension of linear programming and focuses attention on the analysis of a given subproblem. Specifically, if K = {x | Ax ≤ b} is bounded with a nonempty interior and represents a residual unsearched region in some convex programming algorithm, what is (are) the "best" trial point(s) which can be selected? The generalized slack variable linear program (GSVLP) provides a mechanism for implementing trial point selection based on many strategies. Several implications of the L[sub 2] norm are revealed which are especially important in constraint deletion and rate of reduction of the hypervolume of the residual search region K. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to take stock of what is known and to suggest some conceptual foundations for future progress in the areas of postoptimality analysis and parametric optimization techniques for integer programming. [ABSTRACT FROM AUTHOR]

In this paper a man-machine interactive mathematical programming method is presented for solving the multiple criteria problem involving a single decision maker. It is assumed that all decision-relevant criteria or objective functions are concave functions to be maximized, and that the constraint set is convex. The overall utility function is assumed to be unknown explicitly to the decision maker, but is assumed to be implicitly a linear function, and more generally a concave function of the objective functions. To solve a problem involving multiple objectives the decision maker is requested to provide answers to yes and no questions regarding certain trade offs that he likes or dislikes. Convergence of the method is proved; a numerical example is presented. Tests of the method as well as an extension of the method for solving integer linear programming problems are also described. [ABSTRACT FROM AUTHOR]

This paper formulates a general longitudinal manpower flow model and poses the problem of scheduling the inflow of manpower for an infinite number of periods subject to constraints on the stocks and inflows of manpower and the size of the manpower system. The objective is to minimize the present value of the costs of system operation. A finite linear program is introduced which can calculate a lower bound on the optimal value of the infinite problem. The optimal solution of the finite linear program can be used to construct a sound and easily implemented policy for the infinite problem. [ABSTRACT FROM AUTHOR]

There are numerous situations in management and elsewhere in which an individual decision maker chooses subsets of multiattributed items. The specification of a measure of goodness for selecting subsets may differ from one situation to the next. In this paper, a model is developed for evaluating subsets where the choice criterion is one of balance among the attributes of items in the subset chosen. A method for determining the parameters of the model from a small number of judgments on subsets using linear programming is discussed, The model is applied to the problem of evaluating subsets of television shows and of choosing the most balanced subset of shows. Several extensions of the model and potential applications are also given. [ABSTRACT FROM AUTHOR]

A variety of combinatorial problems (e.g., in capital budgeting, scheduling, allocation) can be expressed as a linear integer programming problem. However, the standard devices for doing this often produce an inordinate number of variables and constraints, putting the problem beyond the practical reach of available integer programming methods. This paper presents new formulation techniques for capturing the essential nonlinearities of the problem of interest, while producing a significantly smaller problem size than the standard techniques. [ABSTRACT FROM AUTHOR]

The rim multiparametric linear programming problem (RMPLP) is a parametric problem with a vector-parameter in both the right-hand side and objective function (i.e. in the "rim"). The RMPLP determines the region K&lowest; ⊂ E &lowest; such that the problem, maximize z(λ) = c T(λ)x, subject to Ax = b(λ), x ≥ 0, has a finite optimal solution for all λ ∈ K&lowest;. Let Bi be an optimal basis to the given problem, and let Ri&lowest; be a region assigned to Bi such that for all λ ∈ Ri&lowest; the basis Bi is optimal. The goal of the RMPLP problem is to cover K&lowest; by the Ri&lowest; such that the various Ri&lowest; do not overlap. The purpose of this paper is to present a solution method for finding all regions Ri&lowest; that cover K&lowest; and do not overlap. This method is based upon an algorithm for a multiparametric problem described in an earlier paper by Gal and Nedoma. [ABSTRACT FROM AUTHOR]

In an earlier issue of this journal, Charnes, Cooper, Niehaus and Stedry provided different problem formulations to take into account the multiple attributes that organizations may consider in assigning men to jobs. The present paper shows that their formulations for static multi-attribute models (i.e., when assignments are time independent) can be reformulated either as standard assignment problems or as bottleneck assignment problems by suitably redefining the cost coefficients, with the result that optimal solutions with integer assignments can be guaranteed. [ABSTRACT FROM AUTHOR]

Continuous location models generally use the Euclidean or rectangular norm to approximate travel in a transportation network. This paper considers a new and more accurate distance measure, termed the weighted one-two norm, which is a positive linear combination of the preceding norms. A directional bias function is introduced to show the equivalence of this distance measure to the well known l[sub p] norm. We then formulate a simple linear regression model to fit the parameters of our distance function to a given data set. Some novel applications based on standard statistical tests are derived which provide practical insights into the nature of networks with rectangular bias. The results are readily extended to other types of networks. [ABSTRACT FROM AUTHOR]

This paper describes a decentralized linear programming solution procedure. Unlike the classic Dantzig-Wolfe decomposition algorithm, this procedure is a complete decentralization, where the subproblems act independently to generate the optimal solution. In Dantzig-Wolfe decomposition, the master problem must "dictate" the final optimal solution. Our procedure is an improvement over Dantzig-Wolfe decomposition in this sense. The procedure works by adding a "coercion" function to the subproblem objective. Under proper conditions, this function "coerces" the subproblem to behave as desired. Such total decentralization is important for loosely coupled systems where it is not possible for the master level to dictate optimal decision values for the subsystems. [ABSTRACT FROM AUTHOR]

In this paper we propose a new method for solving linear programs. This method may be viewed as a generalized coordinate descent method whereby the descent directions are chosen from a finite set. The generation of the descent directions are based on results from monotropic programming theory. The method may be alternatively viewed as an extension of the relaxation method for network flow problems [1], [2]. Node labeling, cuts, and flow augmentation paths in the network case correspond to, respectively, tableau pivoting, rows of tableaus, and columns of tableaus possessing special sign patterns in the linear programming case. [ABSTRACT FROM AUTHOR]

This paper compares solution concepts associated with three location problems on a network: (i) a single-facility distance minimization problem; (ii) a two-facility spatial competition problem; and (iii) a single-facility locational voting problem. It is shown that the three problems have a common global solution when the network exhibits a property of symmetry around a point. For more general networks, this ceases to be true for global solutions but an identity holds for local solutions. [ABSTRACT FROM AUTHOR]

In this paper we consider a class of generalized equations, which are a unified way of formulating problems of linear and nonlinear programming, complementarity, variational inequalities and mathematical economics among others. We introduce a set of conditions, which we call the strong positivity conditions, prove that they are sufficient for a solution of a generalized equation to be locally unique, and discuss their stability when the functions involved in the problem are subjected to small perturbations. Applications to linear generalized equations and nonlinear programming problems are discussed. [ABSTRACT FROM AUTHOR]

The problem of two-dimensional irregular packing involves the arrangement of objects with diverse shapes and sizes within a given area. This challenge arises across various industrial sectors, where effective packing optimization can yield cost savings, enhanced productivity, and reduced material waste. Existing methods for addressing the two-dimensional irregular packing problem encounter several challenges, such as limited computing resources, a prolonged solving time, and the propensity to converge to local optima. To address this issue, this study proposes a hybrid algorithm called the GA-LP algorithm to optimize the two-dimensional irregular packing problem in the manufacturing industry. The algorithm combines the global search capability of a genetic algorithm with the precise solving characteristics of linear programming. Matheuristics merges the advantages of metaheuristics, such as genetic algorithms, and mathematical programming, such as linear programming. The algorithm employs the no-fit-polygon technique along with the bottom-left and lowest-gravity center mixing placement strategies to acquire an initial solution via the utilization of a genetic algorithm. The algorithm then optimizes the solution obtained by the genetic algorithm using linear programming to obtain the final packing result. Experimental results, drawn from a real case involving the European Special Interest Group on Cutting and Packing (ESICUP) demonstrate that the GA-LP algorithm outperforms two hybrid algorithms from the relevant literature. Compared with recent methods, this algorithm can increase the best and average utilization rates by up to 5.89% and 4.02%, respectively, with important implications for improving work quality in areas such as packing and cutting. [ABSTRACT FROM AUTHOR]

Scientific communities are motivated to schedule their large-scale data analysis workflows in heterogeneous cluster environments because of privacy and financial issues. In such environments containing considerably diverse resources, efficient resource allocation approaches are essential for reaching high performance. Accordingly, this research addresses the scheduling problem of workflows with bag-of-task form to minimize total runtime (makespan). To this aim, we develop a mixed-integer linear programming model (MILP). The proposed model contains binary decision variables determining which tasks should be assigned to which nodes. Also, it contains linear constraints to fulfill the tasks requirements such as memory and scheduling policy. Comparative results show that our approach outperforms related approaches in most cases. As part of the post-optimality analysis, some secondary preferences are imposed on the proposed model to obtain the most preferred optimal solution. We analyze the relaxation of the makespan in the hope of significantly reducing the number of consumed nodes. [ABSTRACT FROM AUTHOR]

This paper develops an algorithm for pure integer programming problems. It first transforms the integer programming problem to an algebraically equivalent Hermite canonical problem, and then employs the Fourier-Motzkin elimination. These algebraic operations transform the problem into a form that leads to an efficient implicit enumeration scheme to calculate an optimal solution. The algorithm constructs, in a finite number of operations, an optimal solution to an integer program with n variables and n or n + 1 inequality constraints. If the original problem has more than n + 1 constraints, then the integer program with only the constraints that are binding at an optimal linear programming solution is solved in place of the original problem. Computational results are presented. [ABSTRACT FROM AUTHOR]

The generalized network problem and the closely related restricted dyadic problem occur frequently in applications of linear programming. Although they are next in order of computational complexity after pure network or distribution problems, the jump in degree of difficulty is such that, in the most general problem, there exist no algorithms comparable in speed to those for pure networks. In this paper we characterize the properties of a special class of generalized network problems that permit a dual feasible basic solution to be determined in one 'pass' through the network. In particular, this class includes the class of pure network problems for which no such procedure has previously existed. Our algorithm also makes it possible to apply LEMKE'S dual method and the poly-ω technique of CHARNES AND COOPER in an efficient manner to solve capacitated (pure) network problems. [ABSTRACT FROM AUTHOR]

Multistage minimum-cost network-flow analysis solves many practical problems in production-inventory-distribution, marketing, personnel, and finance. Unlike previous network papers, which generally restricted themselves to a deterministic situation, this paper investigates the stochastic environment. Starting from the standard multistage network-flow problem, we create a stochastic network by permitting the node requirements to be discrete random variables with known conditional probability distributions. Our goal is to determine the minimum-expected-cost flow and thereby solve the problem. Although linear programming under uncertainty can determine this flow, it would ignore the special structure of network-flow problems that allows development of computationally efficient algorithms. In this paper, we instead exploit the underlying network structure to produce both a new structure that is not a network but maintains many of the properties of a network, and a new node that replicates flows instead of conserving them. The new nodes, called replication nodes, together with the new structure, allow the development of an efficient computational algorithm that is capable of solving problems much larger than those solvable by linear programming under uncertainty. [ABSTRACT FROM AUTHOR]

This paper reviews the principal public literature concerned with expected profit decision-theoretic closed-competitive-bidding models. It makes extensions of previous formulations for static multi-contract bidding situations with and without cost dependencies and resource constraints. The same decision model is reformulated to utilize numerical, Lagrange multiplier, dynamic, and integer linear programming techniques according to the information available to the bidder. A zero-one integer programming formulation is well suited to utilize subjective probabilities of winning estimates. Finally, the paper suggests a format for further development. [ABSTRACT FROM AUTHOR]

This paper combines the theory of generalized Lagrange multipliers with a reformulation of the integer-programming problem due to group theory. The use of multipliers enhances the algorithmic efficiency of group theory in a variety of ways. One particular application is the approximation of generalized Lagrange multipliers by generalized linear programming as suggested by BROOKS AND GEOFFRION. This procedure is shown to be closely related to the cutting-plane method of GOMORY. [ABSTRACT FROM AUTHOR]

This paper proposes a new class of cutting planes for integer programming. A typical member of the class is generated as follows. Let X be the feasible set, and ... the optimal (noninteger) solution to the linear program associated with an integer program in n-space. Consider a unit hypercube containing 2, whose vertices are integer, and the hypersphere circumscribing the cube. This hypersphere is intersected in n independent points by the n hairlines originating at ... and containing the n edges of X adjacent to (if ... is degenerate, X is replaced by X' ⊃ X having exactly n edges adjacent to ...). The hyperplane through these n points of intersection defines a valid cut, the (spherical) intersection cut. The paper gives a simple formula for finding the equation of the hyperplane, discusses some ways of strengthening the cut, proposes an algorithm, and gives a finiteness proof. A straightforward extension of these geometric ideas yields an analogous (cylindrical) intersection cut for the mixed-integer case. A discussion of relations to other work (Young, Gomory) is followed by the introduction of some additional intersection cuts obtained from hypersurfaces other than the sphere or the cylinder. The message of this paper lies, not so much in the particular cuts that it proposes, as in the basically new approach to integer programming that these cuts typify. This approach is geometrically motivated and uses the 'local' properties (in the integer-programming sense) of the feasible set. [ABSTRACT FROM AUTHOR]