Spherical cuts for integer programming problems

We introduce a new family of valid inequalities for general linear integer programming problems, based on the distance of the relaxed solution to the closest integral point. We show that these are valid cuts, establish some relations with Balas' intersection cuts, and show that a straightforward cutting plane algorithm derived from either spherical or intersection cuts will in general only converge if a suitable Gomory‐type strengthening is put in place.     

求解0-1背包问题的二进制狮群算法

针对传统二进制群智能算法求解0-1背包问题易陷入局部最优、收敛速度慢的缺点,提出一种新的解决离散空间问题的二进制狮群算法BLSO。二进制狮群算法对狮王、母狮和幼狮的位置重新定义,引入反置运算、移动算子和学习算子建立全新的位置转移方式和局部搜索规则;加入贪心策略进行解的可行化处理和充分利用,增强局部搜索能力,进一步提高收敛速度。对9个典型的0-1背包算例进行仿真实验,实验结果表明,该算法不仅可以有效求解0-1背包问题,而且还能够以较快的速度搜索到精度较高的次优解甚至全局最优解,具有较好的稳定性;同时,对高维背包问题的求解与参考算法相比,在寻优时间和精度上更具优势。     

An improved monkey algorithm for a 0-1 knapsack problem

The 0-1 knapsack problem is a classic combinational optimization problem. However, many exiting algorithms have low precision and easily fall into local optimal solutions to solve the 0-1 knapsack problem. In order to overcome these problems, this paper proposes a binary version of the monkey algorithm where the greedy algorithm is used to strengthen the local search ability, the somersault process is modified to avoid falling into local optimal solutions, and the cooperation process is adopted to speed up the convergence rate of the algorithm. To validate the efficiency of the proposed algorithm, experiments are carried out with various data instances of 0-1 knapsack problems and the results are compared with those of five metaheuristic algorithms.     

Solving multidimensional 0–1 knapsack problem by P systems with input and active membranes

Membrane systems are biologically motivated theoretical models of distributed and parallel computing. In this paper, we present a membrane algorithm to solve multidimensional 0–1 knapsack problem in linear time by recognizer P systems with input and with active membranes using 2-division. This algorithm can also be modified to solve general 0–1 integer programming problem.     

Determining the K-best solutions of knapsack problems

It is well-known that knapsack problems arise as subproblems of a number of large-scale integer optimization problems. In order to solve these large problems, it is necessary to solve the subproblems efficiently, and for many of them it can be useful to determine the K-best solutions. In this paper, a branch-and-bound method for the unbounded knapsack problem described in the literature is extended to determine the K-best solutions of unbounded and bounded knapsack problems. We show that the proposed extension determines exactly the K-best solutions and we solve important classical instances using high values of K.     

Stage- and scenario-wise Fenchel decomposition for stochastic mixed 0-1 programs with special structure

Solving stochastic integer programs (SIPs) is generally difficult. This paper considers a comparative study of stage- and scenario-wise Fenchel decomposition (FD) for two-stage SIPs with special structure. The standard FD approach is based on stage-wise or Benders’ decomposition. This work derives a scenario FD method based on decomposing the SIP problem by scenario and performs a computational study of the two approaches. In particular, two algorithms are studied, stage-wise FD (ST-FD) and scenario-wise FD (SC-FD) algorithms. The algorithms use FD cuts generated based on the scenario subproblem under each decomposition setting to iteratively recover (partially) the convex hull of integer points in the neighborhood of the optimal solution. The L-shaped method is used to solve the LP relaxation of the SIP problem in the ST-FD algorithm, while the progressive hedging algorithm (PHA) is used in the SC-FD algorithm. Computational results on knapsack test instances demonstrate the viability of both approaches towards solving large instances in reasonable amount of time and outperforming a direct solver in most cases. Overall, the ST-FD algorithm provides the best performance in our experiments.     

A parallel algorithm for the 0–1 knapsack problem

Research efforts on parallel exact algorithms for the 0–1 knapsack problem have up to now concentrated on solving small problems (at most 1,000 objects) and in many cases results have only been obtained by simulation of the parallel algorithm. After a brief review of a well known sequential branch-and-bound algorithm we discuss a new parallel algorithm for the 0–1 knapsack problem which exploits the potential parallelism that exists during the backtracking steps of the branch-and-bound algorithm. We report results for our parallel algorithm on a transputer network for problems with up to 20,000 objects. The speedup obtained is nearly linear for 2, 4, and 8 processors except when there is a strong correlation between the profit and weight of the objects.     

