Accelerated primal-dual cutting plane algorithm for all-integer programming

The use of integer programming as a modeling technique is widespread in practice, but current algorithms for solving these models are less than satisfactory even for problems of modest size. Thus the search continues for more efficient and reliable algorithms. In this paper we present a technique for solving all-integer programming problems. The algorithm, which we call the accelerated primal-dual algorithm (APDA), uses all-integer cutting planes and an advanced feasible start to speed convergence to optimality. We discuss computational results on a standard set of test problems.     

An advanced start algorithm for all-integer programming

In this paper, we present an all-integer cutting plane technique called the Advanced Start Algorithm (ASA), for solving the all-integer (otherwise linear) programming problem (IP). We develop a good advanced primal-infeasible start based on the optimal solution to the LP relaxation, and use a two-stage dual/primal algorithm to obtain the optimal solution to (IP). We illustrate the operation of the ASA on three small problems, and exhibit computational results on a set of standard test problems.     

A cutting plane algorithm for robustness analysis of periodicallytime-varying systems

An algorithm for robustness analysis of periodic systems is derived. The system under consideration consists of a linear periodically time-varying plant in feedback interconnection with a structured uncertainty. Conditions for robust stability and robust performance can be formulated in terms of periodic integral quadratic constraints (IQCs). In this way, the robustness analysis becomes a problem of optimizing the parameters of the IQC. A cutting plane algorithm is suggested for solving this infinite-dimensional optimization problem     

An interior point cutting plane heuristic for mixed integer programming

We explore the use of interior point methods in finding feasible solutions to mixed integer programming. As integer solutions are typically in the interior, we use the analytic center cutting plane method to search for integer feasible points within the interior of the feasible set. The algorithm searches along two line segments that connect the weighted analytic center and two extreme points of the linear programming relaxation. Candidate points are rounded and tested for feasibility. Cuts aimed to improve the objective function and restore feasibility are then added to displace the weighted analytic center until a feasible integer solution is found. The algorithm is composed of three phases. In the first, points along the two line segments are rounded gradually to find integer feasible solutions. Then in an attempt to improve the quality of the solutions, the cut related to the bound constraint is updated and a new weighted analytic center is found. Upon failing to find a feasible integer solution, a second phase is started where cuts related to the violated feasibility constraints are added. As a last resort, the algorithm solves a minimum distance problem in a third phase. The heuristic is tested on a set of problems from MIPLIB and CORAL. The algorithm finds good quality feasible solutions in the first two phases and never requires the third phase.     

Solution approaches for highly primal- and dual-degenerate all-integer programming problems

In this paper, we discuss solution approaches to the important but difficult class of all-integer programming problems that are highly primal and dual-degenerate. In particular, we note our success with an “objective function cut” in this regard, and exhibit a computational comparison with other cutting plane techniques.     

A cutting plane method for knapsack polytope

A separation algorithm for knapsack polytope is proposed. This algorithm has been used in the branch-and-cut method for solving the generalized assignment problem and the capacitated p-median problem. The computational experiment on the test instances has shown that this method is highly competitive in comparison with the existing approaches.     

A cutting plane method for solving KYP-SDPs

Semidefinite programs originating from the Kalman-Yakubovich-Popov lemma are convex optimization problems and there exist polynomial time algorithms that solve them. However, the number of variables is often very large making the computational time extremely long. Algorithms more efficient than general purpose solvers are thus needed. To this end structure exploiting algorithms have been proposed, based on the dual formulation. In this paper a cutting plane algorithm is proposed. In a comparison with a general purpose solver and a structure exploiting solver it is shown that the cutting plane based solver can handle optimization problems of much higher dimension.     

A cutting plane approach for integrated planning and scheduling

In this paper we propose a branch-and-cut algorithm for solving an integrated production planning and scheduling problem in a parallel machine environment. The planning problem consists of assigning each job to a week over the planning horizon, whereas in the scheduling problem those jobs assigned to a given week have to be scheduled in a parallel machine environment such that all jobs are finished within the week. We solve this problem in two ways: (1) as a monolithic mathematical program and (2) using a hierarchical decomposition approach in which only the planning decisions are modeled explicitly, and the existence of a feasible schedule for each week is verified by using cutting planes. The two approaches are compared with extensive computational testing.     

A dynamic programming branch and bound algorithm for pure integer programming

Several algorithms for linear integer programming have been proposed in which one or more of the conditions are relaxed to produce a solvable problem form. Reimposing these relaxed conditions can lead to a branch and bound process. In this paper an alternative relaxation is proposed in which the integer conditions are maintained but the feasibility conditions are relaxed in a special way. Reimposing feasibility by sequentially setting variables creates the branch and bound process. In special cases, the algorithm reverts to the normal form of dynamic programming.The algorithm is applicable to both linear and non-linear pure integer problems. It has been programmed to solve pure $\text{0}\text{1}$ problems and results of computational experience with some linear problems previously used in the literature are given.     

A revised iterative algorithm for decomposition goal programming

