Exact Algorithm for the Surrogate Dual of an Integer Programming Problem: Subgradient Method Approach

One of the critical issues in the effective use of surrogate relaxation for an integer programming problem is how to solve the surrogate dual within a reasonable amount of computational time. In this paper, we present an exact and efficient algorithm for solving the surrogate dual of an integer programming problem. Our algorithm follows the approach which Sarin et al. (Ref. 8) introduced in their surrogate dual multiplier search algorithms. The algorithms of Sarin et al. adopt an ad-hoc stopping rule in solving subproblems and cannot guarantee the optimality of the solutions obtained. Our work shows that this heuristic nature can actually be eliminated. Convergence proof for our algorithm is provided. Computational results show the practical applicability of our algorithm.     

Parallelization Strategies for Rollout Algorithms

Rollout algorithms are innovative methods, recently proposed by Bertsekas et al. [3], for solving NP-hard combinatorial optimization problems. The main advantage of these approaches is related to their capability of magnifying the effectiveness of any given heuristic algorithm. However, one of the main limitations of rollout algorithms in solving large-scale problems is represented by their computational complexity. Innovative versions of rollout algorithms, aimed at reducing the computational complexity in sequential environments, have been proposed in our previous work [9]. In this paper, we show that a further reduction can be accomplished by using parallel technologies. Indeed, rollout algorithms have very appealing characteristics that make them suitable for efficient and effective implementations in parallel environments, thus extending their range of relevant practical applications.We propose two strategies for parallelizing rollout algorithms and we analyze their performance by considering a shared-memory paradigm. The computational experiments have been carried out on a SGI Origin 2000 with 8 processors, by considering two classical combinatorial optimization problems. The numerical results show that a good reduction of the execution time can be obtained by exploiting parallel computing systems.     

Global solutions to a class of CEC benchmark constrained optimization problems

This paper aims to solve a class of CEC benchmark constrained optimization problems that have been widely studied by nature-inspired optimization algorithms. Based on canonical duality theory, these challenging problems can be reformulated as a unified canonical dual problem over a convex set, which can be solved deterministically to obtain global optimal solutions in polynomial time. Applications are illustrated by some well-known CEC benchmark problems, and comparisons with other methods have demonstrated the effectiveness of the proposed approach.     

Rules-based heuristic approach for the U-shaped assembly line balancing problem

The type-2 U-shaped assembly line balancing problem is important for many just-in-time manufactures, but an efficient algorithm is not available at present. Thus, in this study, a novel heuristic approach based on multiple rules and an integer programming model is proposed to address this problem. In the proposed approach, three rules are systematically grouped together, i.e., task selection, task assignment, and task exchange rules. The sufficient conditions for implementing the exchange rules are proposed and proved. Thirteen small or medium scale benchmark issues comprising 63 instances were solved, where the computational results demonstrate the efficiency and effectiveness of the proposed method compared with integer programming. The computational results obtained for 18 examples comprising 121 instances demonstrate that the task exchange rules significantly improve the computational accuracy compared with the traditional heuristic. Finally, 30 new standard instances produced by a systematic data generation process were also solved effectively by the proposed approach. The proposed heuristic approach with multiple rules can provide a theoretical basis for other local search algorithms, especially for addressing issues such as the U-Shaped assembly line balancing problem.     

The use of dynamic programming in genetic algorithms for permutation problems

To deal with computationally hard problems, approximate algorithms are used to provide reasonably good solutions in practical time. Genetic algorithms are an example of the meta-heuristics which were recently introduced and which have been successfully applied to a variety of problems. We propose to use dynamic programming in the process of obtaining new generation solutions in the genetic algorithm, and call it a genetic DP algorithm. To evaluate the effectiveness of this approach, we choose three representative combinatorial optimization problems, the single machine scheduling problem, the optimal linear arrangement problem and the traveling salesman problem, all of which ask to compute optimum permutations of n objects and are known to be NP-hard. Computational results for randomly generated problem instances exhibit encouraging features of genetic DP algorithms.     

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.     

Haplotyping populations by pure parsimony based on compatible genotypes and greedy heuristics

