On threshold BDDs and the optimal variable ordering problem

Many combinatorial optimization problems can be formulated as 0/1 integer programs (0/1 IPs). The investigation of the structure of these problems raises the following tasks: count or enumerate the feasible solutions and find an optimal solution according to a given linear objective function. All these tasks can be accomplished using binary decision diagrams (BDDs), a very popular and effective datastructure in computational logics and hardware verification. We present a novel approach for these tasks which consists of an output-sensitive algorithm for building a BDD for a linear constraint (a so-called threshold BDD) and a parallel AND operation on threshold BDDs. In particular our algorithm is capable of solving knapsack problems, subset sum problems and multidimensional knapsack problems. BDDs are represented as a directed acyclic graph. The size of a BDD is the number of nodes of its graph. It heavily depends on the chosen variable ordering. Finding the optimal variable ordering is an NP-hard problem. We derive a 0/1 IP for finding an optimal variable ordering of a threshold BDD. This 0/1 IP formulation provides the basis for the computation of the variable ordering spectrum of a threshold function. We introduce our new tool azove 2.0 as an enhancement to azove 1.1 which is a tool for counting and enumerating 0/1 points. Computational results on benchmarks from the literature show the strength of our new method.     

Approximation algorithms on 0–1 linear knapsack problem with a single continuous variable

The 0–1 linear knapsack problem with a single continuous variable (KPC) is a natural generalization of the standard 0–1 linear knapsack problem (KP). In KPC, the capacity of the knapsack is not fixed, but can be adjusted by a continuous variable. This paper studies the approximation algorithm on KPC. Firstly, assuming that the weight of each item is at most the original capacity of the knapsack, we give a 2-approximation algorithm on KPC by generalizing the 2-approximation algorithm on KP. Then, without the above assumption, we give another 2-approximation algorithm on KPC for general cases by extending the first algorithm.     

Upper Bounds for the SPOT 5 Daily Photograph Scheduling Problem

This paper introduces tight upper bounds for the daily photograph scheduling problem of earth observation satellites. These bounds, which were unavailable until now, allow us to assess the quality of the heuristic solutions obtained previously. These bounds are obtained with a partition-based approach following the divide and pas conquer principle. Dynamic programming and tabu search are conjointly used in this approach. We present also simplex-based linear programming relaxation and a relaxed knapsack approach for the problem.     

SIRALINA: efficient two-steps heuristic for storage optimisation in single period task scheduling

In this paper, we study the general problem of one-dimensional periodic task scheduling under storage requirement, irrespective of machine constraints. We have already presented in (Touati and Eisenbeis, Parallel Process. Lett. 14(2):287–313, 2004) a theoretical framework that allows an optimal optimisation of periodic storage requirement in a cyclic schedule. Since our optimisation problem is NP-hard (Touati, PhD thesis, 2002), solving an exact integer linear programming formulation is too expensive in practice. In this article, we propose an efficient two-steps heuristic using model’s properties that allows fast computation times while providing highly satisfactory results. This method includes the solution of an integer linear program with a totally unimodular constraints matrix in first step, then the solution of a linear assignment problem. Our heuristic is implemented for an industrial compiler for embedded VLIW processors.     

A Semidefinite Programming Approach to the Quadratic Knapsack Problem

In order to gain insight into the quality of semidefinite relaxations of constrained quadratic 0/1 programming problems we study the quadratic knapsack problem. We investigate several basic semidefinite relaxations of this problem and compare their strength in theory and in practice. Various possibilities to improve these basic relaxations by cutting planes are discussed. The cutting planes either arise from quadratic representations of linear inequalities or from linear inequalities in the quadratic model. In particular, a large family of combinatorial cuts is introduced for the linear formulation of the knapsack problem in quadratic space. Computational results on a small class of practical problems illustrate the quality of these relaxations and cutting planes.     

A successive approximation algorithm for the multiple knapsack problem

