Orbitopal fixing

The topic of this paper are integer programming models in which a subset of 0/1-variables encode a partitioning of a set of objects into disjoint subsets. Such models can be surprisingly hard to solve by branch-and-cut algorithms if the order of the subsets of the partition is irrelevant, since this kind of symmetry unnecessarily blows up the search tree.We present a general tool, called orbitopal fixing, for enhancing the capabilities of branch-and-cut algorithms in solving such symmetric integer programming models. We devise a linear time algorithm that, applied at each node of the search tree, removes redundant parts of the tree produced by the above mentioned symmetry. The method relies on certain polyhedra, called orbitopes, which have been introduced in [14]. It does, however, not explicitly add inequalities to the model. Instead, it uses certain fixing rules for variables. We demonstrate the computational power of orbitopal fixing at the example of a graph partitioning problem.     

A direct bijection between descending plane partitions with no special parts and permutation matrices

We present a direct bijection between descending plane partitions with no special parts and permutation matrices. This bijection has the desirable property that the number of parts of the descending plane partition corresponds to the inversion number of the permutation. Additionally, the number of maximum parts in the descending plane partition corresponds to the position of the one in the last column of the permutation matrix. We also discuss the possible extension of this approach to finding a bijection between descending plane partitions and alternating sign matrices.     

A hybrid two-stage flowshop with part family,batch production,major and minor set-ups

In this paper, we consider a two-stage hybrid flowshop with a single machine at stage 1 and multiple identical machines at stage 2. The flowshop is characterized by major and minor setups, part families and batch production allowing split and no split at stage 2. The parts within a family share a major setup and the parts in a batch share a minor setup. The objective of our problem is to minimize the makespan. We develop two allocation policies with one as a traditional way (called Forward Heuristic) and the other as a non-traditional way (called Backward Heuristic). We also develop several effective sequence rules to further improve the makespan. The computational results show that the Backward Heuristic, in general, is superior to the Forward Heuristic. The sequence rules developed in this paper also perform better than the traditional sequence rules such as SPT and LPT.     

On random partitions

Let S be a finite set with n labeled elements. One of the partitions of S is selected at random each of them has the same probability. Harper determined the expected number of subsets in the random partition. Haigh studied the probability that the random partition has (at least one) subset of a given size. The present paper considers the expected number of subsets in a given size. Average and maximum are also determined. Results are generalized for the case if the number of subsets in the partition is also fixed.     

A successive approximations method for a cellular manufacturing problem

The problem of interest is to partition a collection of machines into production cells so that a given set of part-manufacturing requirements may be carried out optimally. In the present case transitions of parts between different cells is the only measure of machine partition goodness. The present formulation and approximate solution of this optimization problem is best described as one of successive approximations or as a one-at-a-time method. An initial cellular structure is taken and an easy part assignment optimization routine executed. With the part assignment fixed, a heuristic is employed to find an improved cell structure. These bipartite iterations continue until a convergence criterion is satisfied. Several small computer examples are provided and the straightforward requirements for large problem adaptation.     

Solving the segmentation problem for the 2010 Argentine census with integer programming

One of the most challenging tasks within the planning of a demographic census is to partition each census track into sets of homes such that each census taker visits exactly one set from this partition. In this work we introduce the home segmentation problem, which consists in designing such a partition subject to specific constraints. We present an integer programming-based algorithm for this problem, and we report the application of this algorithm for the 2010 census in the main province in Argentina.     

Three-stage recursive least squares parameter estimation for controlled autoregressive autoregressive systems

A three-stage recursive least squares parameter estimation algorithm is derived for controlled autoregressive autoregressive (CARAR) systems. The basic idea is to decompose a CARAR system into three subsystems, one of which contains one parameter vector, and to identify the parameters of each subsystem one by one. Compared with the recursive generalized least squares algorithm, the dimensions of the involved covariance matrices in each subsystem become small and thus the proposed algorithm has a high computational efficiency. Finally, we verify the proposed algorithm with a simulation example.     

Linear and quadratic programming approaches for the general graph partitioning problem

