A linear programming problem in separable closed queueing networks

A separable closed queueing network is decomposed into two subnetworks. The rates of the servers in one of the subnetworks are controllable in order to maximize the throughput of the other one. This problem of optimal flow control is transformed to a linear programming problem. The optimal solution of the linear program yields the structure of the optimal control. Conditions for the network are given to guarantee the applicability of this approach     

A linear programming approach to max-sum problem: a review

The max-sum labeling problem, defined as maximizing a sum of binary (i.e., pairwise) functions of discrete variables, is a general NP-hard optimization problem with many applications, such as computing the MAP configuration of a Markov random field. We review a not widely known approach to the problem, developed by Ukrainian researchers Schlesinger et al. in 1976, and show how it contributes to recent results, most importantly, those on the convex combination of trees and tree-reweighted max-product. In particular, we review Schlesinger et al.'s upper bound on the max-sum criterion, its minimization by equivalent transformations, its relation to the constraint satisfaction problem, the fact that this minimization is dual to a linear programming relaxation of the original problem, and the three kinds of consistency necessary for optimality of the upper bound. We revisit problems with Boolean variables and supermodular problems. We describe two algorithms for decreasing the upper bound. We present an example application for structural image analysis.     

A neural network approach for solving linear bilevel programming problem

A novel neural network approach is proposed for solving linear bilevel programming problem. The proposed neural network is proved to be Lyapunov stable and capable of generating optimal solution to the linear bilevel programming problem. The numerical result shows that the neural network approach is feasible and efficient.     

A linear complementarity approach to the articulated multifingered friction gripper

In this article, the problem of grasping by an articulated multifingered gripper is investigated. The fingers' joints are idealized by angular and linear springs for the revolute and prismatic joints, respectively. The method, which was developed here, considers the cases of both hard and soft fingers. The unilateral frictional contact problem for the gripper-object system is formulated as a linear complementarity problem. Numerical examples illustrating the theory are given.     

A linear two-level programming problem

A stackleberg game in which a first player can affect the resources available to a second player is defined. For given first move the second player will maximize a linear program, subject to the resources available. The first player attempts to maximize his own linear objective function which contains variables under the control of the second player. Even though all functions are linear, it is shown that local optima can exist. An implicit search is described which uses necessary conditions for a better solution, to limit the extent of the search.     

A linear programming approach to reasoning about probabilities

We continue our study, initiated in [9], of the following computational problem proposed by Nilsson: Several clauses (Boolean functions of several variables) are given, and for each clause the probability that the clause is true is specified. We are asked whether these probabilities are consistent. They are if there is a probability distribution on the truth assignments such that the probability of each clause is the measure of its satisfying set of assignments. Since this is a generalization of the satisfiability problem of predicate calculus, it is immediately NP-hard. In [9] we showed certain restricted cases of the problem to be NP-complete, and used the Ellipsoid Algorithm to show that a certain special case is in P. In this paper we use the Simplex method, column generation techniques, and variable-depth local search to derive an effective heuristic for the general problem. Experiments show that our heuristic performs successfully on instances with many dozens of variables and clauses. We also prove several interesting complexity results that answer open questions in [9] and motivate our approach.     

A linear programming approach to constrained robust predictivecontrol

A receding horizon predictive control algorithm for systems with model uncertainty and input constraints is developed. The proposed algorithm adopts the receding horizon dual-mode (i.e., free control moves and invariant set) paradigm. The approach is novel in that it provides a convenient way of combining predictions of control moves, which are optimal in the sense of worst case performance, with large target invariant sets. Thus, the proposed algorithm has a large stabilizable set of states corresponding to a cautious state feedback law while enjoying the good performance of a tightly tuned but robust control law. Unlike earlier approaches which are based on QP or semidefinite programming, here computational complexity is reduced through the use of LP     

Iterative algorithms for the linear complementarity problem

Direct complementary pivot algorithms for the linear complementarity problem with P-matrices are known to have exponential computational complexity. The analog of Gauss-Seidel and SOR iteration for linear complementarity problems with P-matrices has not been extensively developed. This paper extends some work of van Bokhoven to a class of nonsymmetric P-matrices, and develops and compares several new iterative algorithms for the linear complementarity problem. Numerical results for several hundred test problems are presented. Such indirect iterative algorithms may prove useful for large sparse complementarity problems.     

A sequential linear programming approach to solve mixed integer programming problems

The optimal operation of pumps in a large water supply system under time-of-use electricity rates is formulated as a mixed integer programming (MIP) problem. The problem is solved using an iterative linear programming (LP) scheme. The scheme is applied to an actual world problem, the City of Inglewood Water Supply System. Computational results are presented and termination criteria for the solution scheme are discussed.     

A multiplicative multisplitting method for solving the linear complementarity problem

The convergence of the multiplicative multisplitting-type method for solving the linear complementarity problem with an H-matrix is discussed using classical and new results from the theory of splitting. This directly results in a sufficient condition for guaranteeing the convergence of the multiplicative multisplitting method. Moreover, the multiplicative multisplitting method is applied to the H-compatible splitting and the multiplicative Schwarz method, separately. Finally, we establish the monotone convergence of the multiplicative multisplitting method under appropriate conditions.     