The population haplotype inference problem based on the pure parsimony criterion (HIPP) infers an m × n genotype matrix for a population by a 2m × n haplotype matrix with the minimum number of distinct haplotypes. Previous integer programming based HIPP solution methods are time-consuming, and their practical effectiveness remains unevaluated. On the other hand, previous heuristic HIPP algorithms are efficient, but their theoretical effectiveness in terms of optimality gaps has not been evaluated, either. We propose two new heuristic HIPP algorithms (MGP and GHI) and conduct more complete computational experiments. In particular, MGP exploits the compatible relations among genotypes to solve a reduced integer linear programming problem so that a solution of good quality can be obtained very quickly; GHI exploits a weight mechanism to selects better candidate haplotypes in a greedy fashion. The computational results show that our proposed algorithms are efficient and effective, especially for solving cases with larger recombination rates.     

On the convergence of global methods in multiextremal optimization

A general class of derivative-free optimization procedures is presented including the corresponding convergence theory. This theory turns out to be very constructive, in the sense that the convergence conditions not only can be verified easily for many existing algorithms, but also allow one to construct new procedures. It is shown that popular methods such as branch-and-bound concepts, Pintér's general class of procedures, the algorithms of Pijavskii, Shubert, and Mladineo, and the approach of Zheng and Galperin can not only be subsumed under this class of methods, but also partly be improved by regarding them within the framework presented.     

Some Variants of the Controlled Random Search Algorithm for Global Optimization

We suggested some modifications to the controlled random search (CRS) algorithm for global optimization. We introduce new trial point generation schemes in CRS, in particular, point generation schemes using linear interpolation and mutation. Central to our modifications is the probabilistic adaptation of point generation schemes within the CRS algorithm.A numerical study is carried out using a set of 50 test problems many of which are inspired by practical applications. Numerical experiments indicate that the resulting algorithms are considerably better than the previous versions. Thus, they offer a reasonable alternative to many currently available stochastic algorithms, especially for problems requiring direct search type methods.     

A storm of feasibility pumps for nonconvex MINLP

One of the foremost difficulties in solving Mixed-Integer Nonlinear Programs, either with exact or heuristic methods, is to find a feasible point. We address this issue with a new feasibility pump algorithm tailored for nonconvex Mixed-Integer Nonlinear Programs. Feasibility pumps are algorithms that iterate between solving a continuous relaxation and a mixed-integer relaxation of the original problems. Such approaches currently exist in the literature for Mixed-Integer Linear Programs and convex Mixed-Integer Nonlinear Programs: both cases exhibit the distinctive property that the continuous relaxation can be solved in polynomial time. In nonconvex Mixed-Integer Nonlinear Programming such a property does not hold, and therefore special care has to be exercised in order to allow feasibility pump algorithms to rely only on local optima of the continuous relaxation. Based on a new, high level view of feasibility pump algorithms as a special case of the well-known successive projection method, we show that many possible different variants of the approach can be developed, depending on how several different (orthogonal) implementation choices are taken. A remarkable twist of feasibility pump algorithms is that, unlike most previous successive projection methods from the literature, projection is ??naturally?? taken in two different norms in the two different subproblems. To cope with this issue while retaining the local convergence properties of standard successive projection methods we propose the introduction of appropriate norm constraints in the subproblems; these actually seem to significantly improve the practical performance of the approach. We present extensive computational results on the MINLPLib, showing the effectiveness and efficiency of our algorithm.     

Incremental-like bundle methods with application to energy planning

An important field of application of non-smooth optimization refers to decomposition of large-scale or complex problems by Lagrangian duality. In this setting, the dual problem consists in maximizing a concave non-smooth function that is defined as the sum of sub-functions. The evaluation of each sub-function requires solving a specific optimization sub-problem, with specific computational complexity. Typically, some sub-functions are hard to evaluate, while others are practically straightforward. When applying a bundle method to maximize this type of dual functions, the computational burden of solving sub-problems is preponderant in the whole iterative process. We propose to take full advantage of such separable structure by making a dual bundle iteration after having evaluated only a subset of the dual sub-functions, instead of all of them. This type of incremental approach has already been applied for subgradient algorithms. In this work we use instead a specialized variant of bundle methods and show that such an approach is related to bundle methods with inexact linearizations. We analyze the convergence properties of two incremental-like bundle methods. We apply the incremental approach to a generation planning problem over an horizon of one to three years. This is a large scale stochastic program, unsolvable by a direct frontal approach. For a real-life application on the French power mix, we obtain encouraging numerical results, achieving a significant improvement in speed without losing accuracy.     

