区间规划问题的最优性条件

区间规划是带有区间参数的规划问题,是一种更易于求解实际问题的柔性规划。它是确定性优化问题的延伸,有区间线性规划和区间非线性规划两种形式。本文讨论了目标函数是区间函数的区间非线性问题。给出了区间规划问题最优性必要条件的较简单证明方法,并利用LU最优解的概念,在一类广义凸函数－(p,r)－ρ－(η,θ)－不变凸函数定义下讨论了最优性充分条件。     

On the global solution of multi-parametric mixed integer linear programming problems

This paper deals with the global solution of the general multi-parametric mixed integer linear programming problem with uncertainty in the entries of the constraint matrix, the right-hand side vector, and in the coefficients of the objective function. To derive the piecewise affine globally optimal solution, the steps of a multi-parametric branch-and-bound procedure are outlined, where McCormick-type relaxations of bilinear terms are employed to construct suitable multi-parametric under- and overestimating problems. The alternative of embedding novel piecewise affine relaxations of bilinear terms in the proposed algorithmic procedure is also discussed.     

A two-phase method for selecting IMRT treatment beam angles: Branch-and-Prune and local neighborhood search

This paper presents a new two-phase solution approach to the beam angle and fluence map optimization problem in Intensity Modulated Radiation Therapy (IMRT) planning. We introduce Branch-and-Prune (B&P) to generate a robust feasible solution in the first phase. A local neighborhood search algorithm is developed to find a local optimal solution from the Phase I starting point in the second phase. The goal of the first phase is to generate a clinically acceptable feasible solution in a fast manner based on a Branch-and-Bound tree. In this approach, a substantially reduced search tree is iteratively constructed. In each iteration, a merit score based branching rule is used to select a pool of promising child nodes. Then pruning rules are applied to select one child node as the branching node for the next iteration. The algorithm terminates when we obtain a desired number of angles in the current node. Although Phase I generates quality feasible solutions, it does not guarantee optimality. Therefore, the second phase is designed to converge Phase I starting solutions to local optimality. Our methods are tested on two sets of real patient data. Results show that not only can B&P alone generate clinically acceptable solutions, but the two-phase method consistently generates local optimal solutions, some of which are shown to be globally optimal.     

Enumeration of All Possibly Optimal Vertices with Possible Optimality Degrees in Linear Programming Problems with a Possibilistic Objective Function

In this paper, we treat linear programming problems with fuzzy objective function coefficients. To such a problem, the possibly optimal solution set is defined as a fuzzy set. It is shown that any possibly optimal solution can be represented by a convex combination of possibly optimal vertices. A method to enumerate all possibly optimal vertices with their membership degrees is developed. It is shown that, given a possibly optimal extreme point with a higher membership degree, the membership degree of an adjacent extreme point is calculated by solving a linear programming problem and that all possibly optimal vertices are enumerated sequentially by tracing adjacent possibly optimal extreme points from a possibly optimal extreme point with the highest membership degree.     

Production planning with approved vendor matrices for a hard-disk drive manufacturer

We develop an optimal production schedule for a manufacturer of hard-disk drives that offers its customers the approved vendor matrix (AVM) as a competitive advantage. An AVM allows each customer to pick and choose the various product component vendors for individual or pairs of components constituting their product. The production planning problem faced by the manufacturer is to meet customer demand as precisely as possible while observing the matrix restrictions and also the limited availability of production resources. We formulate this problem as a linear programming model with a large number of variables, and present a solution procedure based on the column generation technique. A special class of the problem is then studied, whereby the number of production setups in each period is limited and discrete. We modify our formulation into a mixed-integer problem, and proceed to develop procedures that can obtain good feasible solutions using linear programming rounding techniques.     

Geometric and algorithmic developments for a hierarchical planning problem

This paper presents a new model for multiobjective planning in hierarchical systems that explicitly takes into consideration the order in which decisions are made. Interactions and conflicts that normally exist among the levels are introduced by specifying jointly controlled feasible regions and interdependent objective functions. At each level in the system, planners attempt to maximize net benefits in light of all higher-level decisions, and thus may influence but not control the behavior of others. The resultant formulation leads to the multilevel programming problem. The geometry of an all linear case is first examined wherein it is shown that the optimal solution must lie at a vertex of the original polyhedral constraint region. Next, a set of first order optimality conditions is derived for the general case and used as the basis of an algorithm for the linear problem. A number of examples are given to highlight the results.     

Parametric global optimisation for bilevel programming

We propose a global optimisation approach for the solution of various classes of bilevel programming problems (BLPP) based on recently developed parametric programming algorithms. We first describe how we can recast and solve the inner (follower’s) problem of the bilevel formulation as a multi-parametric programming problem, with parameters being the (unknown) variables of the outer (leader’s) problem. By inserting the obtained rational reaction sets in the upper level problem the overall problem is transformed into a set of independent quadratic, linear or mixed integer linear programming problems, which can be solved to global optimality. In particular, we solve bilevel quadratic and bilevel mixed integer linear problems, with or without right-hand-side uncertainty. A number of examples are presented to illustrate the steps and details of the proposed global optimisation strategy.     

