A fast approximation algorithm for solving the complete set packing problem

We study the complete set packing problem (CSPP) where the family of feasible subsets may include all possible combinations of objects. This setting arises in applications such as combinatorial auctions (for selecting optimal bids) and cooperative game theory (for finding optimal coalition structures). Although the set packing problem has been well-studied in the literature, where exact and approximation algorithms can solve very large instances with up to hundreds of objects and thousands of feasible subsets, these methods are not extendable to the CSPP since the number of feasible subsets is exponentially large. Formulating the CSPP as an MILP and solving it directly, using CPLEX for example, is impossible for problems with more than 20 objects. We propose a new mathematical formulation for the CSPP that directly leads to an efficient algorithm for finding feasible set packings (upper bounds). We also propose a new formulation for finding tighter lower bounds compared to LP relaxation and develop an efficient method for solving the corresponding large-scale MILP. We test the algorithm with the winner determination problem in spectrum auctions, the coalition structure generation problem in coalitional skill games, and a number of other simulated problems that appear in the literature.     

Job-shop scheduling with resource-time models of operations

The job-shop problems with allocation of continuously-divisible nonrenewable resource is considered. The mathematical models of operations are linear, decreasing functions with respect to an amount of resource. The objective is sequencing operations and allocation of constrained resource such that the project duration is minimized. Thus, the problem considered is a generalization of the classical job-shop problem. Some properties of the optimal solution are presented. The algorithm of solving this problem is based on the disjunctive graphs theory and branch-and-bound technique. The theory of the algorithm is based on the critical path concept using the segment system approach. The special feature of the algorithm is that it gives a complete solution which is associated with each node of the enumeration tree. Possible generalizations of the results presented are indicated.     

The auction algorithm for the transportation problem

The auction algorithm is a parallel relaxation method for solving the classical assignment problem. It resembles a competitive bidding process whereby unassigned persons bid simultaneously for objects, thereby raising their prices. Once all bids are in, objects are awarded to the highest bidder. This paper generalizes the auction algorithm to solve linear transportation problems. The idea is to convert the transportation problem into an assignment problem, and then to modify the auction algorithm to exploit the special structure of this problem. Computational results show that this modified version of the auction algorithm is very efficient for certain types of transportation problems.     

Iterative Algorithm for Solving Triple-Hierarchical Constrained Optimization Problem

Many practical problems such as signal processing and network resource allocation are formulated as the monotone variational inequality over the fixed point set of a nonexpansive mapping, and iterative algorithms to solve these problems have been proposed. This paper discusses a monotone variational inequality with variational inequality constraint over the fixed point set of a nonexpansive mapping, which is called the triple-hierarchical constrained optimization problem, and presents an iterative algorithm for solving it. Strong convergence of the algorithm to the unique solution of the problem is guaranteed under certain assumptions.     

Mathematical programming based heuristics for the 0–1 MIP: a survey

The 0–1 mixed integer programming problem is used for modeling many combinatorial problems, ranging from logical design to scheduling and routing as well as encompassing graph theory models for resource allocation and financial planning. This paper provides a survey of heuristics based on mathematical programming for solving 0–1 mixed integer programs (MIP). More precisely, we focus on the stand-alone heuristics for 0–1 MIP as well as those heuristics that use linear programming techniques or solve a series of linear programming models or reduced problems, deduced from the initial one, in order to produce a high quality solution of a considered problem. Our emphasis will be on how mathematical programming techniques can be used for approximate problem solving, rather than on comparing performances of heuristics.     

Dynamic multi-criteria evaluation of co-evolution strategies for solving stock trading problems

Risk and return are interdependent in a stock portfolio. To achieve the anticipated return, comparative risk should be considered simultaneously. However, complex investment environments and dynamic change in decision making criteria complicate forecasts of risk and return for various investment objects. Additionally, investors often fail to maximize their profits because of improper capital allocation. Although stock investment involves multi-criteria decision making (MCDM), traditional MCDM theory has two shortfalls: first, it is inappropriate for decisions that evolve with a changing environment; second, weight assignments for various criteria are often oversimplified and inconsistent with actual human thinking processes.In 1965, Rechenberg proposed evolution strategies for solving optimization problems involving real number parameters and addressed several flaws in traditional algorithms, such as their use of point search only and their high probability of falling into optimal solution area. In 1992, Hillis introduced the co-evolutionary concept that the evolution of living creatures is interactive with their environments (multi-criteria) and constantly improves the survivability of their genes, which then expedites evolutionary computation. Therefore, this research aimed to solve multi-criteria decision making problems of stock trading investment by integrating evolutionary strategies into the co-evolutionary criteria evaluation model. Since co-evolution strategies are self-calibrating, criteria evaluation can be based on changes in time and environment. Such changes not only correspond with human decision making patterns (i.e., evaluation of dynamic changes in criteria), but also address the weaknesses of multi-criteria decision making (i.e., simplified assignment of weights for various criteria).Co-evolutionary evolution strategies can identify the optimal capital portfolio and can help investors maximize their returns by optimizing the preoperational allocation of limited capital. This experimental study compared general evolution strategies with artificial neural forecast model, and found that co-evolutionary evolution strategies outperform general evolution strategies and substantially outperform artificial neural forecast models. The co-evolutionary criteria evaluation model avoids the problem of oversimplified adaptive functions adopted by general algorithms and the problem of favoring weights but failing to adaptively adjust to environmental change, which is a major limitation of traditional multi-criteria decision making. Doing so allows adaptation of various criteria in response to changes in various capital allocation chromosomes. Capital allocation chromosomes in the proposed model also adapt to various criteria and evolve in ways that resemble thinking patterns.     