The graph partitioning problem is to partition the vertex set of a graph into a number of nonempty subsets so that the total weight of edges connecting distinct subsets is minimized. Previous research requires the input of cardinalities of subsets or the number of subsets for equipartition. In this paper, the problem is formulated as a zero-one quadratic programming problem without the input of cardinalities. We also present three equivalent zero-one linear integer programming reformulations. Because of its importance in data biclustering, the bipartite graph partitioning is also studied. Several new methods to determine the number of subsets and the cardinalities are presented for practical applications. In addition, hierarchy partitioning and partitioning of bipartite graphs without reordering one vertex set, are studied.     

Length of clustering algorithms based on random walks with an application to neuroscience

In this paper we show how the notions of conductance and cutoff can be used to determine the length of the random walks in some clustering algorithms. We consider graphs which are globally sparse but locally dense. They present a community structure: there exists a partition of the set of vertices into subsets which display strong internal connections but few links between each other. Using a distance between nodes built on random walks we consider a hierarchical clustering algorithm which provides a most appropriate partition. The length of these random walks has to be chosen in advance and has to be appropriate. Finally, we introduce an extension of this clustering algorithm to dynamical sequences of graphs on the same set of vertices.     

A two-level graph partitioning problem arising in mobile wireless communications

In the k -partition problem (k-PP), one is given an edge-weighted undirected graph, and one must partition the node set into at most k subsets, in order to minimise (or maximise) the total weight of the edges that have their end-nodes in the same subset. Various hierarchical variants of this problem have been studied in the context of data mining. We consider a ‘two-level’ variant that arises in mobile wireless communications. We show that an exact algorithm based on intelligent preprocessing, cutting planes and symmetry-breaking is capable of solving small- and medium-size instances to proven optimality, and providing strong lower bounds for larger instances.     

Optimal control of impulsive switched systems with minimum subsystem durations

This paper presents a new computational approach for solving optimal control problems governed by impulsive switched systems. Such systems consist of multiple subsystems operating in succession, with possible instantaneous state jumps occurring when the system switches from one subsystem to another. The control variables are the subsystem durations and a set of system parameters influencing the state jumps. In contrast with most other papers on the control of impulsive switched systems, we do not require every potential subsystem to be active during the time horizon (it may be optimal to delete certain subsystems, especially when the optimal number of switches is unknown). However, any active subsystem must be active for a minimum non-negligible duration of time. This restriction leads to a disjoint feasible region for the subsystem durations. The problem of choosing the subsystem durations and the system parameters to minimize a given cost function is a non-standard optimal control problem that cannot be solved using conventional techniques. By combining a time-scaling transformation and an exact penalty method, we develop a computational algorithm for solving this problem. We then demonstrate the effectiveness of this algorithm by considering a numerical example on the optimization of shrimp harvesting operations.     

Minimizing number of tardy jobs on a batch processing machine with incompatible job families

In this paper we consider the problem of minimizing number of tardy jobs on a single batch processing machine. The batch processing machine is capable of processing up to B jobs simultaneously as a batch. We are given a set of n jobs which can be partitioned into m incompatible families such that the processing times of all jobs belonging to the same family are equal and jobs of different families cannot be processed together. We show that this problem is NP-hard and present a dynamic programming algorithm which has polynomial time complexity when the number of job families and the batch machine capacity are fixed. We also show that when the jobs of a family have a common due date the problem can be solved by a pseudo-polynomial time procedure.     

Flow-shop scheduling with setup and assembly operations

A scheduling model for a production system including machining, setup and assembly operations is considered. Production of a number of single-item products is ordered. Each product is made by assembling a set of several different parts. First, the parts are manufactured in a flow-shop consisting of multiple machines. Then, they are assembled into products on a single assembly stage. Setup operation and setup time are needed when a machine starts processing the parts or it changes items. The operations are partitioned into several blocks. Each block consists of the machining operations, the setup operations, and the assembly operation(s) for one or several products. The parts of the same item in a block are processed successively. The objective function is the mean completion time for all products. We consider a problem to partition the operations into blocks and sequence the parts in each block so as to minimize the objective function. Solution procedures using pseudo-dynamic programming and a branch-and-bound method are proposed. Computational experiments are carried out to evaluate the performance of the solution procedures. It has been found that a good near-optimal schedule is obtained efficiently by the proposed solution procedures.     

The number of feasible designs in a compatibility matrix

