The augmented Lagrangian method for a type of inverse quadratic programming problems over second-order cones

The focus of this paper is on studying an inverse second-order cone quadratic programming problem, in which the parameters in the objective function need to be adjusted as little as possible so that a known feasible solution becomes the optimal one. We formulate this problem as a minimization problem with cone constraints, and its dual, which has fewer variables than the original one, is a semismoothly differentiable (SC ¹) convex programming problem with both a linear inequality constraint and a linear second-order cone constraint. We demonstrate the global convergence of the augmented Lagrangian method with an exact solution to the subproblem and prove that the convergence rate of primal iterates, generated by the augmented Lagrangian method, is proportional to 1/r, and the rate of multiplier iterates is proportional to $1/\sqrt{r}$ , where r is the penalty parameter in the augmented Lagrangian. Furthermore, a semismooth Newton method with Armijo line search is constructed to solve the subproblems in the augmented Lagrangian approach. Finally, numerical results are reported to show the effectiveness of the augmented Lagrangian method with both an exact solution and an inexact solution to the subproblem for solving the inverse second-order cone quadratic programming problem.     

Reoptimizing the 0-1 knapsack problem

In this paper we study the problem where an optimal solution of a knapsack problem on n items is known and a very small number k of new items arrive. The objective is to find an optimal solution of the knapsack problem with n+k items, given an optimal solution on the n items (reoptimization of the knapsack problem). We show that this problem, even in the case k=1, is NP-hard and that, in order to have effective heuristics, it is necessary to consider not only the items included in the previously optimal solution and the new items, but also the discarded items. Then, we design a general algorithm that makes use, for the solution of a subproblem, of an α-approximation algorithm known for the knapsack problem. We prove that this algorithm has a worst-case performance bound of , which is always greater than α, and therefore that this algorithm always outperforms the corresponding α-approximation algorithm applied from scratch on the n+k items. We show that this bound is tight when the classical Ext-Greedy algorithm and the algorithm are used to solve the subproblem. We also show that there exist classes of instances on which the running time of the reoptimization algorithm is smaller than the running time of an equivalent PTAS and FPTAS.     

Involutive solutions for toda and langmuir lattices through nonlinearization of lax pairs

Under the constraint determined by a relation (a _n ,b _n )^T={f(?)} _n between the reflectionless potentials and the eigenfunctions of the general discrete Schrödinger eigenvalue problem, the Lax pair of the Toda lattice is nonlinearized to be a finite-dimensional difference system and a nonlinear evolution equation, while the solution varietyN of the former is an invariant set of S-flows determined by the latter, and the constants of the motion for the algebraic system are presented.f maps the solution of the algebraic system into the solution of a certain stationary Toda equation. Similar results concerning the Langmuir lattice are given, and a relation between the two difference systems, which are the spatial parts of the nonlinearized Lax pairs of the Toda lattice and Langmuir lattice, is discussed.     

Approximate methods for convex minimization problems with series–parallel structure

Consider a problem of minimizing a separable, strictly convex, monotone and differentiable function on a convex polyhedron generated by a system of m linear inequalities. The problem has a series–parallel structure, with the variables divided serially into n disjoint subsets, whose elements are considered in parallel. This special structure is exploited in two algorithms proposed here for the approximate solution of the problem. The first algorithm solves at most min{m, ν − n + 1} subproblems; each subproblem has exactly one equality constraint and at most n variables. The second algorithm solves a dynamically generated sequence of subproblems; each subproblem has at most ν − n + 1 equality constraints, where ν is the total number of variables. To solve these subproblems both algorithms use the authors’ Projected Newton Bracketing method for linearly constrained convex minimization, in conjunction with the steepest descent method. We report the results of numerical experiments for both algorithms.     

Lagrangean relaxation for a lower bound to a set partitioning problem with side constraints: properties and algorithms

The problem (P) addressed here is a special set partitioning problem with two additional non-trivial constraints. A Lagrangean Relaxation (LR_u) is proposed to provide a lower bound to the optimal solution to this problem. This Lagrangean relaxation is accomplished by a subgradient optimization procedure which solves at each iteration a special 0–1 knapsack problem (KP-k). We give two procedures to solve (KP-k), namely an implicity enumeration algorithm and a column generation method. The approach is promising for it provides feasible integer solutions to the side constraints that will hopefully be optimal to most of the instances of the problem (P). Properties of the feasible solutions to (KP-k) are highlighted and it is shown that the linear programming relaxation to this problem has a worst case time bound of order O(n³).     

Chance constrained bottleneck spanning tree problem

