No Dimension-Independent Core-Sets for Containment Under Homothetics

This paper deals with the containment problem under homothetics which has the minimal enclosing ball (MEB) problem as a prominent representative. We connect the problem to results in classic convex geometry and introduce a new series of radii, which we call core-radii. For the MEB problem, these radii have already been considered from a different point of view and sharp inequalities between them are known. In this paper sharp inequalities between core-radii for general containment under homothetics are obtained. Moreover, the presented inequalities are used to derive sharp upper bounds on the size of core-sets for containment under homothetics. In the MEB case, this yields a tight (dimension-independent) bound for the size of such core-sets. In the general case, we show that there are core-sets of size linear in the dimension and that this bound stays sharp even if the container is required to be symmetric.     

Validation of subgradient optimization

The “relaxation” procedure introduced by Held and Karp for approximately solving a large linear programming problem related to the traveling-salesman problem is refined and studied experimentally on several classes of specially structured large-scale linear programming problems, and results on the use of the procedure for obtaining exact solutions are given. It is concluded that the method shows promise for large-scale linear programming     

一类特殊二维0-1规划的广义指派模型求解

二维0-1整数规划模型应用广泛,对广义指派问题的研究,解决了一些二维0-1整数规划问题.但有些实际问题具有特殊上限约束,目前还没有对应的方法.针对该实际情形,本文建立了相应的数学模型,利用对指派模型的推广,求得问题最优解,从理论上解决了这一类特殊约束二维0-1整数规划的最优解求取问题.并通过算例说明了方法的使用.     

A dual algorithm for the one-machine scheduling problem

A branch and bound algorithm is presented for the problem of schedulingn jobs on a single machine to minimize tardiness. The algorithm uses a dual problem to obtain a good feasible solution and an extremely sharp lower bound on the optimal objective value. To derive the dual problem we regard the single machine as imposing a constraint for each time period. A dual variable is associated with each of these constraints and used to form a Lagrangian problem in which the dualized constraints appear in the objective function. A lower bound is obtained by solving the Lagrangian problem with fixed multiplier values. The major theoretical result of the paper is an algorithm which solves the Lagrangian problem in a number of steps proportional to the product ofn ² and the average job processing time. The search for multiplier values which maximize the lower bound leads to the formulation and optimization of the dual problem. The bounds obtained are so sharp that very little enumeration or computer time is required to solve even large problems. Computational experience with 20-, 30-, and 50-job problems is presented.     

Improvements of the Held—Karp algorithm for the symmetric traveling-salesman problem

A highly efficient algorithm (HK) devised by Held and Karp for solving the symmetric traveling-salesman problem was presented at the 7th Mathematical Programming Symposium in 1970 and published in Mathematical Programming in 1971. Its outstanding performance is due to a clever exploitation of the relationship between the traveling-salesman problem and minimum spanning trees.However, various improvements of their method have led to a version (IHK) which tends to be some 25 times faster than the original one. Experiments with data selected at random, ranging in size up to 80 cities, show that the computing time for IHK is roughly doubled as the number of cities is increased by 10.     

Efficient Solution of the Single-item,Capacitated Lot-sizing Problem with Start-up and Reservation Costs

A capacitated dynamic lot-sizing model, where the costs incurred are a start-up cost for switching the production facility on and another reservation cost for keeping the facility on, whether or not it is producing, is considered. The resulting scheduling problem is NP-hard. An efficient shortest path model of the uncapacitated version of the problem is developed. This model is then included, via a redefinition of variables, into a tight capacitated model; tight in the sense that sharp lower bounds can be produced from it. The lower bound problems are solved efficiently by recovering the shortest path structure through column generation, and effective upper bounds are generated by solving a small capacitated trans-shipment problem. The results of computational tests to verify the computational efficiency of the resulting solution scheme are presented.     

The equal flow problem