Many design and planning problems consist of a number of distinct subsystems. Generally, there are several possible alternatives for design of a subsystem. However, an alternative for one subsystem may be incompatible with an alternative for another subsystem. Thus, a feasible design is one that incorporates one alternative for each subsystem such that no pairwise incompatibilities exist. Several such design and planning problems have been formulated as compatibility matrices. The feasible designs can be identified by using an efficient algorithm. This paper shows that, in general, the exact number of feasible designs decreases exponentially with the increase in the number of incompatible pairs. This finding should motivate more potential users to employ the compatibility matrix approach.     

Generating pareto-optimal alternatives by a nonfeasible hierarchical method

A hierarchical algorithm for generating Pareto-optimal alternatives for convex multicriteria problems is derived. At the upper level, values for Lagrange multipliers of the coupling constraints are first given. Then at the subsystems, Pareto-optimal values are determined for the subsystem objectives, whereby an additional term or an additional objective is included due to the Lagrange multipliers. In the subsystem optimizations, the coupling equations between the subsystems are not satisfied; therefore, the method is called nonfeasible. Finally, the upper level checks which of the subsystem solutions satisfy the coupling constraints; these solutions are Pareto-optimal solutions for the overall system.     

An efficiency measurement framework for multi-stage production systems

We develop an efficiency measurement framework for systems composed of two subsystems arranged in series that simultaneously computes the efficiency of the aggregate system and each subsystem. Our approach expands the technology sets of each subsystem by allowing each to acquire resources from the other in exchange for delivery of the appropriate (intermediate or final) product, and to form composites from both subsystems. Managers of each subsystem will not agree to ‘`vertical integration’' initiatives unless each subsystem will be more efficient than what each can achieve by separately applying conventional efficiency analysis. A Pareto Efficient frontier characterizes the acceptable set of efficiencies of each subsystem from which the managers will negotiate to select the final outcome. Three proposals for the choice for the Pareto efficient point are discussed: the one that achieves the largest equiproportionate reduction in the classical efficiencies; the one that achieves the largest equal reduction in efficiency; and the one that maximizes the radial contraction in the aggregate consumption of resources originally employed before integration. We show how each choice for the Pareto efficient point determines a derived measure of aggregate efficiency. An extensive numerical example is used to illustrate exactly how the 2 subsystems can significantly improve their operational efficiencies via integration beyond what would be predicted by conventional analysis.     

Computing lower and upper bounds for a large-scale industrial job shop scheduling problem

In this paper we present a case study from the lighting industry concerned with the scheduling of a set of job families each representing the production of a particular end-item in a given quantity. It is a job shop type problem, where each job family has a number of routing alternatives, and the solution has to respect batching and machine availability constraints. All jobs of the same job family have a common release date and a common due date, and they differ only in size. The objective is to minimize the total tardiness of the job families, rather than that of individual jobs. We propose a two-phase method based on solving a mixed-integer linear program and then improving the initial solution by tabu search. We evaluate our method on real-world as well as generated instances.     

The satisfactory partition problem

The SATISFACTORY PARTITION problem consists in deciding if a given graph has a partition of its vertex set into two nonempty parts such that each vertex has at least as many neighbors in its part as in the other part. This problem was introduced by Gerber and Kobler [Partitioning a graph to satisfy all vertices, Technical report, Swiss Federal Institute of Technology, Lausanne, 1998; Algorithmic approach to the satisfactory graph partitioning problem, European J. Oper. Res. 125 (2000) 283-291] and further studied by other authors but its complexity remained open until now. We prove in this paper that SATISFACTORY PARTITION, as well as a variant where the parts are required to be of the same cardinality, are NP-complete. However, for graphs with maximum degree at most 4 the problem is polynomially solvable. We also study generalizations and variants of this problem where a partition into k nonempty parts (k?3) is requested.     

An optimal algorithm for generating equivalence relations on a linear array of processors

We describe a cost-optimal parallel algorithm for enumerating all partitions (equivalence relations) of the set {1, ...,n}, in lexicographic order. The algorithm is designed to be executed on a linear array of processors. It usesn processors, each having constant size memory and each being responsible for producing one element of a given set partition. Set partitions are generated with constant delay leading to anO(B _n) time solution, whereB _n is the total number of set partitions. The same method can be generalized to enumerate some other combinatorial objects such as variations. The algorithm can be made adaptive, i.e. to run on any prespecified number of processors. To illustrate the model of parallel computation, a simple case of enumerating subsets of the set {1, ...,n}, having at mostm (n) elements is also described.The research is partialy supported by NSERC operating grant OGPIN 007.