On accuracy,robustness and tolerances in vector Boolean optimization

A Boolean programming problem with a finite number of alternatives where initial coefficients (costs) of linear payoff functions are subject to perturbations is considered. We define robust solution as a feasible solution which for a given set of realizations of uncertain parameters guarantees the minimum value of the worst-case relative regret among all feasible solutions. For the Pareto optimality principle, an appropriate definition of the worst-case relative regret is specified. It is shown that this definition is closely related to the concept of accuracy function being recently intensively studied in the literature. We also present the concept of robustness tolerances of a single cost vector. The tolerance is defined as the maximum level of perturbation of the cost vector which does not destroy the solution robustness. We present formulae allowing the calculation of the robustness tolerance obtained for some initial costs. The results are illustrated with several numerical examples.     

The final NETLIB-LP results

With standard linear programming solvers there is always some uncertainty about the precise values of the optimal solutions. We implemented a program using exact rational arithmetic to compute proofs for the feasibility and optimality of an LP solution. This paper reports the exact optimal objective values for all NETLIB problems.     

A further study on inverse linear programming problems

In this paper we continue our previous study (Zhang and Liu, J. Comput. Appl. Math. 72 (1996) 261–273) on inverse linear programming problems which requires us to adjust the cost coefficients of a given LP problem as less as possible so that a known feasible solution becomes the optimal one. In particular, we consider the cases in which the given feasible solution and one optimal solution of the LP problem are 0–1 vectors which often occur in network programming and combinatorial optimization, and give very simple methods for solving this type of inverse LP problems. Besides, instead of the commonly used l₁ measure, we also consider the inverse LP problems under l_∞ measure and propose solution methods.     

Checking weak optimality of the solution to linear programming with interval right-hand side

The interval linear programming (IvLP) is a method for decision making under uncertainty. A weak feasible solution to IvLP is called weakly optimal if it is optimal for some scenario of the IvLP. One of the basic and difficult tasks in IvLP is to check whether a given point is weak optimal. In this paper, we investigate linear programming problems with interval right-hand side. Some necessary and sufficient conditions for checking weak optimality of given feasible solutions are established, based on the KKT conditions of linear programming. The proposed methods are simple, easy to implement yet very effective, since they run in polynomial time.     

A Semidefinite Programming Heuristic for Quadratic Programming Problems with Complementarity Constraints

The presence of complementarity constraints brings a combinatorial flavour to an optimization problem. A quadratic programming problem with complementarity constraints can be relaxed to give a semidefinite programming problem. The solution to this relaxation can be used to generate feasible solutions to the complementarity constraints. A quadratic programming problem is solved for each of these feasible solutions and the best resulting solution provides an estimate for the optimal solution to the quadratic program with complementarity constraints. Computational testing of such an approach is described for a problem arising in portfolio optimization.Research supported in part by the National Science Foundations VIGRE Program (Grant DMS-9983646).Research partially supported by NSF Grant number CCR-9901822.     

The out-of-kilter algorithm applied to traffic congestion

The out-of-kilter algorithm finds a minimum cost assignment of flows to a network defined in terms of one-way arcs, each with upper and lower bounds on flow, and a cost. It is a mathematical programming algorithm which exploits the network structure of the data. The objective function, being the sum taken over all the arcs of the products, cost×flow, is linear. The algorithm is applied in a new way to minimise a series of linear functions in a heuristic method to reduce the value of a non-convex quadratic function which is a measure of traffic congestion. The coefficients in these linear functions are chosen in a way which avoids one of the pitfalls occurring when Beale's method is applied to such a quadratic function. The method does not guarantee optimality but has produced optimal results with networks small enough for an integer linear programming method to be feasible.     

An Improved Multi-parametric Programming Algorithm for Flux Balance Analysis of Metabolic Networks

Flux balance analysis has proven an effective tool for analyzing metabolic networks. In flux balance analysis, reaction rates and optimal pathways are ascertained by solving a linear program, in which the growth rate is maximized subject to mass-balance constraints. A variety of cell functions in response to environmental stimuli can be quantified using flux balance analysis by parameterizing the linear program with respect to extracellular conditions. However, for most large, genome-scale metabolic networks of practical interest, the resulting parametric problem has multiple and highly degenerate optimal solutions, which are computationally challenging to handle. An improved multi-parametric programming algorithm based on active-set methods is introduced in this paper to overcome these computational difficulties. Degeneracy and multiplicity are handled, respectively, by introducing generalized inverses and auxiliary objective functions into the formulation of the optimality conditions. These improvements are especially effective for metabolic networks because their stoichiometry matrices are generally sparse; thus, fast and efficient algorithms from sparse linear algebra can be leveraged to compute generalized inverses and null-space bases. We illustrate the application of our algorithm to flux balance analysis of metabolic networks by studying a reduced metabolic model of Corynebacterium glutamicum and a genome-scale model of Escherichia coli. We then demonstrate how the critical regions resulting from these studies can be associated with optimal metabolic modes and discuss the physical relevance of optimal pathways arising from various auxiliary objective functions. Achieving more than fivefold improvement in computational speed over existing multi-parametric programming tools, the proposed algorithm proves promising in handling genome-scale metabolic models.     