In this paper we consider a stochastic version of the bottleneck spanning tree in which edge costs are independent random variables. Our problem is to find an optimal spanning tree and optimal satisficing level of the chance constraint with respect to the bottleneck (maximum cost) edge of the spanning tree. The problem is first transformed into a deterministic equivalent problem. Then a subproblem in order to solve the problem is introduced and the close relation between these problems is clarified. Finally, based on the relation, polynomial time solution procedures to solve the problem are proposed under two special functions of satisficing level which are given as examples to be solved easily.     

An O(n2) simplex algorithm for a class of linear programs with tree structure

In connection with the optimal design of centralized circuit-free networks linear 0–1 programming problems arise which are related to rooted trees. For each problem the variables correspond to the edges of a given rooted tree T. Each path from a leaf to the root of T, together with edge weights, defines a linear constraint, and a global linear objective is to be maximized. We consider relaxations of such problems where the variables are not restricted to 0 or 1 but are allowed to vary continouosly between these bounds. The values of the optimal solutions of such relaxations may be used in a branch and bound procedure for the original 0–1 problem. While in [10] a primal algorithm for these relaxations is discussed, in this paper, we deal with the dual linear program and present a version of the simplex algorithm for its solution which can be implemented to run in time O(n²). For balanced trees T this time can be reduced to O(n log n).     

An efficient linearization technique for mixed 0-1 polynomial problem

This paper addresses a new and efficient linearization technique to solve mixed 0-1 polynomial problems to achieve a global optimal solution. Given a mixed 0-1 polynomial term z=c_tx₁x₂…x_ny, where x₁,x₂,…,x_n are binary (0-1) variables and y is a continuous variable. Also, c_t can be either a positive or a negative parameter. We transform z into a set of auxiliary constraints which are linear and can be solved by exact methods such as branch and bound algorithms. For this purpose, we will introduce a method in which the number of additional constraints is decreased significantly rather than the previous methods proposed in the literature. As is known in any operations research problem decreasing the number of constraints leads to decreasing the mathematical computations, extensively. Thus, research on the reducing number of constraints in mathematical problems in complicated situations have high priority for decision makers. In this method, each n-auxiliary constraints proposed in the last method in the literature for the linearization problem will be replaced by only 3 novel constraints. In other words, previous methods were dependent on the number of 0-1 variables and therefore, one auxiliary constraint was considered per 0-1 variable, but this method is completely independent of the number of 0-1 variables and this illustrates the high performance of this method in computation considerations. The analysis of this method illustrates the efficiency of the proposed algorithm.     

Exterior penalty in optimal control problem with state-control constraints

We consider an abstract optimal control problem with additional equality and inequality state and control constraints, we use the exterior penalty function to transform the constrained optimal control problem into a sequence of unconstrained optimal control problems, under conditions in control lie in L ₁, the sequence of the solution to the unconstrained problem contains a subsequence converging of the solution of constrained problem, this convergence is strong when the problemis non convex, and is weak if the problemis convex in control. This generalizes the results of P.Nepomiastcthy [4] where he considered the control in the Hilbert space L ²(I,? ^m ).     

On Existence for Polynomial-Like Iterative Equations

Many known results on the iterative equation α_i=1 ⁿ λ_i?ⁱ(x) = F(x) require a condition that λ₁ > 0 for technical reasons. A problem on the existence of solutions of this iterative equation with the natural restriction λ_n ≠ 0 is raised. In this paper we study an auxiliary functional equation for its invertible solutions. Then we apply our results on the auxiliary equation to solve the problem in some cases.     

Rectilinear line segment intersection,layered segment trees,and dynamization

The aim of the present paper is to provide an efficient solution to the following problem: “Given a family of n rectilinear line segments in two-space report all intersections in the family with a query consisting of an arbitrary rectilinear line segment.” We provide an algorithm which takes O(nlog₂n) preprocessing time, o(nlog₂n) space and O(log₂n + k) query time, where k is the number of reported intersections. This solution serves to introduce a powerful new data structure, the layered segment tree, which is of independent interest. Second it yields, by way of recent dynamization techniques, a solution to the on-line version of the above problem, that is the operations INSERT and DELETE and QUERY with a line segment are allowed. Third it also yields a new nonscanning solution to the batched version of the above problem. Finally we apply these techniques to the problem obtained by replacing “line segment” by “rectangle” in the above problem, giving an efficient solution in this case also.     

Three-stage flow-shop scheduling with assembly operations to minimize the weighted sum of product completion times