It is well-known that the multiple knapsack problem is NP-hard, and does not admit an FPTAS even for the case of two identical knapsacks. Whereas the 0-1 knapsack problem with only one knapsack has been intensively studied, and some effective exact or approximation algorithms exist. A natural approach for the multiple knapsack problem is to pack the knapsacks successively by using an effective algorithm for the 0-1 knapsack problem. This paper considers such an approximation algorithm that packs the knapsacks in the nondecreasing order of their capacities. We analyze this algorithm for 2 and 3 knapsack problems by the worst-case analysis method and give all their error bounds.     

An improved MIP heuristic for the intermodal hub location problem

Optimization methods have been commonly developed for the intermodal hub location problem because it has a broad range of practical applications. These methods include exact methods (limited on solving large-size problems) and heuristics (no guarantee on solution quality). In order to avoid their weakness but to leverage their strength, we develop an improved MIP heuristic combining branch-and-bound, Lagrangian relaxation, and linear programming relaxation. In the heuristic, we generate a population of initial feasible solutions using the branch-and-bound and Lagrangian relaxation methods and create a linear-relaxed solution using the linear programming relaxation method. We combine these feasible and linear-relaxed solutions to fix a portion of hub location variables so as to create a number of restricted hub location subproblems. We then combine the branch-and-bound method to solve these restricted subproblems for iteratively improving solution quality. We discuss in detail the application of the method to the intermodal hub location problem. The discussion is followed by extensive statistical analysis and computational tests, where the analysis shows statistical significance of solutions for guiding the heuristic search and comparisons with other methods indicate that the proposed approach is computationally tractable and is able to obtain competitive results.     

A Note on the Max-Min 0-1 Knapsack Problem

In this paper we propose new lower and upper bounds for the max-min 0-1 knapsack problem, employing a mixture of two relaxations. In addition, in order to expose whether the bounds are practical or not, we implement a method incorporating the bounds to achieve an optimal solution of the problem.     

Joint chance-constrained staffing optimization in multi-skill call centers

This paper concerns the staffing optimization problem in multi-skill call centers. The objective is to find a minimal cost staffing solution while meeting a target level for the quality of service (QoS) to customers. We consider a staffing problem in which joint chance constraints are imposed on the QoS of the day. Our joint chance-constrained formulation is more rational capturing the correlation between different call types, as compared to separate chance-constrained versions considered in previous studies. We show that, in general, the probability functions in the joint-chance constraints display S-shaped curves, and the optimal solutions should belong to the concave regions of the curves. Thus, we propose an approach combining a heuristic phase to identify solutions lying in the concave part and a simulation-based cut generation phase to create outer-approximations of the probability functions. This allows us to find good staffing solutions satisfying the joint-chance constraints by simulation and linear programming. We test our formulation and algorithm using call center examples of up to 65 call types and 89 agent groups, which shows the benefits of our joint-chance constrained formulation and the advantage of our algorithm over standard ones.

     

Corporate structure optimisation for multinational companies

In this paper we consider a multinational corporate structuring problem. This problem involves designing a corporate/organisational structure (across different countries) so as to remit profits from a number of subsidiaries to a single parent company, whilst minimising the tax paid (maximise the amount received at the parent company). This corporate structure is constrained to be a (directed) tree structure.We present a mixed-integer zero-one formulation of the problem that (for the test problems examined) provides very good linear programming relaxation bounds. We also present a tabu search heuristic for the problem which, when combined with the bounds provided by the linear programming relaxation, is able to find provably optimal solutions. Extensions to the basic corporate structuring problem and how they can be dealt with using our heuristic are also discussed.Computational results for the solution (to proven optimality) of publicly available test problems involving up to 150 countries are reported. The largest problem solved previously in the literature to proven optimality involved only 22 countries.     

Job scheduling with dual criteria and sequence-dependent setups: mathematical versus genetic programming