The Complex Interior-Boundary method for linear and nonlinear programming with linear constraints

In this paper we develop the Complex method; an algorithm for solving linear programming (LP) problems with interior search directions. The Complex Interior-Boundary method (as the name suggests) moves in the interior of the feasible region from one boundary point to another of the feasible region bypassing several extreme points at a time. These directions of movement are guaranteed to improve the objective function. As a result, the Complex method aims to reach the optimal point faster than the Simplex method on large LP programs. The method also extends to nonlinear programming (NLP) with linear constraints as compared to the generalized-reduced gradient.The Complex method is based on a pivoting operation which is computationally efficient operation compared to some interior-point methods. In addition, our algorithm offers more flexibility in choosing the search direction than other pivoting methods (such as reduced gradient methods). The interior direction of movement aims at reducing the number of iterations and running time to obtain the optimal solution of the LP problem compared to the Simplex method. Furthermore, this method is advantageous to Simplex and other convex programs in regard to starting at a Basic Feasible Solution (BFS); i.e. the method has the ability to start at any given feasible solution.Preliminary testing shows that the reduction in the computational effort is promising compared to the Simplex method.     

线性多级规划的最优性条件和基本性质

本文研究的线性多级规划模型比较一般化，容许集可以是无界的，每级的目标函数可以与各下级控制的决策变量有关．我们得到了这类多级规划的一组最优性充要条件，利用这组条件推导了各级可行集的弱拟凸性、连通性等几何性质．作为应用订正了Bard的一个例题．     

On the adjustment problem for linear programs

We propose a generalization of the inverse problem which we will call the adjustment problem. For an optimization problem with linear objective function and its restriction defined by a given subset of feasible solutions, the adjustment problem consists in finding the least costly perturbations of the original objective function coefficients, which guarantee that an optimal solution of the perturbed problem is also feasible for the considered restriction. We describe a method of solving the adjustment problem for continuous linear programming problems when variables in the restriction are required to be binary.     

Solving knapsack sharing problems with general tradeoff functions

A knapsack sharing problem is a maximin or minimax mathematical programming problem with one or more knapsack constraints (an inequality constraint with all non-negative coefficients). All knapsack sharing algorithms to date have assumed that the objective function is composed of single variable functions called tradeoff functions which are strictly increasing continuous functions. This paper develops optimality conditions and algorithms for knapsack sharing problems with any type of continuous tradeoff function including multiple-valued and staircase functions which can be increasing, decreasing, unimodal, bimodal, or even multi-modal. To do this, optimality conditions are developed for a special type of multiple-valued, nondecreasing tradeoff function called an ascending function. The optimal solution to any knapsack sharing problem can then be found by solving an equivalent problem where all the tradeoff functions have been transformed to ascending functions. Polynomial algorithms are developed for piecewise linear tradeoff functions with a fixed number of breakpoints. The techniques needed to construct efficient algorithms for any type of tradeoff function are discussed.     

Optimal operating strategy for a long-haul liner service route

This paper proposes an optimal operating strategy problem arising in liner shipping industry that aims to determine service frequency, containership fleet deployment plan, and sailing speed for a long-haul liner service route. The problem is formulated as a mixed-integer nonlinear programming model that cannot be solved efficiently by the existing solution algorithms. In view of some unique characteristics of the liner shipping operations, this paper proposes an efficient and exact branch-and-bound based ε-optimal algorithm. In particular, a mixed-integer nonlinear model is first developed for a given service frequency and ship type; two linearization techniques are subsequently presented to approximate this model with a mixed-integer linear program; and the branch-and-bound approach controls the approximation error below a specified tolerance. This paper further demonstrates that the branch-and-bound based ε-optimal algorithm obtains a globally optimal solution with the predetermined relative optimality tolerance ε in a finite number of iterations. The case study based on an existing long-haul liner service route shows the effectiveness and efficiency of the proposed solution method.     

The b-hull of an integer program

Given a linear integer program: max{cx:Ax=b, x≥0 and integer},A rational, it is known that it can be solved in theory for all values of c, either by testing a finite number of solutions for optimality, or by adding a finite number of valid inequalities, each generated from a superadditive function, and solving the resulting linear program.The main result of this paper is to show that (analogously) the integer program can be solved for all values of b, either by testing a finite number of solutions for feasibility and optimality, or by adding a finite number of valid inequalities, each generated from a superadditive function, and solving the resulting linear program.