Approximate algorithms for some generalized knapsack problems

In this paper we construct approximate algorithms for the following problems: integer multiple-choice knapsack problem, binary multiple-choice knapsack problem and multi-dimensional knapsack problem. The main result can be described as follows: for every ε 0 one can construct a polynomial-time algorithm for each of the above problems such that the ratio of the value of the objective function by this algorithm and the optimal value is bounded below by 1 - ε.     

Analysis of the knapsack problem using L-partition

A periodicity region of the knapsack problem with a parameter in the right-hand side is analyzed using a partition of a finite-dimensional space. Upper bounds are constructed on the cardinality of L-covers and on the number of regular cuts required to solve the problem.Translated from Kibernetika, No. 2, pp. 38–43, March–April, 1991.     

Exact and greedy solutions of the knapsack problem: the ratio of values of objective functions

Ratios δ of the values of objective functions of optimal Boolean (or integer) to the values of greedy solutions for the knapsack problem are considered. The relationship of the parameter δ with the ratio Δ of the values of objective functions for the optimal solution of linear relaxation to the values of optimal integer solution was found. Two-sided estimates for δ and Δ were obtained. A computational experiment was conducted to investigate the ratio of δ of problems of one- and two-dimensional knapsack problems with Boolean variables. A hypothesis on asymptotic behavior of the ratio δ with growth of the number of problem variables was formulated.     

Testable heuristics for the 0–1 knapsack problem

Two kinds of heuristics, fixed time and cut time, are proposed in order to use the running time available in solving 0–1 knapsack problems profitably.Translated from Kibernetika, No. 2, pp. 44–52, March–April, 1991.     

Stability Analysis of Some Discrete Optimization Algorithms

Facts established for stability of the relaxation set-based integer programming algorithms were reviewed. For the problem of integer linear programming, the branch-and-bound algorithms were examined for stability within the framework of the Land–Doig method. They were shown to be unstable for sufficiently small oscillations of the relaxation sets of the problems at hand. A similar result was obtained for algorithms with the Dantzig cuts.     

Ratios of optimal values of objective functions of the knapsack problem and its linear relaxation

The ratios of the values of objective functions for optimal solutions of linear and integer knapsack problems are considered. Estimates for these ratios are obtained. One-dimensional and multi-dimensional knapsack problems with Boolean variables are studied experimentally. For these problems, a hypothesis is formulated on the asymptotic behavior of the ratio as the number of variables grows.     

Searching for optimal integer solutions to set partitioning problems using column generation

In this paper, we describe a new approach to increase the possibility of finding integer feasible columns to a set partitioning problem (SPP) directly in solving the linear programming (LP) relaxation using column generation. Traditionally, column generation is aimed to solve the LP‐relaxation as quickly as possible without any concern for the integer properties of the columns formed. In our approach, we aim to generate columns forming an optimal integer solution while simultaneously solving the LP‐relaxation. Using this approach, we can improve the possibility of finding integer solutions by heuristics at each node in the branch‐and‐bound search. In addition, we improve the possibility of finding high‐quality integer solutions in cases where only the columns in the root node are used to solve the problem. The basis of our approach is a subgradient technique applied to a Lagrangian dual formulation of the SPP extended with an additional surrogate constraint. This extra constraint is not relaxed and is used to better control the subgradient evaluations and how the multiplier values are computed. The column generation is then directed, via the multipliers, to construct columns that form feasible integer solutions. Computational experiments show that we can generate optimal integer columns in a large set of well‐known test problems as compared to both standard and stabilized column generation, and simultaneously keep the number of columns smaller than standard column generation. This is also supported by tests on a case study with work‐shift generation.     

A simple strategy for solving a class of 0–1 integer programming models

In this paper, a strategy is proposed for solving certain generalized set packing models. The strategy is based on using a recently developed heuristic coupled with the solution of the linear programming relaxation of the model. The strategy is programmed, and execution times required for it to obtain optimal solutions to randomly generated models are compared to those required for an implementation of the Gomory cutting plane algorithm. The Cray 1 computer was used for all computations. Computational experience thus gained indicates that the proposed strategy is superior to the Gomory algorithm, and that it seems to perform relatively better on models with relatively higher-density constraint coefficient matrices.     

