Successive Linear Approximation Procedure for Generalized Fixed-Charge Transportation Problems

In this paper, we develop a new heuristic procedure for solving a generalization of the fixed-charge transportation problem in which there are resource losses in addition to the fixed charges. The losses may be evaporation losses when the commodity is a liquid, heat losses in an electrical distribution network, or deterioration losses in distribution networks involving perishable commodities such as, for example, food items. The proposed procedure consists of solving a sequence of pro-rated problems. It is different from heuristic procedures that have been developed for solving the standard fixed charge transportation problem, in that it is not based on extreme point enumeration. We experiment with problems involving up to 2100 arcs with fixed charges and resource losses. The results show that the proposed approach is viable for solving medium-to-large sized problems.     

Asymptotic efficiency analysis on the modified Paulson’s procedure with a PAC guarantee

While solving large-scale ranking-and-selection (R&S) problems, the statistical validities of many existing fully-sequential R&S procedures may no longer hold. With a few modifications on a classical fully-sequential procedure, Paulson’s procedure, it can provide the probably approximately correct (PAC) guarantee which is a good fit for large-scale R&S problems. To provide the PAC guarantee, the modified procedure loses some efficiency on the total sample size. In this paper, we show, both theoretically and numerically, that the efficiency loss is tolerable.     

An alternative technique for solving a coupled PDE system in interphase heat transfer

Recently an accelerated iterative procedure was studied for solving a coupled partial differential equation system in interphase heat transfer to improve some existing iterative procedures in the literature. In that procedure, at each step of the iteration one has to evaluate the derivative of a well-known function at a new point. In this paper, an alternative approach is proposed in which one has to evaluate the derivative only once throughout the procedure. The proposed new iterative scheme also has the same order of convergence and takes lesser number of iterations for certain benchmark problems. An interesting theoretical study on the monotone convergence as well as error estimate of the proposed iterative procedure are provided for continuous as well as discretized problems. The proposed iterative procedure also supplements the existence and uniqueness of the solution in both the cases. A comparative numerical study is also done to demonstrate the efficacy of the proposed scheme.     

Minimizing the sum of squares lateness on a single machine

This paper proposes a new procedure that considers the use of inserted idle time to optimally solve the single machine scheduling problem where the objective is to minimize the sum of squares lateness. A heuristic procedure is also proposed for this problem. These procedures and an existing procedure developed by Gupta and Sen are tested using problems of various sizes in terms of the number of jobs to be scheduled and for different degrees of due date tightness. The performance measures are CPU time and sum of squares lateness of the solutions generated. The results show that a simple descent procedure yields very good results and is efficient even on large problems.     

Optimization of unconstrained functions with sparse hessian matrices-newton-type methods

Newton-type methods for unconstrained optimization problems have been very successful when coupled with a modified Cholesky factorization to take into account the possible lack of positive-definiteness in the Hessian matrix. In this paper we discuss the application of these method to large problems that have a sparse Hessian matrix whose sparsity is known a priori. Quite often it is difficult, if not impossible, to obtain an analytic representation of the Hessian matrix. Determining the Hessian matrix by the standard method of finite-differences is costly in terms of gradient evaluations for large problems. Automatic procedures that reduce the number of gradient evaluations by exploiting sparsity are examined and a new procedure is suggested. Once a sparse approximation to the Hessian matrix has been obtained, there still remains the problem of solving a sparse linear system of equations at each iteration. A modified Cholesky factorization can be used. However, many additional nonzeros (fill-in) may be created in the factors, and storage problems may arise. One way of approaching this problem is to ignore fill-in in a systematic manner. Such technique are calledpartial factorization schemes. Various existing partial factorization are analyzed and three new ones are developed. The above algorithms were tested on a set of problems. The overall conclusions were that these methods perfom well in practice.     

Quasi-human seniority-order algorithm for unequal circles packing

In the existing methods for solving unequal circles packing problems, the initial configuration is given arbitrarily or randomly, but the impact of different initial configurations for existing packing algorithm to the speed of existing packing algorithm solving unequal circles packing problems is very large. The quasi-human seniority-order algorithm proposed in this paper can generate a better initial configuration for existing packing algorithm to accelerate the speed of existing packing algorithm solving unequal circles packing problems. In experiments, the quasi-human seniority-order algorithm is applied to generate better initial configurations for quasi-physical elasticity methods to solve the unequal circles packing problems, and the experimental results show that the proposed quasi-human seniority-order algorithm can greatly improve the speed of solving the problem.     