A modified flow-shop scheduling problem for a production system, characterized by parts machining followed by their subsequent assembly (joining) operation, is studied. Several products of different kinds are ordered. Each part for the products is processed on machine M₁ (the first stage) and then processed on machine M₂ (the second stage). Each product is processed (e.g., joined) with the parts by one assembly operation on assembly stage M_A (the third stage). The objective function to be minimized is the weighted sum of product completion times. The decision variables are the sequence of products to be assembled and the sequence of parts to be processed. In this paper, we assume that if product h is assembled before product h^′, then, on each machine, processing of any part for product h^′ is done after processing of all parts for product h is completed. We call this assumption “Assumption B(2)” and call this problem “SP_constrained”. An efficient solution procedure using a branch and bound method is developed based on this assumption, where Johnson's algorithm is used as a part of the solution procedure. Computational experiments are provided to evaluate the performance of the solution procedure. It has been found that the proposed solution procedure is effective to obtain an optimal or ε-optimal solution for larger-scaled problems. We further compare the optimal value for SP_constrained with the optimal value for another problem SP_{unconstrained} defined without Assumption B(2); the optimal solution for SP_{unconstrained} being significantly more difficult to obtain. We offer three propositions to analyze some special cases in which the difference between the optimal value of SP_constrained and the optimal value of SP_{unconstrained} is zero. For general cases, we make some computational experiments to evaluate the difference between the optimal value of SP_constrained and the optimal value of SP_{unconstrained}. It has been found that the difference is very small.     

Formulations and Benders decomposition algorithms for multidepot salesmen problems with load balancing

This paper describes new models and exact solution algorithms for the fixed destination multidepot salesmen problem defined on a graph with n nodes where the number of nodes each salesman is to visit is restricted to be in a predefined range. Such problems arise when the time to visit a node takes considerably longer as compared to the time of travel between nodes, in which case the number of nodes visited in a salesman’s tour is the determinant of their ‘load’. The new models are novel multicommodity flow formulations with O(n²) binary variables, which is contrary to the existing formulations for the same (and similar) problems that typically include O(n³) binary variables. The paper also describes Benders decomposition algorithms based on the new formulations for solving the problem exactly. Results of the computational experiments on instances derived from TSPLIB show that some of the proposed algorithms perform remarkably well in cases where formulations solved by a state-of-the-art optimization code fail to yield optimal solutions within reasonable computation time.     

An asymptotically exact algorithm for one modification of planar three-index assignment problem

An m-layer three-index assignment problem is considered which is a modification of the classical planar three-index assignment problem. This problem is NP-hard for m ? 2. An approximate algorithm, solving this problem for 1 < m < n/2, is suggested. The bounds on its quality are proved in the case when the input data (the elements of an m × n × n matrix) are independent identically distributed random variables whose values lie in the interval [a _n, b _n], where b _n > a _n > 0. The time complexity of the algorithm is O(mn ² + m ^7/2). It is shown that in the case of a uniform distribution (and also a distribution of minorized type) the algorithm is asymptotically exact if m = Θ(n ^{1 ? θ} ) and b _n/a _n = o(n ^θ) for every constant θ, 0 < θ < 1.     

Approximation de la L1-distance de Wasserstein

In this Note, we show that an optimal coupling for the L¹-Wasserstein distance, in the case of ℝⁿ space, can be obtained via the resolution of nonlinear equation g(·) = α, where g is a cyclically monotone application. Hence, to get an approximation to the optimal coupling, it suffices to construct a sequence (x_n)_n >0 that converges to the solution of the previous equation.     

Hilbert series of invariants, constant terms and Kostka-Foulkes polynomials

A problem that arose in the study of the mass of the neutrino led us to the evaluation of a constant term with a variety of ramifications into several areas from Invariant Theory, Representation Theory, the Theory of Symmetric Functions and Combinatorics. A significant by-product of our evaluation is the construction of a trigraded Cohen Macaulay basis for the Invariants under an action of SL_n(C) on a space of 2n+n² variables.     

Complexity and structure of near-minimal contact circuits for elementary symmetric functions

The paper studies the problem of the synthesis of contact circuits for elementary symmetric functions. The structure of minimal contact circuits realizing elementary symmetric functions is established and the estimates of the complexity of the obtained circuits, which are accurate to within an additive constant, are determined. It is proved that, for substantially large n, the complexity of an elementary symmetric function of n variables with the working number w satisfies the relation L(s _n ^w ) = (2w + 1)n ? B _w , whereB _w is a nonnegative constant.     

The 1-median and 1-highway problem

In this paper we study a facility location problem in the plane in which a single point (median) and a rapid transit line (highway) are simultaneously located in order to minimize the total travel time of the clients to the facility, using the L₁ or Manhattan metric. The highway is an alternative transportation system that can be used by the clients to reduce their travel time to the facility. We represent the highway by a line segment with fixed length and arbitrary orientation. This problem was introduced in [Computers & Operations Research 38(2) (2011) 525–538]. They gave both a characterization of the optimal solutions and an algorithm running in O(n³logn) time, where n represents the number of clients. In this paper we show that the previous characterization does not work in general. Moreover, we provide a complete characterization of the solutions and give an algorithm solving the problem in O(n³) time.