The Transportation Problem and its Variants

For 54 unimodular linear programming problems it is shown that either (i) the objective function is unbounded, or (ii) the problem is infeasible, or (iii) the problem can be solved by solving a related transportation problem. The related transportation problem is obtained by adding at the most two new constraints to the original problem.     

Global Maximization of a Generalized Concave Multiplicative Function

This article presents a branch-and-bound algorithm for globally solving the problem (P) of maximizing a generalized concave multiplicative function over a compact convex set. Since problem (P) does not seem to have been studied previously, the algorithm is apparently the first algorithm to be proposed for solving this problem. It works by globally solving a problem (P1) equivalent to problem (P). The branch-and-bound search undertaken by the algorithm uses rectangular partitioning and takes place in a space which typically has a much smaller dimension than the space to which the decision variables of problem (P) belong. Convergence of the algorithm is shown; computational considerations and benefits for users of the algorithm are given. A sample problem is also solved.     

The inverse solution of the atomic mixing equations by an operator-splitting method

The quantification problem of recovering the original material distribution from secondary ion mass spectrometry (SIMS) data is considered in this paper. It is an inverse problem, is ill-posed and hence it requires a special technique for its solution. The quantification problem is essentially an inverse diffusion or (classically) a backward heat conduction problem. In this paper an operator-splitting method (that is proposed in a previous paper by the first author for the solution of inverse diffusion problems) is developed for the solution of the problem of recovering the original structure from the SIMS data. A detailed development of the quantification method is given and it is applied to typical data to demonstrate its effectiveness.     

Non-stationary problem of active sound control in bounded domains

The present paper deals with the non-stationary problem of active shielding of a domain from undesirable external sources of noise. Active shielding is achieved by constructing additional (secondary) sources in such a way that the total contribution of all sources leads to the desirable effect. The problem is formulated as an inverse source problem with the secondary sources positioned outside the domain to be shielded. Along with the undesirable field (noise) to be shielded the presence of a desirable component (“friendly” sound) is accepted in the analysis. The constructed solution of the problem requires only the knowledge of the total field (noise) on the perimeter of the shielded domain. Some important aspects of the problem are addressed in the paper for the first time, such as the non-stationary formulation of the problem, existence of the resonance regimes and sensitivity of the solution to the input errors. The obtained solution is applicable to aeroacoustics problems.     

一类抛物型方程系数反问题的分裂算法

考虑利用终端时刻的温度u(x,T)=Z_T(x)反演热传导方程u_t-a~2u_(xx) q(x)u=0,x∈(0,1)中的未知系数q(x)的反问题.通过引进变换v(x,t)=(u_t(x,t)/u(x,t))将此非线性不适定问题的求解分解为两步.首先利用输入数据迭代求解一个非线性的正问题(该过程独立于未知系数),得到其迭代解v~(k)(x,t).其次利用q(x)与v(x,t)的关系式求出q(x)的近似解.对提出的反演方法,证明了采用的变换的可行性,得到了原反问题与由变换后的非线性正问题反演q(x)的等价性并且证明了迭代解的收敛性,给出了收敛速度.数值结果表明了该方法的有效性.     

An all-linear programming relaxation algorithm for optimizing over the efficient set

The problem (P) of optimizing a linear function over the efficient set of a multiple objective linear program has many important applications in multiple criteria decision making. Since the efficient set is in general a nonconvex set, problem (P) can be classified as a global optimization problem. Perhaps due to its inherent difficulty, it appears that no precisely-delineated implementable algorithm exists for solving problem (P) globally. In this paper a relaxation algorithm is presented for finding a globally optimal solution for problem (P). The algorithm finds an exact optimal solution to the problem after a finite number of iterations. A detailed discussion is included of how to implement the algorithm using only linear programming methods. Convergence of the algorithm is proven, and a sample problem is solved.Research supported by a grant from the College of Business Administration, University of Florida, Gainesville, Florida, U.S.A.     

Maximum weight archipelago subgraph problem

This paper is devoted to a new problem of combinatorial optimization. The problem is called Maximum Weight Archipelago Subgraph Problem (MWASP). Archipelago is a signed graph such that the negative edges connect the components of the graph of the positive edges. The new problem is to find a subset of edges in a weighted signed graph such that (i) if the edges of the subset are deleted from the graph then the remaining graph is an archipelago; and (ii) the subset has minimal total weight among the subsets having property (i). The problem is NP-complete, however a polynomial algorithm is provided to obtain the maximal weight of an edge what is still necessary to delete. The problem MWAP is used to analyze the relation of the blue chips of the Dow Jones Index.     

Using clustering analysis in a capacitated location-routing problem