Flexibility, speed, and efficiency are major challenges for operations managers in today's knowledge-intensive organizations. Such requirements are converted into three production scheduling criteria: (a) minimize the impact of setup times in flexible production lines when moving from one product to another, (b) minimize number of tardy jobs, and (c) minimize overall production time, or makespan, for a given set of products or services. There is a wide range of solution methodologies for such NP-hard scheduling problems. While mathematical programming models provide optimal solutions, they become too complex to model for large scheduling problems. Simultaneously, heuristic approaches are simpler and very often independent of the problem size, but provide “good” rather than optimal solutions. This paper proposes and compares two alternative solutions: 0-1 mixed integer linear programming and genetic programming. It also provides guidelines that can be used by practitioners in the process of selecting the appropriate scheduling methodology.     

A general space-time model for combinatorial optimization problems (and not only)

We consider the problem of defining a strategy consisting of a set of facilities taking into account also the location where they have to be assigned and the time in which they have to be activated. The facilities are evaluated with respect to a set of criteria. The plan has to be devised respecting some constraints related to different aspects of the problem such as precedence restrictions due to the nature of the facilities. Among the constraints, there are some related to the available budget. We consider also the uncertainty related to the performances of the facilities with respect to considered criteria and plurality of stakeholders participating to the decision. The considered problem can be seen as the combination of some prototypical operations research problems: knapsack problem, location problem and project scheduling. Indeed, the basic brick of our model is a variable x_ilt which takes value 1 if facility i is activated in location l at time t, and 0 otherwise. Due to the conjoint consideration of a location and a time in the decision variables, what we propose can be seen as a general space-time model for operations research problems. We discuss how such a model permits to handle complex problems using several methodologies including multiple attribute value theory and multiobjective optimization. With respect to the latter point, without any loss of the generality, we consider the compromise programming and an interactive methodology based on the Dominance-based Rough Set Approach. We illustrate the application of our model with a simple didactic example.     

The Knapsack Sharing Problem: An Exact Algorithm

In this paper, we propose an exact algorithm for the knapsack sharing problem. The proposed algorithm seems quite efficient in the sense that it solves quickly some large problem instances. The problem is decomposed into a series of single constraint knapsack problems; and by applying the dynamic programming and another strategy, we solve optimally the original problem. The performance of the exact algorithm is evaluated on a set of medium and large problem instances (a total of 240 problem instances). This algorithm is parallelizable and this is one of its important feature.     

Heuristics for the network design problem with connectivity requirements

We consider the NP-complete problem of finding a spanning \(k\)-tree of minimum weight in a complete weighted graph. This problem has a number of applications in designing reliable backbone telecommunication networks. We propose effective algorithms based on a greedy strategy and several variable neighborhood search metaheuristics. We also develop an integer linear programming model for calculating a lower bound. Preliminary numerical experiments using random and real-word data sets are reported to show the effectiveness of our approach. In addition, we compare our approach with known metaheuristics.     

Approximation of knapsack problems with conflict and forcing graphs

We study the classical 0–1 knapsack problem with additional restrictions on pairs of items. A conflict constraint states that from a certain pair of items at most one item can be contained in a feasible solution. Reversing this condition, we obtain a forcing constraint stating that at least one of the two items must be included in the knapsack. A natural way for representing these constraints is the use of conflict (resp. forcing) graphs. By modifying a recent result of Lokstanov et al. (Proceedings of the 25th annual ACM-SIAM symposium on discrete algorithms, SODA, pp 570–581, 2014) we derive a fairly complicated FPTAS for the knapsack problem on weakly chordal conflict graphs. Next, we show that the techniques of modular decompositions and clique separators, widely used in the literature for solving the independent set problem on special graph classes, can be applied to the knapsack problem with conflict graphs. In particular, we can show that every positive approximation result for the atoms of prime graphs arising from such a decomposition carries over to the original graph. We point out a number of structural results from the literature which can be used to show the existence of an FPTAS for several graph classes characterized by the exclusion of certain induced subgraphs. Finally, a PTAS for the knapsack problem with H-minor free conflict graph is derived. This includes planar graphs and, more general, graphs of bounded genus. The PTAS is obtained by expanding a general result of Demaine et al. (Proceedings of 46th annual IEEE symposium on foundations of computer science, FOCS 2005, pp 637–646, 2005). The knapsack problem with forcing graphs can be transformed into a minimization knapsack problem with conflict graphs. It follows immediately that all our FPTAS results of the current and a previous paper carry over from conflict graphs to forcing graphs. In contrast, the forcing graph variant is already inapproximable on planar graphs.     

