Demurrage costs optimization in ports using binary mathematical programming models

Summary SODA is a system by which the schedule of ships in a port can be found in order to minimize the demurrage and operating costs associated with shipping operations. SODA constructs and resolves binary programming models using shipping data (arrival dates, demurrage costs, berths to be used, etc.) and available berths in a planning horizon. The model is of an adjustable precision: major accuracy implies greater calculation time. SODA provides an optimal result to a complex problem in a resolution time which is generally better than that needed for a manual solution.     

A meta-control algorithm for generating approximate solutions to binary integer programming problems

Binary integer program problems, which are known to be difficult to solve, have long been an important research area. We use a new approach with continualization techniques to find approximate solutions to binary integer programming problems. The algorithm constructs a sequence of approximations to a solution using a meta-control approach that has low polynomial time complexity. The algorithm is illustrated with a BIP example.     

MATHEMATICAL ANALYSIS OF SOME NEURAL NETWORKS FOR SOLVING LINEAR AND QUADRATIC PROGRAMMING

ＺＨＡＮＧＸＩＡＮＧＳＵＮ（章祥荪）（ＩｎｓｔｉｔｕｔｅｏｆＡｐｐｌｉｅｄＭａｔｈｅｍａｔｉｃｓｔｈｅＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ１０００８０，Ｃｈｉｎａ）ＲｅｃｅｉｖｅｄＪｕｎｅ１８，１９９４．Ｔｈｉｓｗｏｒｋｉ...     

A global continuation algorithm for solving binary quadratic programming problems

In this paper, we propose a new continuous approach for the unconstrained binary quadratic programming (BQP) problems based on the Fischer-Burmeister NCP function. Unlike existing relaxation methods, the approach reformulates a BQP problem as an equivalent continuous optimization problem, and then seeks its global minimizer via a global continuation algorithm which is developed by a sequence of unconstrained minimization for a global smoothing function. This smoothing function is shown to be strictly convex in the whole domain or in a subset of its domain if the involved barrier or penalty parameter is set to be sufficiently large, and consequently a global optimal solution can be expected. Numerical results are reported for 0-1 quadratic programming problems from the OR-Library, and the optimal values generated are made comparisons with those given by the well-known SBB and BARON solvers. The comparison results indicate that the continuous approach is extremely promising by the quality of the optimal values generated and the computational work involved, if the initial barrier parameter is chosen appropriately. This work is partially supported by the Doctoral Starting-up Foundation (B13B6050640) of GuangDong Province.     

Binary fuzzy goal programming

Goal programming is an important technique for solving many decision/management problems. Fuzzy goal programming involves applying the fuzzy set theory to goal programming, thus allowing the model to take into account the vague aspirations of a decision-maker. Using preference-based membership functions, we can define the fuzzy problem through natural language terms or vague phenomena. In fact, decision-making involves the achievement of fuzzy goals, some of them are met and some not because these goals are subject to the function of environment/resource constraints. Thus, binary fuzzy goal programming is employed where the problem cannot be solved by conventional goal programming approaches. This paper proposes a new idea of how to program the binary fuzzy goal programming model. The binary fuzzy goal programming model can then be solved using the integer programming method. Finally, an illustrative example is included to demonstrate the correctness and usefulness of the proposed model.     

Analysis and comparisons of some solution concepts for stochastic programming problems

The aim of this study is to analyse the resolution of Stochastic Programming Problems in which the objective function depends on parameters which are continuous random variables with a known distribution probability. In the literature on these questions different solution concepts have been defined for problems of these characteristics. These concepts are obtained by applying a transformation criterion to the stochastic objective which contains a statistical feature of the objective, implying that for the same stochastic problem there are different optimal solutions available which, in principle, are not comparable. Our study analyses and establishes some relations between these solution concepts. The work of these authors was supported byMinisterio de Ciencia y Tecnología andConsejería de Educación y Ciencia, Junta de Andalucía.     

Dynamic programming for some optimal control problems with hysteresis

