Solving 0-1 Minimax Problems

It has been shown that it is possible to solve a minimax 0-1 programming problem by transforming the objective function coefficients and solving a minisum problem. This result is very useful for solving a ‘hard’ minimax problem when there exists a ‘relatively easy’ algorithm to solve the minisum problem. We discuss such problems and present a new transformation.     

A Parametric 1-Maximin Location Problem

We introduce a version of the weighted 1-maximin problem in a convex polygon, where the weights are functions of a parameter. The 1-maximin problem is applicable in the location of undesirable facilities. Its objective is to find an optimal location such that the minimum weighted distance to a given set of points is maximized. We show that the parametric 1-maximin problem is equivalent to a 1-minimax problem, where the costs are non-linearly decreasing functions of distance. Using different values of the parameter in the 1-maximin problem, one can model different disutility functions for the users of the facility. Furthermore, the parameterization provides for a systematic way of reducing the effects of the weights, resulting in the unweighted 1-maximin problem in the limit. For two example problems we construct the optimal trajectory as a function of the parameter, and demonstrate that the trajectory may be discontinuous.     

Duality Theory in Nonlinear Buckling Analysis for von Kármán Equations

The nonlinear eigenvalue problem in buckling analysis is studied for von Kármán plates. By using the general duality theory developed by Gao-Strang [1, 2] it is proved that the stability criterion for the bifurcated state depends on a reduced complementary gap function. The duality theory is established for nonlinear bifurcation problems. This theory shows that the nonlinear eigenvalue problem is eventually equivalent to a coupled quadratic dual optimization problem. A series of equivalent variational principles are constructed and a lower bound theorem for the first eigenvalue of the buckling factor is proved.     

An Algorithm for the 0-1 Equality Knapsack Problem

The 0-1 knapsack problem is a linear integer-programming problem with a single constraint and binary variables. The knapsack problem with an inequality constraint has been widely studied, and several efficient algorithms have been published. We consider the equality-constraint knapsack problem, which has received relatively little attention. We describe a branch-and-bound algorithm for this problem, and present computational experience with up to 10,000 variables. An important feature of this algorithm is a least-lower-bound discipline for candidate problem selection.     

The weighted euclidean 1-center problem

We present a polynomial algorithm for the weighted 1-center problem (indeed minimization of the ratio of convex quadratic and an affine function over a polyhedral set). In the location problem, the complexity is polynomial in the dimension of the space.     

Reducibility of minimax to minisum 0–1 programming problems

We consider 0–1 programming problems with a minimax objective function and any set of constraints. Upon appropriate transformations of its cost coefficients, such a minimax problem can be reduced to a linear minisum problem with the same set of feasible solutions such that an optimal solution to the latter will also solve the original minimax problem.Although this reducibility applies for any 0–1 programming problem, it is of particular interest for certain locational decision models. Among the obvious implications are that an algorithm for solving a p-median (minisum) problem in a network will also solve a corresponding p-center (minimax) problem.It should be emphasized that the results presented will in general only hold for 0–1 problems due to intrinsic properties of the minimax criterion.     

Elementary landscape decomposition of the 0-1 unconstrained quadratic optimization

Landscapes’ theory provides a formal framework in which combinatorial optimization problems can be theoretically characterized as a sum of an especial kind of landscape called elementary landscape. The elementary landscape decomposition of a combinatorial optimization problem is a useful tool for understanding the problem. Such decomposition provides an additional knowledge on the problem that can be exploited to explain the behavior of some existing algorithms when they are applied to the problem or to create new search methods for the problem. In this paper we analyze the 0-1 Unconstrained Quadratic Optimization from the point of view of landscapes’ theory. We prove that the problem can be written as the sum of two elementary components and we give the exact expressions for these components. We use the landscape decomposition to compute autocorrelation measures of the problem, and show some practical applications of the decomposition.     

Non-linear oscillations of a 1:1 resonance Hamiltonian system

The non-linear oscillations of an autonomous two-degree-of-freedom Hamiltonian system in the neighbourhood of its stable equilibrium position are considered. It is assumed that the Hamilton function is sign-definite in the neighbourhood of the equilibrium position and that the values of the frequencies of its linear oscillations are equal or close to one another (1:1 resonance). The investigation is carried out using the example of the problem of the motion of a dynamically symmetrical rigid body (satellite) about its centre of mass in a circular orbit in a central Newtonian gravitational field. In this problem there is relative equilibrium of the rigid body in the orbital system of coordinates, for which its axis of dynamic symmetry is directed along the velocity vector of the centre of mass. Resonance occurs when the ratio of the polar and equatorial principal central moments of inertia is equal to 4/3 or is close to it. The problem of the existence, bifurcation and orbital stability of the periodic motions of a rigid body generated from its relative equilibrium is solved. Some aspects of the existence of quasiperiodic motions are also considered.     

Solving the 0–1 proportional knapsack problem by sampling