Progress in the dual simplex method for large scale LP problems: practical dual phase 1 algorithms

The dual simplex algorithm has become a strong contender in solving large scale LP problems. One key problem of any dual simplex algorithm is to obtain a dual feasible basis as a starting point. We give an overview of methods which have been proposed in the literature and present new stable and efficient ways to combine them within a state-of-the-art optimization system for solving real world linear and mixed integer programs. Furthermore, we address implementation aspects and the connection between dual feasibility and LP-preprocessing. Computational results are given for a large set of large scale LP problems, which show our dual simplex implementation to be superior to the best existing research and open-source codes and competitive to the leading commercial code on many of our most difficult problem instances.     

Single machine earliness and tardiness scheduling

We examine the problem of scheduling a given set of jobs on a single machine to minimize total early and tardy costs without considering machine idle time. We decompose the problem into two subproblems with a simpler structure. Then the lower bound of the problem is the sum of the lower bounds of two subproblems. A lower bound of each subproblem is obtained by Lagrangian relaxation. Rather than using the well-known subgradient optimization approach, we develop two efficient multiplier adjustment procedures with complexity O(nlog n) to solve two Lagrangian dual subproblems. A branch-and-bound algorithm based on the two efficient procedures is presented, and is used to solve problems with up to 50 jobs, hence doubling the size of problems that can be solved by existing branch-and-bound algorithms. We also propose a heuristic procedure based on the neighborhood search approach. The computational results for problems with up to 3 000 jobs show that the heuristic procedure performs much better than known heuristics for this problem in terms of both solution efficiency and quality. In addition, the results establish the effectiveness of the heuristic procedure in solving realistic problems to optimality or near optimality.     

An evolutionary algorithm with the partial sequential forward floating search mutation for large-scale feature selection problems

Several meta-heuristic algorithms, such as evolutionary algorithms (EAs) and genetic algorithms (GAs), have been developed for solving feature selection problems due to their efficiency for searching feature subset spaces in feature selection problems. Recently, hybrid GAs have been proposed to improve the performance of conventional GAs by embedding a local search operation, or sequential forward floating search mutation, into the GA. Existing hybrid algorithms may damage individuals’ genetic information obtained from genetic operations during the local improvement procedure because of a sequential process of the mutation operation and the local improvement operation. Another issue with a local search operation used in the existing hybrid algorithms is its inappropriateness for large-scale problems. Therefore, we propose a novel approach for solving large-sized feature selection problems, namely, an EA with a partial sequential forward floating search mutation (EAwPS). The proposed approach integrates a local search technique, that is, the partial sequential forward floating search mutation into an EA method. Two algorithms, EAwPS-binary representation (EAwPS-BR) for medium-sized problems and EAwPS-integer representation (EAwPS-IR) for large-sized problems, have been developed. The adaptation of a local improvement method into the EA speeds up the search and directs the search into promising solution areas. We compare the performance of the proposed algorithms with other popular meta-heuristic algorithms using the medium- and large-sized data sets. Experimental results demonstrate that the proposed EAwPS extracts better features within reasonable computational times.     

A Globally Convergent and Efficient Method for Unconstrained Discrete-Time Optimal Control

Shift schemes are commonly used in non-convex situations when solving unconstrained discrete-time optimal control problems by the differential dynamic programming (DDP) method. However, the existing shift schemes are inefficient when the shift becomes too large. In this paper, a new method of combining the DDP method with a shift scheme and the steepest descent method is proposed to cope with non-convex situations. Under certain assumptions, the proposed method is globally convergent and has q-quadratic local conve rgence. Extensive numerical experiments on many test problems in the literature are reported. These numerical results illustrate the robustness and efficiency of the proposed method.     

Hybrid optimization procedure applied to optimal location finding for piezoelectric actuators and sensors for active vibration control