We study an infinite horizon optimal control problem for a system with two state variables. One of them has the evolution governed by a controlled ordinary differential equation and the other one is related to the latter by a hysteresis relation, represented here by either a play operator or a Prandtl-Ishlinskii operator. By dynamic programming, we derive the corresponding (discontinuous) first order Hamilton-Jacobi equation, which in the first case is of finite dimension and in the second case is of infinite dimension. In both cases we prove that the value function is the only bounded uniformly continuous viscosity solution of the equation.     

Membership functions,some mathematical programming models and production scheduling

The authors have studied in [5] alternative real variable models based on the function $\text{d(x) =}\text{x}\text{(α + x)}\text{, α >0}$, for certain integer or mixed-interger programming problems. Mainly, we have shown that there exists a vector α > 0 such that the solution to the problem min $\text{σ}{}_1\text{(x, α) = Σ}{}_{\mathrm{i=1}}{}^{\mathrm{n}}\text{x}{}_{\mathrm{i}}\text{(ga}{}_{\mathrm{i}}\text{+x}{}_{\mathrm{i}}\text{)}\text{, Ax = b, x ? 0}$, is a solution to the problem min σxσ⁺, Ax = b, x ? 0, where σxσ⁺ denotes the cardinal of x, i.e. the number of strictly positive components of x, thus obtaining a new model for solving in real numbers a Generalized Lattice Point Problem (Cabot, [3]).The function d(x) has been introduced by use as a general tool for solving integer or mixed-integer problems due to its property of having almost everywhere almost discrete values. In the meantime we noticed that this function may represent a membership function of a fuzzy set.In this paper, we study in detail the features of this membership function and show that Cabot's results [3] may be derived in this more general setting using the complementary function $\text{s(x) =}\text{1 ? x}\text{(α + x)}\text{=}\text{α}\text{(α+x)}$.At the same time, in the paper there are some production scheduling models within the framework of fuzzy-sets theory. To this end, a nonconvex production model is presented and it is shown that the value of the objective function $\text{μ}{}_2\text{=}\text{1 ? σ}{}_1\text{n}$ for a production programming model whose deman and/or resource vector components are parametrized, may be considered as a grade of membership of the solution of the parametrized model to the feasible set of the nonparametrized production programming model.Consequently, we get a nonconvex production programming model whose convex envelope is linear with coefficients which are in an inverse proportior to the magnitude of the nonparametrized demand or resource vector components. This result agrees with the intuitive idea that a high level of demand or resource allows a greater interval of variation in the production process than a lower level of demand or resource.     

Block-diagonal semidefinite programming hierarchies for 0/1 programming

Lovász and Schrijver, and later Lasserre, proposed hierarchies of semidefinite programming relaxations for 0/1 linear programming problems. We revisit these two constructions and propose two new, block-diagonal hierarchies, which are at least as strong as the Lovász-Schrijver hierarchy, but less costly to compute. We report experimental results for the stable set problem of Paley graphs.     

A multi-parametric programming approach for constrained dynamic programming problems

In this work, we present a new algorithm for solving complex multi-stage optimization problems involving hard constraints and uncertainties, based on dynamic and multi-parametric programming techniques. Each echelon of the dynamic programming procedure, typically employed in the context of multi-stage optimization models, is interpreted as a multi-parametric optimization problem, with the present states and future decision variables being the parameters, while the present decisions the corresponding optimization variables. This reformulation significantly reduces the dimension of the original problem, essentially to a set of lower dimensional multi-parametric programs, which are sequentially solved. Furthermore, the use of sensitivity analysis circumvents non-convexities that naturally arise in constrained dynamic programming problems. The potential application of the proposed novel framework to robust constrained optimal control is highlighted.     

On some symmetric dual models in multiobjective programming

Certain omissions have been pointed out in some papers on symmetric duality in multiobjective programming. Corrective measures have also been discussed.     

Convergence property of the Iri-Imai algorithm for some smooth convex programming problems

In this paper, the Iri-Imai algorithm for solving linear and convex quadratic programming is extended to solve some other smooth convex programming problems. The globally linear convergence rate of this extended algorithm is proved, under the condition that the objective and constraint functions satisfy a certain type of convexity, called the harmonic convexity in this paper. A characterization of this convexity condition is given. The same convexity condition was used by Mehrotra and Sun to prove the convergence of a path-following algorithm.The Iri-Imai algorithm is a natural generalization of the original Newton algorithm to constrained convex programming. Other known convergent interior-point algorithms for smooth convex programming are mainly based on the path-following approach.     