A novel differential evolution algorithm for binary optimization

Differential evolution (DE) is one of the most powerful stochastic search methods which was introduced originally for continuous optimization. In this sense, it is of low efficiency in dealing with discrete problems. In this paper we try to cover this deficiency through introducing a new version of DE algorithm, particularly designed for binary optimization. It is well-known that in its original form, DE maintains a differential mutation, a crossover and a selection operator for optimizing non-linear continuous functions. Therefore, developing the new binary version of DE algorithm, calls for introducing operators having the major characteristics of the original ones and being respondent to the structure of binary optimization problems. Using a measure of dissimilarity between binary vectors, we propose a differential mutation operator that works in continuous space while its consequence is used in the construction of the complete solution in binary space. This approach essentially enables us to utilize the structural knowledge of the problem through heuristic procedures, during the construction of the new solution. To verify effectiveness of our approach, we choose the uncapacitated facility location problem (UFLP)—one of the most frequently encountered binary optimization problems—and solve benchmark suites collected from OR-Library. Extensive computational experiments are carried out to find out the behavior of our algorithm under various setting of the control parameters and also to measure how well it competes with other state of the art binary optimization algorithms. Beside UFLP, we also investigate the suitably of our approach for optimizing numerical functions. We select a number of well-known functions on which we compare the performance of our approach with different binary optimization algorithms. Results testify that our approach is very efficient and can be regarded as a promising method for solving wide class of binary optimization problems.     

Cutting plane versus compact formulations for uncertain (integer) linear programs

Robustness is about reducing the feasible set of a given nominal optimization problem by cutting ??risky?? solutions away. To this end, the most popular approach in the literature is to extend the nominal model with a polynomial number of additional variables and constraints, so as to obtain its robust counterpart. Robustness can also be enforced by adding a possibly exponential family of cutting planes, which typically leads to an exponential formulation where cuts have to be generated at run time. Both approaches have pros and cons, and it is not clear which is the best one when approaching a specific problem. In this paper we computationally compare the two options on some prototype problems with different characteristics. We first address robust optimization à la Bertsimas and Sim for linear programs, and show through computational experiments that a considerable speedup (up to 2 orders of magnitude) can be achieved by exploiting a dynamic cut generation scheme. For integer linear problems, instead, the compact formulation exhibits a typically better performance. We then move to a probabilistic setting and introduce the uncertain set covering problem where each column has a certain probability of disappearing, and each row has to be covered with high probability. A related uncertain graph connectivity problem is also investigated, where edges have a certain probability of failure. For both problems, compact ILP models and cutting plane solution schemes are presented and compared through extensive computational tests. The outcome is that a compact ILP formulation (if available) can be preferable because it allows for a better use of the rich arsenal of preprocessing/cut generation tools available in modern ILP solvers. For the cases where such a compact ILP formulation is not available, as in the uncertain connectivity problem, we propose a restart solution strategy and computationally show its practical effectiveness.     

Fast proximal algorithms for nonsmooth convex optimization

In the lines of our previous approach to devise proximal algorithms for nonsmooth convex optimization by applying Nesterov fast gradient concept to the Moreau–Yosida regularization of a convex function, we develop three new proximal algorithms for nonsmooth convex optimization. In these algorithms, the errors in computing approximate solutions for the Moreau–Yosida regularization are not fixed beforehand, while preserving the complexity estimates already established. We report some preliminary computational results to give a first estimate of their performance.     

Artificial time integration

Many recent algorithmic approaches involve the construction of a differential equation model for computational purposes, typically by introducing an artificial time variable. The actual computational model involves a discretization of the now time-dependent differential system, usually employing forward Euler. The resulting dynamics of such an algorithm is then a discrete dynamics, and it is expected to be “close enough” to the dynamics of the continuous system (which is typically easier to analyze) provided that small – hence many – time steps, or iterations, are taken. Indeed, recent papers in inverse problems and image processing routinely report results requiring thousands of iterations to converge. This makes one wonder if and how the computational modeling process can be improved to better reflect the actual properties sought. In this article we elaborate on several problem instances that illustrate the above observations. Algorithms may often lend themselves to a dual interpretation, in terms of a simply discretized differential equation with artificial time and in terms of a simple optimization algorithm; such a dual interpretation can be advantageous. We show how a broader computational modeling approach may possibly lead to algorithms with improved efficiency. AMS subject classification (2000)  65L05, 65M32, 65N21, 65N22, 65D18     