The location routing problem (LRP) appears as a combination of two difficult problems: the facility location problem (FLP) and the vehicle routing problem (VRP). In this work, we consider a discrete LRP with two levels: a set of potential capacitated distribution centres (DC) and a set of ordered customers. In our problem we intend to determine the set of installed DCs as well as the distribution routes (starting and ending at the DC). The problem is also constrained with capacities on the vehicles. Moreover, there is a homogeneous fleet of vehicles, carrying a single product and each customer is visited just once. As an objective we intend to minimize the routing and location costs.     

A tabu search heuristic for solving the CLSP with backlogging and set-up carry-over

In this paper, the multi-item, single-level, capacitated, dynamic lot sizing problem with set-up carry-over and backlogging, abbreviated to CLSP⁺, is considered. The problem is formulated as a mixed integer programming problem. A heuristic method consisting of four elements: (1) a demand shifting rule, (2) lot size determination rules, (3) checking feasibility conditions and (4) set-up carry-over determination, provides us with an initial feasible solution. The resulting feasible solution is improved by adopting the corresponding set-up and set-up carry-over schedule and re-optimizing it by solving a minimum-cost network flow problem. Then the improved solution is used as a starting solution for a tabu search procedure, with the value of moves assessed using the same minimum-cost network problem. Computational results on randomly generated problems show that the algorithm, which is coded in C++, is able to provide optimal solutions or solutions extremely close to optimal. The computational efficiency makes it possible to solve reasonably large problem instances routinely on a personal computer.     

Global optimization for the sum of generalized polynomial fractional functions

In this paper, a branch and bound approach is proposed for global optimization problem (P) of the sum of generalized polynomial fractional functions under generalized polynomial constraints, which arises in various practical problems. Due to its intrinsic difficulty, less work has been devoted to globally solving this problem. By utilizing an equivalent problem and some linear underestimating approximations, a linear relaxation programming problem of the equivalent form is obtained. Consequently, the initial non-convex nonlinear problem (P) is reduced to a sequence of linear programming problems through successively refining the feasible region of linear relaxation problem. The proposed algorithm is convergent to the global minimum of the primal problem by means of the solutions to a series of linear programming problems. Numerical results show that the proposed algorithm is feasible and can successfully be used to solve the present problem (P).     

树的线图的图扩充问题

图G的弦图扩充问题包含两个问题:图G的最小填充问题和树宽问题,分别表示为f(G)和TW(G);图G的区间图扩充问题也包含两个问题:侧廓问题和路宽问题,分别表示为P(G)和PW(G).对一般图而言,它们都是NP-困难问题.一些特殊图类的填充数、树宽、侧廓问题和路宽具体值已被求出.主要研究树T的线图L(T)的弦图扩充问题;其次涉及到了两类特殊树—毛虫树和直径为4的树的线图的区间图扩充问题.     

Global optimization for the Biaffine Matrix Inequality problem

It has recently been shown that an extremely wide array of robust controller design problems may be reduced to the problem of finding a feasible point under a Biaffine Matrix Inequality (BMI) constraint. The BMI feasibility problem is the bilinear version of the Linear (Affine) Matrix Inequality (LMI) feasibility problem, and may also be viewed as a bilinear extension to the Semidefinite Programming (SDP) problem. The BMI problem may be approached as a biconvex global optimization problem of minimizing the maximum eigenvalue of a biaffine combination of symmetric matrices. This paper presents a branch and bound global optimization algorithm for the BMI. A simple numerical example is included. The robust control problem, i.e., the synthesis of a controller for a dynamic physical system which guarantees stability and performance in the face of significant modelling error and worst-case disturbance inputs, is frequently encountered in a variety of complex engineering applications including the design of aircraft, satellites, chemical plants, and other precision positioning and tracking systems.     

A closed-form solution to the problem of optimal tool-path generation for sculptured surface machining on multi-axis NC machine

The topic of the paper is in the field of sculptured surface machining (SSM) on multi-axis NC machines. It presents novel results of investigation of tool-path generation for sculptured surface machining on multi-axis NC machines. The purpose of the paper is to develop an integral form of solution to the problem of optimal tool-path generation. The concept of time-minimal tool-paths is introduced, as well as the optimization problem being formulated analytically. The problem of optimization is subdivided into the following three partial sub-problems: (a) the problem of local tool-path generation; (b) the problem of regional tool-path generation, and finally, (c) the problem of global tool-path generation. The paper presents a closed-form solution to the first two sub-problems. A solution to the problem of optimal tool-path generation is given in the form of an integral equation. The obtained solution enables one to retain the optimal cutter configuration (i.e., the cutter position, and the cutter orientation), as well as the optimal instant direction of feed-rate at every cutter location-point (further, CC-point).     

Finite Element Approximation of Fluid-Structure Interaction with Coupled Wave Propagation