This paper presents an efficient hybrid optimization approach using a new coupling technique for solving the constrained optimization problems. This methodology is based on genetic algorithm, sequential quadratic programming and particle swarm optimization combined with a projected gradient techniques in order to correct the solutions out of domain and send them to the domain’s border. The established procedures have been successfully tested with some well known mathematical and engineering optimization problems, also the obtained results are compared with the existing approaches. It is clearly demonstrated that the solutions obtained by the proposed approach are superior to those of existing best solutions reported in the literature. The main application of this procedure is the location optimization of piezoelectric sensors and actuators for active control, the vibration of plates with some piezoelectric patches is considered. Optimization criteria ensuring good observability and controllability based on some main eigenmodes and residual ones are considered. Various rectangular piezoelectric actuators and sensors are used and two optimization variables are considered for each piezoelectric device: the location of its center and shape orientation. The applicability and effectiveness of the present methodological approach are demonstrated and the location optimization of multiple sensors and actuators are successfully obtained with some main modes and residual ones. The shape orientation optimization of sensors observing various modes as well as the local optimization of multiple sensors and actuators are numerically investigated. The effect of residual modes and the spillover reduction can be easily analyzed for a large number of modes and multiple actuators and sensors.     

Fixed point and Bregman iterative methods for matrix rank minimization