Estimating the Firm Value Distribution Function by Entropy Optimization and Geometric Programming

By applying the option pricing theory ideas, this paper models the estimation of firm value distribution function as an entropy optimization problem, subject to correlation constraints. It is shown that the problem can be converted to a dual of a computationally attractive primal geometric programming (GP) problem and easily solved using publicly available software. A numerical example involving stock price data from a Japanese company demonstrates the practical value of the GP approach. Noting the use of Monte Carlo simulation in option pricing and risk analysis and its difficulties in handling distribution functions subject to correlations, the GP based method discussed here may have some computational advantages in wider areas of computational finance in addition to the application discussed here.     

Prices stabilization for inexact unit-commitment problems

A widespread and successful approach to tackle unit-commitment problems is constraint decomposition: by dualizing the linking constraints, the large-scale nonconvex problem decomposes into smaller independent subproblems. The dual problem consists then in finding the best Lagrangian multiplier (the optimal “price”); it is solved by a convex nonsmooth optimization method. Realistic modeling of technical production constraints makes the subproblems themselves difficult to solve exactly. Nonsmooth optimization algorithms can cope with inexact solutions of the subproblems. In this case however, we observe that the computed dual solutions show a noisy and unstable behaviour, that could prevent their use as price indicators. In this paper, we present a simple and easy-to-implement way to stabilize dual optimal solutions, by penalizing the noisy behaviour of the prices in the dual objective. After studying the impact of a general stabilization term on the model and the resolution scheme, we focus on the penalization by discrete total variation, showing the consistency of the approach. We illustrate our stabilization on a synthetic example, and real-life problems from EDF (the French Electricity Board).     

Convergence and numerical results for a parallel asynchronous quasi-Newton method

During the execution of a parallel asynchronous iterative algorithm, each task does not wait for predetermined data to become available. On the contrary, they can be viewed as local and independent iterative algorithms, which perform their own iterative scheme on the data currently available.On the basis of this computational model, a parallel asynchronous version of the quasi-Newton method for solving unconstrained optimization problems is proposed. The algorithm is based on four tasks concurrently executing and interacting in an asynchronous way.Convergence conditions are established and numerical results are presented which prove the effectiveness of the proposed parallel asynchronous approach.This research work was partially supported by the National Research Council of Italy within the special project Sistemi Informatici e Calcolo Parallelo under CNR Contract No. 92.01585.PF69.The authors are grateful to M. Al-Baali and R. H. Byrd for their valuable comments.     

An unconstrained dual approach to solving Karmarkar-type linear programs using conventional barrier functions

This paper proposes an unconstrained dual approach and an efficient algorithm for solving Karmarkar-type linear programming problems. Conventional barrier functions are incorporated as a perturbation term in the derivation of the associated duality theory. An optimal solution of the original linear program can be obtained by solving a sequence of unconstrained concave programs, or be approximated by solving one such dual program with a sufficiently small perturbation parameter. A globally convergent curved-search algorithm with a quadratic rate of convergence is designed for this purpose. Based on our testing results, we find that the computational procedure is very efficient and can be a viable approach for solving linear programming problems.     

A Semidefinite Programming Based Polyhedral Cut and Price Approach for the Maxcut Problem

We investigate solution of the maximum cut problem using a polyhedral cut and price approach. The dual of the well-known SDP relaxation of maxcut is formulated as a semi-infinite linear programming problem, which is solved within an interior point cutting plane algorithm in a dual setting; this constitutes the pricing (column generation) phase of the algorithm. Cutting planes based on the polyhedral theory of the maxcut problem are then added to the primal problem in order to improve the SDP relaxation; this is the cutting phase of the algorithm. We provide computational results, and compare these results with a standard SDP cutting plane scheme. Research supported in part by NSF grant numbers CCR–9901822 and DMS–0317323. Work done as part of the first authors Ph.D. dissertation at RPI.