The decomposition approach has received increasing attention in recent years not only as ft computational technique for large-scale management models but also as a systematic tool for designing organizational structure and information systems in decentralized organizations. In this paper, a revised iterative algorithm is developed for multicriteria decomposition in an organization by utilizing goal programming. The algorithm not only has the capability of dealing with multicriteria decomposition problems but is also useful for evaluating organizational effectiveness of a decentralized organization. A simple example is presented for an illustrative purpose of the algorithm application.     

A parallel processing algorithm for nonlinear programming problems

Algorithms for solving multiple criteria nonlinear programming problems are frequently based on the use of the generalized reduced gradient (GRG) metod. Since the GRG method gives complex and large size processing for computation, it takes much time to solve large-scale multiple criteria nonlinear programming problems. Therefore, parallel processing dealing with the GRG method is required to solve the problems. We propose a parallel processing algorithm for the GRG method under multiple processors systems.     

A nonlinear programming algorithm for hydro-thermal generation scheduling

This paper presents an efficient decomposition technique for optimal generation scheduling of hydro-thermal systems. Interval-wise decomposition has been carried out so as to reduce the complexity of the problem. The decomposed subproblems have been converted into unconstrained nonlinear programming subproblems using augmented penalty function approach. Each subproblem is separately solved using Fletcher's modified metric algorithm.     

A monotonic projective algorithm for fractional linear programming

We demonstrate that Karmarkar's projective algorithm is fundamentally an algorithm for fractional linear programming on the simplex. Convergence for the latter problem is established assuming only an initial lower bound on the optimal objective value. We also show that the algorithm can be easily modified so as to assure monotonicity of the true objective values, while retaining all global convergence properties. Finally, we show how the monotonic algorithm can be used to obtain an initial lower bound when none is otherwise available.     

A monotonic projective algorithm for fractional linear programming

We demonstrate that Karmarkar's projective algorithm is fundamentally an algorithm for fractional linear programming on the simplex. Convergence for the latter problem is established assuming only an initial lower bound on the optimal objective value. We also show that the algorithm can be easily modified so as to assure monotonicity of the true objective values, while retaining all global convergence properties. Finally, we show how the monotonic algorithm can be used to obtain an initial lower bound when none is otherwise available.     

A genetic algorithm approach for the cutting stock problem

In this paper, a genetic algorithm approach is developed for solving the rectangular cutting stock problem. The performance measure is the minimization of the waste. Simulation results obtained from the genetic algorithm-based approach are compared with one heuristic based on partial enumeration of all feasible patterns, and another heuristic based on a genetic neuro-nesting approach. Some test problems taken from the literature were used for the experimentation. Finally, the genetic algorithm approach was applied to test problems generated randomly. The simulation results of the proposed approach in terms of solution quality are encouraging when compared to the partial enumeration-based heuristic and the genetic neuro-nesting approach.     

A parallel algorithm for constrained two-staged two-dimensional cutting problems

In this paper, we solve the two-staged two-dimensional cutting problem using a parallel algorithm. The proposed approach combines two main features: beam search (BS) and strip generation solution procedures (SGSP). BS employs a truncated tree-search, where a selected subset of generated nodes are retuned for further search. SGSP, a constructive procedure, combines a (sub)set of strips for providing both partial lower and complementary upper bounds. The algorithm explores in parallel a subset of selected nodes following the master-slave paradigm. The master processor serves to guide the search-resolution and each slave processor develops its proper way, trying a global convergence. The aim of such an approach is to show how the parallelism is able to efficiently solve large-scale instances, by providing new solutions within a consistently reduced runtime. Extensive computational testing on instances, taken from the literature, shows the effectiveness of the proposed approach.     

A variable-grouping based genetic algorithm for large-scale integer programming

To effectively reduce the dimensionality of search space, this paper proposes a variable-grouping based genetic algorithm (VGGA) for large-scale integer programming problems (IPs). The VGGA first groups IP’s decision variables based on the optimal solution to the IP’s continuous relaxation problem, and then applies a standard genetic algorithm (GA) to the subproblem for each group of variables. We compare the VGGA with the standard GA and GAs based on even variable-grouping by applying them to solve randomly generated convex quadratic knapsack problems and integer knapsack problems. Numerical results suggest that the VGGA is superior to the standard GA and GAs based on even variable-grouping both on computation time and solution quality.     

A new branch-and-bound algorithm for standard quadratic programming problems

In this paper we propose convex and LP bounds for standard quadratic programming (StQP) problems and employ them within a branch-and-bound approach. We first compare different bounding strategies for StQPs in terms both of the quality of the bound and of the computation times. It turns out that the polyhedral bounding strategy is the best one to be used within a branch-and-bound scheme. Indeed, it guarantees a good quality of the bound at the expense of a very limited computation time. The proposed branch-and-bound algorithm performs an implicit enumeration of all the KKT (stationary) points of the problem. We compare different branching strategies exploiting the structure of the problem. Numerical results on randomly generated problems (with varying density of the underlying convexity graph) are reported which show the effectiveness of the proposed approach, in particular in limiting the growth of the number of nodes in the branch-and-bound tree as the density of the underlying graph increases.