Mathematical programming techniques in majorization

In this paper, we are concerned with mathematical programs which construct nonmajorizing vectors for several specific majorization applications. In particular, we develop a linear integer program and two integer goal programs which solve the assignment majorization problem. We also develop a quadratic program for solving majorization problems which arise in probability and statistics. In the appendix, we present a general goal-programming algorithm for these, as well as others, goal programs.The authors would like to thank Professor Y. Tong for introducing them to majorization and its applications. They would also like to thank Professors Y. Tong and D. Mesner for helpful discussions.     

Mathematical programming in the Netherlands

Results of an exhaustive survey of mathematical programming in the Netherlands held in 1982 are presented and, where applicable, compared to a survey held in 1976. It appears that the growth rate has levelled off, that about half of the largest one hundred industrial firms in the Netherlands now apply MP and that the users are quite satisfied with LP programs except for input, output and documentation.     

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.     

Fuzzy goal programming approach to multilevel programming problems

The purpose of this paper is to propose a procedure for solving multilevel programming problems in a large hierarchical decentralized organization through linear fuzzy goal programming approach. Here, the tolerance membership functions for the fuzzily described objectives of all levels as well as the control vectors of the higher level decision makers are defined by determining individual optimal solution of each of the level decision makers. Since the objectives are potentially conflicting in nature, a possible relaxation of the higher level decision is considered for avoiding decision deadlock. Then fuzzy goal programming approach is used for achieving highest degree of each of the membership goals by minimizing negative deviational variables. Sensitivity analysis with variation of tolerance values on decision vectors is performed to present how the solution is sensitive to the change of tolerance values. The efficiency of our concept is ascertained by comparing results with other fuzzy programming approaches.     

Mathematical models for job-shop scheduling problems with routing and process plan flexibility

As a result of rapid developments in production technologies in recent years, flexible job-shop scheduling problems have become increasingly significant. This paper deals with two NP-hard optimization problems: flexible job-shop scheduling problems (FJSPs) that encompass routing and sequencing sub-problems, and the FJSPs with process plan flexibility (FJSP-PPFs) that additionally include the process plan selection sub-problem. The study is carried out in two steps. In the first step, a mixed-integer linear programming model (MILP-1) is developed for FJSPs and compared to an alternative model in the literature (Model F) in terms of computational efficiency. In the second step, one other mixed-integer linear programming model, a modification of MILP-1, for the FJSP-PPFs is presented along with its computational results on hypothetically generated test problems.     

Mathematical programming models for piecewise-linear discriminant analysis

Mathematical programming (MP) discriminant analysis models are widely used to generate linear discriminant functions that can be adopted as classification models. Nonlinear classification models may have better classification performance than linear classifiers, but although MP methods can be used to generate nonlinear discriminant functions, functions of specified form must be evaluated separately. Piecewise-linear functions can approximate nonlinear functions, and two new MP methods for generating piecewise-linear discriminant functions are developed in this paper. The first method uses maximization of classification accuracy (MCA) as the objective, while the second uses an approach based on minimization of the sum of deviations (MSD). The use of these new MP models is illustrated in an application to a test problem and the results are compared with those from standard MCA and MSD models.     

Connectivity threshold and recovery time in rank-based models for complex networks

We study a generalized version of the protean graph (a probabilistic model of the World Wide Web) with a power law degree distribution, in which the degree of a vertex depends on its age as well as its rank. The main aim of this paper is to study the behaviour of the protean process near the connectivity threshold. Since even above the connectivity threshold it is still possible that the graph becomes disconnected, it is important to investigate the recovery time for connectivity, that is, how long we have to wait to regain the connectivity.     

An efficient method for solving linear goal programming problems

This note proposes a solution algorithm for linear goal programming problems. The proposed method simplifies the traditional solution methods. Also, the proposed method is computationally efficient.