Parallel computation of the eigenvalues of symmetric Toeplitz matrices through iterative methods

This paper presents a new procedure to compute many or all of the eigenvalues and eigenvectors of symmetric Toeplitz matrices. The key to this algorithm is the use of the “Shift–and–Invert” technique applied with iterative methods, which allows the computation of the eigenvalues close to a given real number (the “shift”). Given an interval containing all the desired eigenvalues, this large interval can be divided in small intervals. Then, the “Shift–and–Invert” version of an iterative method (Lanczos method, in this paper) can be applied to each subinterval. Since the extraction of the eigenvalues of each subinterval is independent from the other subintervals, this method is highly suitable for implementation in parallel computers. This technique has been adapted to symmetric Toeplitz problems, using the symmetry exploiting Lanczos process proposed by Voss [H. Voss, A symmetry exploiting Lanczos method for symmetric Toeplitz matrices, Numerical Algorithms 25 (2000) 377–385] and using fast solvers for the Toeplitz linear systems that must be solved in each Lanczos iteration. The method compares favourably with ScaLAPACK routines, specially when not all the spectrum must be computed.     

A bilevel decomposition algorithm for simultaneous production scheduling and conflict-free routing for automated guided vehicles

We address a bilevel decomposition algorithm for solving the simultaneous scheduling and conflict-free routing problems for automated guided vehicles. The overall objective is to minimize the total weighted tardiness of the set of jobs related to these tasks. A mixed integer formulation is decomposed into two levels: the upper level master problem of task assignment and scheduling; and the lower level routing subproblem. The master problem is solved by using Lagrangian relaxation and a lower bound is obtained. Either the solution turns out to be feasible for the lower level or a feasible solution for the problem is constructed, and an upper bound is obtained. If the convergence is not satisfied, cuts are generated to exclude previous feasible solutions before solving the master problem again. Two types of cuts are proposed to reduce the duality gap. The effectiveness of the proposed method is investigated from computational experiments.     

A linear programming approach for the weighted graph matchingproblem

A linear programming (LP) approach is proposed for the weighted graph matching problem. A linear program is obtained by formulating the graph matching problem in L₁ norm and then transforming the resulting quadratic optimization problem to a linear one. The linear program is solved using a simplex-based algorithm. Then, approximate 0-1 integer solutions are obtained by applying the Hungarian method on the real solutions of the linear program. The complexity of the proposed algorithm is polynomial time, and it is O(n ⁶L) for matching graphs of size n. The developed algorithm is compared to two other algorithms. One is based on an eigendecomposition approach and the other on a symmetric polynomial transform. Experimental results showed that the LP approach is superior in matching graphs than both other methods     

Exact optimal solution for facility layout: deciding which pairs of locations should be adjacent

This paper describes the development of a mathematical model for determining optimum block layout systems utilizing 0–1 integer programming as the optimization component. The objective function is to maximize a weighted sum of adjacent departments. The selected weight is a measure of the flow of material between departments. Developing a set of constraints, and changing the objective function to minimization of adjacency of departments with no interaction, it is shown that the procedure is capable of determining the optimal location in small size problems. To apply it to larger size problems, additional constraints are developed that help reduce the number of iterations for the integer program to converge to an optimal solution.     

Software package for large-scale 0–1 linear programming on Unix system: GUB technique

Recently, a multiple criteria decision making (MCDM) has been well established as a practical approach to seek a satisfactory solution to a decision making problem. Linear programming (LP) is one of the most widely used OR/MS/IE techniques for solving MCDM problems. In the realistic decision making problems, many LP problems are involved a large number of 0–1 decision variables and a special type of system structures. So much kind of the large-scale 0–1 LP problems are simply too large fit into a microcomputer/workstation.

In this paper, we develop a software package micro 0–1LP(GUB) for solving LP problems with a generalized upper bounding (GUB) structure as large-scale 0–1LP problems on UNIX systems. From the views of the computational experience and storage requirement, micro 0–1LP(GUB) using the C programming language is implemented an efficient method in which the GUB structure would be effectively handled.

As a real-world large-scale 0–1LP problem with the GUB structures by the micro 0–1LP (GUB) software package developed here, we demonstrate an optimization problem of system reliability for selecting the allocating the components on an UNIX system, Sanyo/Icon MPS 020.