In this paper, we deal with the proportional knapsack problem that is a variation on the ordinary knapsack problem. In the proportional knapsack problem, we look at filling an urn with objects having two characteristics: color and weight. The colors of the objects in the urn should be proportional to the distribution of the colors in the object universe, and the total weight of the objects in the urn should be as close as possible to the capacity of the urn. The formulation of the problem was motivated by a real-life application from the area of finance, called a dollar roll. We show that the proportional knapsack problem is NP-hard, and then, using sampling, develop a heuristic procedure for solving the problem.Partial support from the Fund for the Promotion of Research and from the Alexander Goldberg Memorial Fund at Technion is gratefully acknowledged.     

Untersuchungen zu speziellen linearen gemischt-ganzzahligen 0-1-optimierungsaufgaben

In this paper criteria for solution of a linear mixed-integer 0-1-programming -problem with one restriction and any coefficients in the objective function respectively in the restriction are given. Under certain conditions the given problem can be reduced to a mixed-integer problem of a special structure. An algorithm to solve this problem is described concisely.     

A core approach to the 0–1 equality knapsack problem

For the 0–1 knapsack problem with equality constraint a partitioning procedure is introduced which focuses on the core of the problem. The purpose of the procedure is to reduce the required preliminary sorting for large problem instances. Computational results are presented for an improved heuristic as well as for a complete (exact) algorithm showing the success of the core approach. Test problems of size up to 15–000 objects are solved within 400–ms on a standard personal computer, that is, within the time that is needed for sorting the profit-weight ratios. The core algorithm reduces the solution times by a factor of up to four for large problem instances.     

基于光滑化方法求解非线性l1问题

讨论了求解非线性l1问题的一种新的光滑函数法.通过对非线性l1问题模型的转化,将该问题化为一个不可微优化问题,据此提出了基于BFGS迭代的非线性l1问题的光滑函数法,介绍了非线性l1问题的光滑函数的有关性质、算法步骤及其收敛性.数值仿真显示了提出的光滑函数方法可以避免数值计算的溢出,具有一定的有效性.     

哈明距离下圈图上1-重心问题的反问题

主要讨论哈明距离下圈图上1-重心问题的反问题.1-重心问题的反问题主要研究如何尽可能少地改变网络中的参数值,使得给定的顶点到其它顶点的加权距离之和不超过一个给定的上界.通过将该问题转化为0-1背包问题,证明了在哈明距离下该问题是NP困难的,并运用动态规划的思想,在考虑改变边的长度的情况下,对圈图进行了求解.     

Inverse 1-median problem on trees under weighted Hamming distance

The inverse 1-median problem consists in modifying the weights of the customers at minimum cost such that a prespecified supplier becomes the 1-median of modified location problem. A linear time algorithm is first proposed for the inverse problem under weighted l _?? norm. Then two polynomial time algorithms with time complexities O(n log n) and O(n) are given for the problem under weighted bottleneck-Hamming distance, where n is the number of vertices. Finally, the problem under weighted sum-Hamming distance is shown to be equivalent to a 0-1 knapsack problem, and hence is ${\mathcal{NP}}$ -hard.     

Anisotropic diffusions with singular advections and absorptions part 1: existence

An anisotropic filtration problem with singular advections and strong absorptions, which leads to a quasi-linear degenerate parabolic equation in divergent form, is studied in this paper. The existence for the Cauchy problem as well as the first boundary-initial-value problem is proved.     

On conditions for optimality of the nonlinearl 1 problem

The purpose of this paper is to present necessary and sufficient conditions for optimality in the nonlinearl ₁ problem. Furthermore, the relationship of thel ₁ problem and the Pietrzykowski's approach to solve the nonlinear programming problem is discussed in detail.     

Feasibility and Solvability for Vector Complementarity Problems1

The purpose of this paper is to discuss the feasibility and solvability of vector complementarity problems. We prove that, under suitable conditions, the vector complementarity problem with a pseudomonotonicity assumption is solvable whenever it is strictly feasible. By strengthening the generalized monotonicity condition, we show also that the homogeneous vector complementarity problem is solvable whenever it is feasible. At last, we study the solvability of the vector complementarity problem on product spaces.The authors thank Professor Franco Giannessi for valuable comments and suggestions leading to improvements of this paper.     

非线性0-1规划问题的蜂群算法

针对非线性0-1规划,提出采用一种智能优化算法——蜂群算法进行求解.描述了蜂群算法的实现过程,并在计算机上编程予以实现.经大量实例测试,并与其它算法进行比较,获得了满意的结果.说明了蜂群算法在解决非线性0-1规划问题上的可行性与有效性,同时具有良好的优化能力..     

The 0–1 knapsack problem with multiple choice constraints

In this paper we consider the 0–1 knapsack problem with multiple choice constraints appended. Such a problem may arise in a capital budgeting context where only one project may be selected from a particular group of projects. Thus the problem is to choose one project from each group such that the budgetary constraint is satisfied and the maximum return is realized. We formulate two branch and bound algorithms which use two different relaxations as the primary bounding relaxations. In addition, theoretical results are given for a simple reduction in the number of variables in the problem.