This paper presents a new algorithm for the solution of a network problem with equal flow side constraints. The solution technique is motivated by the desire to exploit the special structure of the side constraints and to maintain as much of the characteristics of pure network problems as possible. The proposed algorithm makes use of Lagrangean relaxation to obtain a lower bound and decomposition by right-hand-side allocation to obtain upper bounds. The lagrangean dual serves not only to provide a lower bound used to assist in termination criteria for the upper bound, but also allows an initial allocation of equal flows for the upper bound. The algorithm has been tested on problems with up to 1500 nodes and 6000 arcs. Computational experience indicates that solutions whose objective function value is well within 1% of the optimum can be obtained in 1%–65% of the MPSX time depending on the amount of imbalance inherent in the problem. Incumbent integer solutions which are within 99.99% feasible and well within 1% of the proven lower bound are obtained in a straightforward manner requiring, on the average, 30% of the MPSX time required to obtain a linear optimum.     

An algorithm for single machine sequencing with release dates to minimize total weighted completion time

Each of n jobs is to be processed without interruption on a single machine which can handle only one job at a time. Each job becomes available for processing at its release date, requires a processing time and has a positive weight. Given a processing order of the jobs, the earliest completion time for each job can be computed. The objective is to find a processing order of the jobs which minimizes the sum of weighted completion times. In this paper a branch and bound algorithm for the problem is derived. Firstly a heuristic is presented which is used in calculating the lower bound. Then the lower bound is obtained by performing a Lagrangean relaxation of the release date constraints; the Lagrange multipliers are chosen so that the sequence generated by the heuristic is an optimum solution of the relaxed problem thus yielding a lower bound. A method to increase the lower bound by deriving improved constraints to replace the original release date constraints is given. The algorithm, which includes several dominance rules, is tested on problems with up to fifty jobs. The computational results indicate that the version of the lower bound using improved constraints is superior to the original version.     

Scheduling preemptive open shops to minimize total tardiness

This article considers the problem of scheduling preemptive open shops to minimize total tardiness. The problem is known to be NP-hard. An efficient constructive heuristic is developed for solving large-sized problems. A branch-and-bound algorithm that incorporates a lower bound scheme based on the solution of an assignment problem as well as various dominance rules are presented for solving medium-sized problems. Computational results for the 2-machine case are reported. The branch-and-bound algorithm can handle problems of up to 30 jobs in size within a reasonable amount of time. The solution obtained by the heuristic has an average deviation of less than 2% from the optimal value, while the initial lower bound has an average deviation of less than 11% from the optimal value. Moreover, the heuristic finds approved optimal solutions for over 65% of the problems actually solved.     

Global optimization algorithm for sum of generalized polynomial ratios problem

In this paper, a global optimization algorithm is proposed for solving sum of generalized polynomial ratios problem (P) which arises in various practical problems. Due to its intrinsic difficulty, less work has been devoted to globally solve the problem (P). For such problems, we present a branch and bound algorithm. In this method, by utilizing exponent transformation and new three-level linear relaxation method, a sequence of linear relaxation programming of the initial nonconvex programming problem (P) are derived which are embedded in a branch and bound algorithm. The proposed method need not introduce new variables and constraints and it is convergent to the global minimum of prime problem by means of the subsequent solutions of a series of linear programming problems. Several numerical examples in the literatures are tested to demonstrate that the proposed algorithm can systematically solve these examples to find the approximate ?-global optimum.     

A regularization method for solving the Cauchy problem for the Helmholtz equation

In this paper, we investigate a Cauchy problem associated with Helmholtz-type equation in an infinite “strip”. This problem is well known to be severely ill-posed. The optimal error bound for the problem with only nonhomogeneous Neumann data is deduced, which is independent of the selected regularization methods. A framework of a modified Tikhonov regularization in conjunction with the Morozov’s discrepancy principle is proposed, it may be useful to the other linear ill-posed problems and helpful for the other regularization methods. Some sharp error estimates between the exact solutions and their regularization approximation are given. Numerical tests are also provided to show that the modified Tikhonov method works well.     

Global optima results for the Kauffman NK model