Tabu search for large location–allocation problems

Recently it has been demonstrated that the use of simulated annealing is a good alternative for solving the minisum location–allocation problem with rectilinear distances compared with other popular methods. In this study it is shown that the same solution quality and a great saving of computational time can be achieved by using tabu search. It is also possible to transfer this method to location–allocation problems with euclidean distances.     

Enhancing CP-based column generation for integer programs

This is a summary of the author’s Ph.D. thesis supervised by Federico Malucelli and defended on 15 May 2008 at the Politecnico di Milano. The thesis is written in English and is available from the author upon request. This work presents new methods for enhancing the Column Generation approach based on Constraint Programming when it is used for solving combinatorial optimization problems. The methods proposed focus on the interactions between the linear programming solver and the constraint programming solver, and on how they impact on both a single iteration and the overall execution of the Column Generation procedure. The result of this work is the design and implementation of general-purpose optimization algorithms, whose efficiency is proven by solving two very different problems: the Minimum Graph Coloring Problem and a resource allocation problem arising in Wireless Ad Hoc Networks.     

Auction algorithms for network flow problems: A tutorial introduction

This paper surveys a new and comprehensive class of algorithms for solving the classical linear network flow problem and its various special cases such as shortest path, max-flow, assignment, transportation, and transhipment problems. The prototype method, from which the other algorithms can be derived, is the auction algorithm for the assignment problem. This is an intuitive method that operates like a rel auction where persons compete for objects by raising their prices through competitive bidding; the prices can be viewed as dual variables. Conceptually, auction algorithms represent a significant departure from the cost improvement idea that underlies primal simplex and dual ascent methods; at any one iteration, they may deteriorate both the primal and the dual cost. Auction algorithms perform very well for several important types of problems, both in theory and in practice, and they are also well suited for parallel computation.     

A decomposition algorithm for solving certain classes of production-transportation problems with concave production cost

This paper addresses a method for solving two classes of production-transportation problems with concave production cost. By exploiting a special network structure both problems are reduced to a kind of resource allocation problem. It is shown that the resultant problem can be solved by using dynamic programming in time polynomial in the number of supply and demand points and the total demand.The author was partially supported by Grand-in-Aid for Scientific Research of the Ministry of Education, Science and Culture, Grant No. (C)05650061.     

Formalization of a synthesis problem and methods for its solution

A formal formulation is proposed for the synthesis problem of finding objects with certain properties described only by a collection of precedents. A key feature of this formalization is that it is closely related to the pattern recognition theory. A general approach to solving the synthesis problem is described, and particular solution methods are presented in two important cases. For this purpose, a new recognition method is proposed that exhibits a high speed as applied to the data of the structure under study. The performance of the methods is demonstrated on actual data.     

On the convergence of the Weiszfeld algorithm for continuous single facility location–allocation problems

A general family of single facility continuous location–allocation problems is introduced, which includes the decreasingly weighted ordered median problem, the single facility Weber problem with supply surplus, and Weber problems with alternative fast transportation network. We show in this paper that the extension of the well known Weiszfeld iterative decrease method for solving the corresponding location problems with fixed allocation yields an always convergent scheme for the location allocation problems. In a generic way, from each starting point, the limit point will be a locally minimal solution, whereas for each possible exceptional situation, a possible solution is indicated. Some computational results are presented, comparing this method with an alternating location–allocation approach. The research of the second author was partially supported by the grant of the Algerian Ministry of High Education 001BIS/PNE/ENSEIGNANTS/BELGIQUE.     

Fast algorithms for collision and proximity problems involving moving geometric objects

Consider a set of geometric objects, such as points, line segments, or axes-parallel hyperrectangles in ^d, that move with constant but possibly different velocities along linear trajectories. Efficient algorithms are presented for several problems defined on such objects, such as determining whether any two objects ever collide and computing the minimum interpoint separation or minimum diameter that ever occurs. In particular, two open problems from the literature are solved: deciding in o(n²) time if there is a collision in a set of n moving points in ², where the points move at constant but possibly different velocities, and the analogous problem for detecting a red-blue collision between sets of red and blue moving points. The strategy used involves reducing the given problem on moving objects to a different problem on a set of static objects, and then solving the latter problem using techniques based on sweeping, orthogonal range searching, simplex composition, and parametric search.     