The linearly constrained matrix rank minimization problem is widely applicable in many fields such as control, signal processing and system identification. The tightest convex relaxation of this problem is the linearly constrained nuclear norm minimization. Although the latter can be cast as a semidefinite programming problem, such an approach is computationally expensive to solve when the matrices are large. In this paper, we propose fixed point and Bregman iterative algorithms for solving the nuclear norm minimization problem and prove convergence of the first of these algorithms. By using a homotopy approach together with an approximate singular value decomposition procedure, we get a very fast, robust and powerful algorithm, which we call FPCA (Fixed Point Continuation with Approximate SVD), that can solve very large matrix rank minimization problems (the code can be downloaded from http://www.columbia.edu/~sm2756/FPCA.htm for non-commercial use). Our numerical results on randomly generated and real matrix completion problems demonstrate that this algorithm is much faster and provides much better recoverability than semidefinite programming solvers such as SDPT3. For example, our algorithm can recover 1000 × 1000 matrices of rank 50 with a relative error of 10^?5 in about 3?min by sampling only 20% of the elements. We know of no other method that achieves as good recoverability. Numerical experiments on online recommendation, DNA microarray data set and image inpainting problems demonstrate the effectiveness of our algorithms.     

One-pass heuristics for large-scale unconstrained binary quadratic problems

Many significant advances have been made in recent years for solving unconstrained binary quadratic programs (UQP). As a result, the size of problem instances that can be efficiently solved has grown from a hundred or so variables a few years ago to 2000 or 3000 variables today. These advances have motivated new applications of the model which, in turn, have created the need to solve even larger problems. In response to this need, we introduce several new “one-pass” heuristics for solving very large versions of this problem. Our computational experience on problems of up to 9000 variables indicates that these methods are both efficient and effective for very large problems. The significance of problems of this size is that they not only open the door to solving a much wider array of real world problems, but also that the standard linear mixed integer formulations of the nonlinear models involve over 40,000,000 variables and three times that many constraints. Our approaches can be used as stand-alone solution methods, or they can serve as procedures for quickly generating high quality starting points for other, more sophisticated methods.     

An inexact alternating direction method of multipliers for the solution of linear complementarity problems arising from free boundary problems

A large number of free boundary problems can be formulated as linear-complementarity problems. In this paper, we propose an inexact alternating direction method of multipliers for solving linear complementarity problem arising from free boundary problems by using the special structure of these problems. The convergence of our proposed method is proved. Numerical results show that the proposed method is feasible and effective, and it is significantly faster than modified alternating direction implicit algorithm and many other methods, especially when dimension of the problem being solved is large.     

New exact method for large asymmetric distance-constrained vehicle routing problem

In this paper we revise and modify an old branch-and-bound method for solving the asymmetric distance–constrained vehicle routing problem suggested by Laporte et al. in 1987. Our modification is based on reformulating distance–constrained vehicle routing problem into a travelling salesman problem, and on using assignment problem as a lower bounding procedure. In addition, our algorithm uses the best-first strategy and new tolerance based branching rules. Since our method is fast but memory consuming, it could stop before optimality is proven. Therefore, we introduce the randomness, in case of ties, in choosing the node of the search tree. If an optimal solution is not found, we restart our procedure. As far as we know, the instances that we have solved exactly (up to 1000 customers) are much larger than the instances considered for other vehicle routing problem models from the recent literature. So, despite of its simplicity, this proposed algorithm is capable of solving the largest instances ever solved in the literature. Moreover, this approach is general and may be used for solving other types of vehicle routing problems.     

Assessing solution quality in stochastic programs

Determining whether a solution is of high quality (optimal or near optimal) is fundamental in optimization theory and algorithms. In this paper, we develop Monte Carlo sampling-based procedures for assessing solution quality in stochastic programs. Quality is defined via the optimality gap and our procedures' output is a confidence interval on this gap. We review a multiple-replications procedure that requires solution of, say, 30 optimization problems and then, we present a result that justifies a computationally simplified single-replication procedure that only requires solving one optimization problem. Even though the single replication procedure is computationally significantly less demanding, the resulting confidence interval might have low coverage probability for small sample sizes for some problems. We provide variants of this procedure that require two replications instead of one and that perform better empirically. We present computational results for a newsvendor problem and for two-stage stochastic linear programs from the literature. We also discuss when the procedures perform well and when they fail, and we propose using ɛ-optimal solutions to strengthen the performance of our procedures.     

Absalom: Balancing assembly lines with assignment restrictions

Assembly line balancing problems (ALBPs) arise whenever an assembly line is configured, redesigned or adjusted. An ALBP consists of distributing the total workload for manufacturing products among the work stations along the line. On the one hand, research has focussed on developing effective and fast solution methods for exactly solving the simple assembly line balancing problem (SALBP). On the other hand, a number of real-world extensions of SALBP have been introduced but solved with straight-forward and simple heuristics in many cases. Therefore, there is a lack of procedures for exactly solving such generalized ALBP.In this paper, we show how to extend the well-known solution procedure Salome [Scholl, A., Klein, R., 1997. Salome: A bidirectional branch-and-bound procedure for assembly line balancing. Informs J. Comput. 9 319–334], which is able to solve even large SALBP instances in a very effective manner, to a problem extension with different types of assignment restrictions (called ARALBP). The extended procedure, referred to as Absalom, employs a favorable branching scheme, an arsenal of bounding rules and a variety of logical tests using ideas from constraint programming.Computational experiments show that Absalom is a very promising exact solution approach although the additional assignment restrictions complicate the problem considerably and necessitate a relaxation of some components of Salome.     

A route-neighborhood-based metaheuristic for vehicle routing problem with time windows

In this paper, a two-stage metaheuristic based on a new neighborhood structure is proposed to solve the vehicle routing problem with time windows (VRPTW). Our neighborhood construction focuses on the relationship between route(s) and node(s). Unlike the conventional methods for parallel route construction, we construct routes in a nested parallel manner to obtain higher solution quality. Valuable information extracted from the previous parallel construction runs is used to enhance the performance of parallel construction. In addition, when there are only a few unrouted customers left, we design a special procedure for handling them. Computational results for 60 benchmark problems are reported. The results indicate that our approach is highly competitive with all existing heuristics, and in particular very promising for solving problems of large size.     

Solving (large scale) matching problems combinatorially

In this paper we describe computational results for a modification of the shortest augmenting path approach for solving large scale matching problems. Using a new assignment start procedure and the two-phase strategy, where first the problem is solved on a sparse subgraph and then reoptimization is used, matching problems on complete graphs with 1000 nodes are solved in about 10–15 seconds on an IBM 4361.This work was partially supported by Sonderforschungsbereich 303, University of Bonn, and a special grant from the Deutsche Forschungsgemeinschaft.     

Solution procedures for three-dimensional eddy current problems

The problem under consideration is that of the scattering of time periodic electromagnetic fields by metallic obstacles. A common approximation here is that in which the metal is assumed to have infinite conductivity. The resulting problem, called the perfect conductor problem, involves solving Maxwell's equations in the region exterior to the obstacle with the tangential component of the electric field zero on the obstacle surface. In the interface problem different sets of Maxwell equations must be solved in the obstacle and outside while the tangential components of both electric and magnetic fields are continuous across the obstacle surface. Solution procedures for this problem are given. There is an exact integral equation procedure for the interface problem and an asymptotic procedure for large conductivity. Both are based on a new integral equation procedure for the perfect conductor problem. The asymptotic procedure gives an approximate solution by solving a sequence of problems analogous to the one for perfect conductors.