The Kauffman NK model has been used in theoretical biology, physics and business organizations to model complex systems with interacting components. Recent NK model results have focused on local optima. This paper analyzes global optima of the NK model. The resulting global optimization problem is transformed into a stochastic network model that is closely related to two well-studied problems in operations research. This leads to applicable strategies for explicit computation of bounds on the global optima particularly with K either small or close to N. A general lower bound, which is sharp for K = 0, is obtained for the expected value of the global optimum of the NK model. A detailed analysis is provided for the expectation and variance of the global optimum when K = N−1. The lower and upper bounds on the expectation obtained for this case show that there is a wide gap between the values of the local and the global optima. They also indicate that the complexity catastrophe that occurs with the local optima does not arise for the global optima.     

An algorithm for the min concave cost flow problem

A method is presented to solve that class of network flow problems, which may be formulated as one source - multiple destination minimum cost flow problems with concave costs. The global optimum is searched using a branch and bound procedure, in which the enumeration scheme is based on a characterization of the optimal solution set, while linear relaxations of the original problem provide lower bounds.     

A Rigorous Global Optimization Algorithm for Problems with Ordinary Differential Equations

The optimization of systems which are described by ordinary differential equations (ODEs) is often complicated by the presence of nonconvexities. A deterministic spatial branch and bound global optimization algorithm is presented in this paper for systems with ODEs in the constraints. Upper bounds for the global optimum are produced using the sequential approach for the solution of the dynamic optimization problem. The required convex relaxation of the algebraic functions is carried out using well-known global optimization techniques. A convex relaxation of the time dependent information is obtained using the concept of differential inequalities in order to construct bounds on the space of solutions of parameter dependent ODEs as well as on their second-order sensitivities. This information is then incorporated in the convex lower bounding NLP problem. The global optimization algorithm is illustrated by applying it to four case studies. These include parameter estimation problems and simple optimal control problems. The application of different underestimation schemes and branching strategies is discussed.     

Antiblocking systems and PD-sets

Since the permutation decoding algorithm is more efficient the smaller the size of the PD-set, it is important for the applications to find small PD-sets. A lower bound on the size of a PD-set is given by Gordon. There are examples for PD-sets, but up to now there is no method known to find PD-sets. The question arises whether the Gordon bound is sharp. To handle this problem we introduce the notion of antiblocking system and we show that there are examples where the Gordon bound is not sharp.     

关于共轭Goldberg问题的一点注记(英文)

对于(p,q)算子范数,我们考虑由Goldberg定义的常数c(称为Goldberg常数)的确定问题.该问题(即求常数c的精确值或它的一个可以达到的最小上界问题)由Moshe Goldberg于1986年提出,且至今仍未能彻底解决.本文给出了常数c的一个上界,改进了Goldberg在1986年所得出的结果.     

The Held—Karp algorithm and degree-constrained minimum 1-trees

In this note we propose to find a degree-constrained minimum 1-tree in the Held—Karp algorithm [5, 6] for the symmetric traveling-salesman problem, and show that it is reduced to finding a minimum common basis of two matroids.     

Reducing work-in-process movement for multiple products in one-dimensional layout problems

This research describes a method to assign M machines, which are served by a material handling transporter, to M equidistant locations along a track, so that the distance traveled by a given set of jobs is minimized. Traditionally, this problem (commonly known as a machine location problem) has been modeled as a quadratic assignment problem (QAP), which is NP-hard, thus motivating the need for efficient procedures to solve instances with several machines. In this paper we develop a branching heuristic to obtain sub-optimum solutions to the problem; a lower bound on the optimum solution has also been presented. Results obtained from the heuristics are compared with results obtained from other heuristics with similar objectives. It is observed that the results are promising, and justify the usage of developed methods.     

B-spline finite-element method in polar coordinates

A numerical solution method for two-dimensional electromagnetic field problems is presented using the B-spline finite-element expression based on polar coordinates. The technique has two main advantages: (1) to avoid the truncation errors at some curved boundaries and (2) to improve the accuracy of singular boundary-value problems with a sharp corner. The B-spline finite-element formulation in polar coordinates is derived and its numerical applications are illustrated by an eddy current problem and several waveguide eigenvalue problems.