An Algorithm for Solving a Resource Allocation Problem

The paper discusses the solution of a resource allocation problem and a new method for solving a special case of the problem. An algorithm for solving the general problem is presented, and computational experience comparing it with existing methods is given.     

A new dynamic programming formulation for scheduling independent tasks with common due date on parallel machines

This paper deals with a scheduling problem of independent tasks with common due date where the objective is to minimize the total weighted tardiness. The problem is known to be ordinary NP-hard in the case of a single machine and a dynamic programming algorithm was presented in the seminal work of Lawler and Moore [E.L. Lawler, J.M. Moore, A functional equation and its application to resource allocation and sequencing problems, Management Science 16 (1969) 77–84]. In this paper, this algorithm is described and discussed. Then, a new dynamic programming algorithm is proposed for solving the single machine case. These methods are extended for solving the identical and uniform parallel-machine scheduling problems.     

An architecture for solving sequencing and resource allocation problems using approximation methods

In the search for better optimisation techniques, new methods that mix artificial intelligence and operations research have emerged. Search heuristics are integrated with optimisation algorithms. Approximation methods, like Hill Climbing, Simulated Annealing, and Tabu Search, that have been used with success in combinatorial optimisation problems, are one of such research lines. This paper presents the key elements of approximation methods and combines them in a tool appropriate for solving sequencing and resource allocation problems. The system permits a clear division between problem specification and problem solving, allowing a declarative representation and therefore minimising developing costs. The key issues discussed in this work are a model for representing this class of problems in a standard form, a set of strategies for applying the approximation methodology, and an expert system that dynamically manipulates the strategies' parameters.     

Resource capacity allocation to stochastic dynamic competitors: knapsack problem for perishable items and index-knapsack heuristic

In this paper we propose an approach for solving problems of optimal resource capacity allocation to a collection of stochastic dynamic competitors. In particular, we introduce the knapsack problem for perishable items, which concerns the optimal dynamic allocation of a limited knapsack to a collection of perishable or non-perishable items. We formulate the problem in the framework of Markov decision processes, we relax and decompose it, and we design a novel index-knapsack heuristic which generalizes the index rule and it is optimal in some specific instances. Such a heuristic bridges the gap between static/deterministic optimization and dynamic/stochastic optimization by stressing the connection between the classic knapsack problem and dynamic resource allocation. The performance of the proposed heuristic is evaluated in a systematic computational study, showing an exceptional near-optimality and a significant superiority over the index rule and over the benchmark earlier-deadline-first policy. Finally we extend our results to several related revenue management problems.     

Lower and upper bounds for location-arc routing problems with vehicle capacity constraints

This paper addresses multi-depot location arc routing problems with vehicle capacity constraints. Two mixed integer programming models are presented for single and multi-depot problems. Relaxing these formulations leads to other integer programming models whose solutions provide good lower bounds for the total cost. A powerful insertion heuristic has been developed for solving the underlying capacitated arc routing problem. This heuristic is used together with a novel location–allocation heuristic to solve the problem within a simulated annealing framework. Extensive computational results demonstrate that the proposed algorithm can find high quality solutions. We also show that the potential cost saving resulting from adding location decisions to the capacitated arc routing problem is significant.     

An improved linearization technique for a class of quadratic 0-1 programming problems

The recent research on linearization techniques for solving 0-1 quadratic programming problems focuses on providing concise models and tightening constraint bounds. In this paper, we propose a computational enhancement for a linearization technique to make the linearized model much faster to solve. We investigate the computational performance of the proposed approach, by comparing it with other linearization techniques on a class of 0-1 quadratic programming problems. We can further speed up the proposed technique by heuristically tightening the constraint bounds, as demonstrated by solving the uncapacitated single allocation p-hub median problem using the Civil Aeronautics Board data.     

Nonlinear Lagrangian Theory for Nonconvex Optimization

The Lagrangian function in the conventional theory for solving constrained optimization problems is a linear combination of the cost and constraint functions. Typically, the optimality conditions based on linear Lagrangian theory are either necessary or sufficient, but not both unless the underlying cost and constraint functions are also convex.We propose a somewhat different approach for solving a nonconvex inequality constrained optimization problem based on a nonlinear Lagrangian function. This leads to optimality conditions which are both sufficient and necessary, without any convexity assumption. Subsequently, under appropriate assumptions, the optimality conditions derived from the new nonlinear Lagrangian approach are used to obtain an equivalent root-finding problem. By appropriately defining a dual optimization problem and an alternative dual problem, we show that zero duality gap will hold always regardless of convexity, contrary to the case of linear Lagrangian duality.