The mixed cutting plane algorithm for all-integer programming

We exhibit and discuss an all-integer programming technique called the Mixed Cutting Plane Algorithm (MCPA). The basic computational vehicle is the All-Integer Simplex Algorithm (AISA), which is used to avoid round-off errors in the LP and fractional cutting plane phases. After an all-integer tableau is attained, the MCPA switches to dual all-integer cuts to complete the solution procedure. We discuss the results of computational testing on randomly generated test problems.     

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.     

An interactive analytic center trade-off cutting plane algorithm for multiobjective linear programming

This paper proposes the use of an interior point algorithm for Multiobjective Linear Programming problems. At each iteration of the algorithm, the decision maker furnishes his precise trade-offs. From these trade-offs, a cut is formed in the objective space. This cut induces a cut in the decision space that defines a half-space of promising points. We compute the analytic center of the restricted feasible region in the decision space and then we calculate the trade-offs of the decision maker at the image of the analytic center in the objective space. Therefore, we obtain a trajectory of analytic centers that converges to the best compromise solution. Since the proposed algorithm moves through the interior of the feasible region, it avoids the combinatorial difficulties of visiting extreme points and is less sensitive to problem size. We illustrate the method through a numerical example and provide computational experience.     

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 algorithm for the site layout planning problem with travel barriers

Site layout planning is an imperative procedure that may significantly impact the productivity and the efficiency of logistical operations undertaken on a construction site. This paper considers the site layout planning problem (SLPP) which entails the allocation of temporary facilities on a construction site in the presence of travel barriers such that the total transportation cost between facilities is minimised. In order to account for travel barriers, the SLPP is typically solved under the assumption that the available region for facility layout can be discretised. In this paper, we propose a general Mixed Integer Programming (MIP) model to represent the SLPP, accounting for the presence of barriers, and we show how space-discretised formulations can be derived from this model. In particular, we propose a novel MIP model, which permits facilities to cover multiple locations. This is then benchmarked against a commonly adopted MIP model in the literature. We also highlight a systematic procedure to convert the continuous feasible space in SLPP to a set of discretised locations based on the concept of d-visibility, enabling us to approximate the barrier distance function embedded in the objective function. In particular, we focus on presenting a simple space discretisation approach for converting the continuous SLP into a discrete problem for which the discrete SLP models would be applicable. Space-discretised MIP formulations are highly combinatorial and we introduce a cutting plane algorithm to improve their tractability. Specifically, we propose a novel exact location-decomposition algorithm which works from a relaxed MIP formulation and iteratively generates feasibility cuts to converge to an optimal solution. Both space-discretised MIP models and the decomposition algorithm are tested on a large group of instances to analyse their effectiveness in solving the SLPP. Computational results indicate that the proposed location-decomposition algorithm improves on the pure MIP approach and provides a competitive framework to solve realistic SLPP instances.     

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.     

An exact dynamic programming algorithm for large-scale unconstrained two-dimensional guillotine cutting problems

In the unconstrained two-dimensional cutting problems (U2DCP) small rectangular objects have to be extracted from a large rectangular sheet, with no limits on the number of small objects.The exact U2DCP solving approaches present in literature show some limits in tackling very large size instances, due to the high memory requirements.In this work we propose five improvements, three original and two derived from the literature, in order to overcome these limits and to reduce the computational burden of the knapsack function based U2DCP solving approaches. These improvements, based on proofed theoretical results, allow to reduce the search space and to avoid redundant solutions without loss of the feasible ones.The presented improvements, together with several computational refinements, are integrated in a new dynamic programming algorithm, which modifies the one by Russo et al. (2013 [16]). The proposed algorithm has been experienced on test instances present in literature and compared with the best U2DCP solving approaches. The obtained results show that it significantly outperforms them and it determines the optimal solution of unsolved very large size instances.     

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.     

一种基于多代理模型的混合整数规划优化方法

提出一种基于多代理模型的优化方法,求解混合整数规划问题.首先,基于群智能优化策略提出一种基于多群体协作模型的采样方法,保证候选解的正确性和多样性;其次,采用基于数据并行的高斯过程建模方法,在线构造局部代理模型;再次,通过多代理模型对候选解进行预筛选,实现与粒子群算法的协同优化;最后,通过14个测试问题和一个基于数据驱动的模型参数选取问题,验证所提出方法的有效性.     

整数规划的量子行为蝙蝠算法

蝙蝠算法是一种新型群体智能算法,传统的蝙蝠算法在解决整数规划问题时容易陷入局部最优并出现早熟收敛现象,为了解决这些弊端,提出了一种基于势阱的具有量子行为的蝙蝠算法。论述了算法的优化原理和实现方式,并通过仿真实验,与粒子群算法和量子行为粒子群算法进行性能对比。实验结果表明,量子行为蝙蝠算法不仅能够有效地解决整数规划问题,而且比其他算法具有更好的性能。     

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.