In this contribution, a concept of coupling the fluid-structure interaction (FSI) with an ultrasonic wave propagation is proposed. It is referred to as the extended Fluid-Structure Interaction (eXFSI) problem. The eXFSI is a one-directional coupling of typical FSI problem with an ultrasonic wave propagation in fluid-solid and their interaction (WpFSI). Notably, the WpFSI is a strongly coupled problem of acoustic and elastic wave equations and automatically adopts the boundary conditions from the FSI problem at each time step. To the best of our knowledge, such a model is novel in the literature. The principal aim we pursue is to explore and develop concept of the efficient numerical solution of the eXFSI problem. The solution of the eXFSI and WpFSI models constitute an important part of on-live and off-live structural health monitoring (SHM) systems design for composite material and lightweight structures. (© 2017 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Minimization of Total Absolute Flow Time Deviation in Single and Multiple Machine Scheduling

In this note, single machine scheduling and minimizing absolute flow time deviation (TAFD) are considered. The relationship between this problem and the mean absolute deviation of job completion times about a common due date (MAD) is discussed. Based on the MAD problem optimal solutions of the TAFD problem are given. Furthermore, the generalization of the problem to the multiple machine case is discussed and an efficient algorithm for generating many optimal solutions of the problem, in the multi-machine case, is given.     

Semi-Infinite Programming and Applications to Minimax Problems

A minimisation problem with infinitely many constraints – semi-infinite programming problem (SIP) is considered. The problem is solved using a two stage procedure that searches for global maximum violation of the constraints. A version of the algorithm that searches for any violation of constraints is also considered, and the performance of the two algorithm is compared. An application to solving minimax problem (with and without coupled constraints) is given and a comparison with the algorithm for continuous minimax of Rustem and Howe (2001) is included. Finally, we consider an application to chemical engineering problems.     

Order-Value Optimization: Formulation and solution by means of a primal cauchy method

The Order-Value Optimization (OVO) problem is a generalization of the classical Minimax problem. Instead of the maximum of a set functions, the functional value that ranks in the p-th place is minimized. The problem seeks the application to (non-pessimistic) decision making and to model fitting in the presence of (perhaps systematic) outliers. A Cauchy-type method is introduced that solves the problem in the sense that every limit point satisfies an adequate optimality condition. Numerical examples are given.This author was supported by FAPESP (Grant 01/05492-1) and CNPq (Grant 301115/96-6)This author was supported by PRONEX, FAPESP (PT 2001-04597-4)     

A new method for solving the nonlinear second-order boundary value differential equations

In this paper we use measure theory to solve a wide range of second-order boundary value ordinary differential equations. First, we transform the problem to a first order system of ordinary differential equations (ODE’s) and then define an optimization problem related to it. The new problem is modified into one consisting of the minimization of a linear functional over a set of Radon measures; the optimal measure is then approximated by a finite combination of atomic measures and the problem converted approximatly to a finite-dimensional linear programming problem. The solution to this problem is used to construct the approximate solution of the original problem. Finally we get the error functionalE (we define in this paper) for the approximate solution of the ODE’s problems.     

The equilibrium generalized assignment problem and genetic algorithm

The well-known generalized assignment problem (GAP) is to minimize the costs of assigning n jobs to m capacity constrained agents (or machines) such that each job is assigned to exactly one agent. This problem is known to be NP-hard and it is hard from a computational point of view as well. In this paper, follows from practical point of view in real systems, the GAP is extended to the equilibrium generalized assignment problem (EGAP) and the equilibrium constrained generalized assignment problem (ECGAP). A heuristic equilibrium strategy based genetic algorithm (GA) is designed for solving the proposed EGAP. Finally, to verify the computational efficiency of the designed GA, some numerical experiments are performed on some known benchmarks. The test results show that the designed GA is very valid for solving EGAP.     

A branch-and-price algorithm for the capacitated facility location problem

The capacitated facility location problem (CFLP) is a well-known combinatorial optimization problem with applications in distribution and production planning. It consists in selecting plant sites from a finite set of potential sites and in allocating customer demands in such a way as to minimize operating and transportation costs. A number of solution approaches based on Lagrangean relaxation and subgradient optimization has been proposed for this problem. Subgradient optimization does not provide a primal (fractional) optimal solution to the corresponding master problem. However, in order to compute optimal solutions to large or difficult problem instances by means of a branch-and-bound procedure information about such a primal fractional solution can be advantageous. In this paper, a (stabilized) column generation method is, therefore, employed in order to solve a corresponding master problem exactly. The column generation procedure is then employed within a branch-and-price algorithm for computing optimal solutions to the CFLP. Computational results are reported for a set of larger and difficult problem instances.