Modified gradient dynamic approach to the tensor complementarity problem

ABSTRACT

Nonlinear gradient dynamic approach for solving the tensor complementarity problem (TCP) are presented. Theoretical analysis shows that each of the defined dynamical system models ensures the convergence. The computer-simulation results further substantiate that the considered dynamical system can solve the TCP.     

An interval programming approach for the bilevel linear programming problem under fuzzy random environments

In this paper, we address a class of bilevel linear programming problems with fuzzy random variable coefficients in objective functions. To deal with such problems, we apply an interval programming approach based on the $\alpha $ -level set to construct a pair of bilevel mathematical programming models called the best and worst optimal models. Through expectation optimization model, the best and worst optimal problems are transformed into the deterministic problems. By means of the Kth best algorithm, we obtain the best and worst optimal solutions as well as the corresponding range of the objective function values. In this way, more information can be provided to the decision makers under fuzzy random circumstances. Finally, experiments on two examples are carried out, and the comparisons with two existing approaches are made. The results indicate the proposed approaches can get not only the best optimal solution (ideal solution) but also the worst optimal solution, and is more reasonable than the existing approaches which can only get a single solution (ideal solution).     

A linear programming approach to shakedown analysis of structures

Two and three dimensional structures are dealt with, subjected to variable repeated loads, in order to establish a numerical tool for determining the load domain multiplier that gives rise to shakedown. The structure is made discrete by finite elements and the yield domain is linearized. By applying Bleich and Melan's theorem, two primal static formulations are found in linear programming, from which the relevant dual kinematic versions are obtained via duality properties.Numerical results are given at the end of the paper, together with some considerations about the numerical efficiency of the proposed formulations.     

A weight space-based approach to fuzzy multiple-objective linear programming

In this paper, the effects of uncertainty on multiple-objective linear programming models are studied using the concepts of fuzzy set theory. The proposed interactive decision support system is based on the interactive exploration of the weight space. The comparative analysis of indifference regions on the various weight spaces (which vary according to intervals of values of the satisfaction degree of objective functions and constraints) enables to study the stability and evolution of the basis that correspond to the calculated efficient solutions with changes of some model parameters.     

A constraint programming approach to the multiple-venue,sport-scheduling problem

In this paper, we consider the problem of scheduling sports competitions over several venues which are not associated with any of the competitors. A two-phase, constraint programming approach is developed, first identifying a solution that designates the participants and schedules each of the competitions, then assigning each competitor as the “home” or the “away” team. Computational experiments are conducted and the results are compared with an integer goal programming approach. The constraint programming approach achieves optimal solutions for problems with up to sixteen teams, and near-optimal solutions for problems with up to thirty teams.     

A unified approach to the linear camera calibration problem

The camera calibration process relates camera system measurements (pixels) to known reference points in a three-dimensional world coordinate system. The calibration process is viewed as consisting of two independent phases: the first is removing geometrical camera distortion so that rectangular calibration grids are straightened in the image plane, and the second is using a linear affine transformation as a map between the rectified camera coordinates and the geometrically projected coordinates on the image plane of known reference points. Phase one is camera-dependent, and in some systems may be unnecessary. Phase two is concerned with a generic model that includes 12 extrinsic variables and up to five intrinsic parameters. General methods handling additional constraints on the intrinsic variables in a manner consistent with explicit satisfaction of all six constraints on the orthogonal rotation matrix are presented. The use of coplanar and noncoplanar calibration points is described     

Sparsity-preserving sor algorithms for separable quadratic and linear programming

The main purpose of this work is to give explicit sparsity-preserving SOR (successive overrelaxation) algorithms for the solution of separable quadratic and linear programming problems. The principal and computationally-distinguishing feature of the present SOR algorithms is that they preserve the sparsity structure of the problem and do not require the computation of the product of the constraint matrix by its transpose as is the case in earlier SOR algorithms for linear and quadratic programming.     

A logarithmic-time solution to the point location problem for parametric linear programming

The optimiser of a (multi) parametric linear program (pLP) is a piecewise affine function defined over a polyhedral subdivision of the set of feasible states. Once this affine function has been pre-calculated, the optimal solution can be computed for a particular parameter by determining the region that contains it. This is the so-called point location problem. In this paper, we show that this problem can be written as an additively weighted nearest neighbour search that can be solved in time linear in the dimension of the state space and logarithmic in the number of regions.

It is well-known that linear model predictive control (MPC) problems based on linear control objectives (e.g., 1- or ∞-norm) can be posed as pLPs, and on-line calculation of the control law involves the solution to the point location problem. Several orders of magnitude sampling speed improvement are demonstrated over traditional MPC and closed-form MPC schemes using the proposed scheme.     

Multi-media instructional approach to teaching linear programming

This paper describes different strategies employed in converting a lecture-oriented mathematical programming course to a Personalized Self-Paced Instructional (PSI) format. This is an elective course for students in science, engineering and management. A multi media instructional approach is used in the PSI system which combines traditional lectures, self-paced and individualized learning assisted by interactive computer programs and video taped instructional materials. This unique PSI system for mathematical programming provides maximum learning opportunity and flexibility to students. The author's experiences with the PSI system and the students' evaluation of the self-paced system are also discussed.