Multi-time scale Markov decision process approach to strategic network growth of reverse supply chains

This paper addresses a complex set of decisions that surround the growth over time of reverse supply chain networks that collect used products for reuse, refurbishment, and/or recycling by processors. The collection network growth problem is decomposed into strategic, tactical and operational problems. This paper focuses on the strategic problem which is to determine how to allocate capital budget resource effectively to grow the network to meet long term collection targets and collection cost constraints. We model the strategic problem as a Markov decision process which can also be posed as multi-time scale Markov decision problem. The recruitment problem in a tactical level appears as a sub-problem for the strategic model. Using dynamic programming, linear programming and Q-Learning approaches, an heuristic is implemented to solve realistically sized problems. A numerical study demonstrates that the heuristic can obtain a good solution for the large-scale problem in reasonable time which is not possible when trying to obtain the optimal solution with the exact DP approach.     

Distribution planning of bulk lubricants at BP Turkey

We address the distribution planning problem of bulk lubricants at BP Turkey. The problem involves the distribution of different lube products from a single production plant to industrial customers using a heterogeneous fleet. The fleet consists of tank trucks where each tank can only be assigned to a single lube. The objective is to minimize total transportation related costs. The problem basically consists of assigning customer orders to the tanks of the trucks and determining the routes of the tank trucks simultaneously. We model this problem as a 0–1 mixed integer linear program. Since the model is intractable for real-life industrial environment we propose two heuristic approaches and investigate their performances. The first approach is a linear programming relaxation-based algorithm while the second is a rolling-horizon threshold heuristic. We propose two variants of the latter heuristic: the first uses a distance priority whereas the second has a due date priority. Our numerical analysis using company data shows that both variants of the rolling horizon threshold heuristic are able to provide good results fast.     

A Novel Method for Solving Unbounded Knapsack Problem

Knapsack problem is one kind of NP-Complete problem. Unbounded knapsack problems are more complex and harder than general knapsack problem. In this paper, we apply QGAs (Quantum Genetic Algorithms) to solve unbounded knapsack problem and then follow other procedures. First, present the problem into the mode of QGAs and figure out the corresponding genes types and their fitness functions. Then, find the perfect combination of limitation and largest benefit. Finally, the best solution will be found. Primary experiment indicates that our method has well results.     

An improvement on “Integrated production strategy and reuse scenario: A CoFAQ model and case study of mail server system development”

The authors (Tang et al. (2013) [1] developed a CoFAQ model to formulate a solution for the problem of production strategy decision and reuse scenario selection for a software product family. In the previous research, we stated that the CoFAQ model was a 0–1 mixed integer nonlinear program, where only a local optimal solution might be found. In a recent study, we found that the CoFAQ could be transformed into a 0–1 mixed integer linear programming model. By solving the model, a global optimal solution can be obtained. In this paper, we present the improved formulation and the optimal solution for the case study.     

基于协同效应的知识创新团队伙伴选择方法

在知识创新团队的伙伴选择问题中着重考虑了伙伴间的协同效应信息。首先,分析了伙伴之间的协同关系与协同效应,描述了考虑多个协同效应评价指标的知识创新团队伙伴选择问题;然后,建立了团队伙伴选择的数学模型,该模型是一个0-1二次整数规划问题,为了求解该问题,开发了一种GRASP启发式算法;最后,通过一个实例分析说明了所提出方法的可行性和实际应用价值。