Integer programming formulations for the minimum weighted maximal matching problem

Given an undirected graph, the problem of finding a maximal matching that has minimum total weight is NP-hard. This problem has been studied extensively from a graph theoretical point of view. Most of the existing literature considers the problem in some restricted classes of graphs and give polynomial time exact or approximation algorithms. On the contrary, we consider the problem on general graphs and approach it from an optimization point of view. In this paper, we develop integer programming formulations for the minimum weighted maximal matching problem and analyze their efficacy on randomly generated graphs. We also compare solutions found by a greedy approximation algorithm, which is based on the literature, against optimal solutions. Our results show that our integer programming formulations are able to solve medium size instances to optimality and suggest further research for improvement.     

A Lagrangian relaxation approach to solve the second phase of the exam scheduling problem

The problem of scheduling final exams at a large university can be viewed as a three phase process. The first phase consists of grouping the exams into sets called exam blocks. The second phase deals with the assignment of exam blocks to exam days and the third phase consists of arranging the exam days and also arranging the blocks within days.In this paper, we present new integer programming formulations for the second phase of the scheduling problem. We present an integer program with a single objective of minimizing the number of students with two or more exams per day. We then present a Lagrangian relaxation based solution procedure to solve this problem. Further, we present a bicriterion integer programming formulation to minimize the number of students with two exams per day and the number of students with three exams per day. Finally, we present some computational experience using randomly generated problems as well as real world data obtained from the State University of New York at Buffalo.     

非线性整规划中的精确光滑罚函数

本文提出了几个非线性整规划 的全局精确光滑罚函数，每个罚函数有两个参数，并且给出了每个罚函数的精确罚参数的估计值，最后，我们举例说明了所提出的罚方法在具有整系数多项式目标函数以约束函数的整数规划中的应用。     

The Steiner tree problem I: Formulations,compositions and extension of facets

In this paper we give some integer programming formulations for the Steiner tree problem on undirected and directed graphs and study the associated polyhedra. We give some families of facets for the undirected case along with some compositions and extensions. We also give a projection that relates the Steiner tree polyhedron on an undirected graph to the polyhedron for the corresponding directed graph. This is used to show that the LP-relaxation of the directed formulation is superior to the LP-relaxation of the undirected one.Corresponding author.     

The single-assignment hub covering problem: Models and linearizations

We study the hub covering problem which, so far, has remained one of the unstudied hub location problems in the literature. We give a combinatorial and a new integer programming formulation of the hub covering problem that is different from earlier integer programming formulations. Both new and old formulations are nonlinear binary integer programs. We give three linearizations for the old model and one linearization for the new one and test their computational performances based on 80 instances of the CAB data set. Computational results indicate that the linear version of the new model performs significantly better than the most successful linearization of the old model both in terms of average and maximum CPU times as well as in core storage requirements.     

Models for a Steiner multi-ring network design problem with revenues

The Steiner multi-ring network design problem with revenues consists of designing node-disjoint multiple rings connected by a specific node (hub) and passing through all the nodes with high priority of service and some of the nodes with low priority of service. The number of nodes in each ring has an upper bound to assure a certain level of service. Besides the usual arc link costs, we also consider revenues between each pair of nodes in the same ring, even when they are not connected by a direct link. The objective is to minimize the difference between the total connection cost and total revenue. The problem is a generalization of the problem studied in Gouveia and Pires (Eur J Oper Res 133:21–31, 2001a) and it can also be seen as a combination of variants of two NP-Hard problems, the vehicle routing problem and the maximum edge-weighted clique problem. We introduce and discuss two types of integer linear programming formulations and propose some valid inequalities to strengthen the linear programming relaxation. Computational results are presented to evaluate the quality of the linear programming relaxation bounds associated with these formulations as well as efficiency of the models to obtain the optimal integer solutions.     

The Red–Blue transportation problem

This paper considers the Red–Blue Transportation Problem (Red–Blue TP), a generalization of the transportation problem where supply nodes are partitioned into two sets and so-called exclusionary constraints are imposed. We encountered a special case of this problem in a hospital context, where patients need to be assigned to rooms. We establish the problem’s complexity, and we compare two integer programming formulations. Furthermore, a maximization variant of Red–Blue TP is presented, for which we propose a constant-factor approximation algorithm. We conclude with a computational study on the performance of the integer programming formulations and the approximation algorithms, by varying the problem size, the partitioning of the supply nodes, and the density of the problem.     

On discrete lot-sizing and scheduling on identical parallel machines

We consider the multi-item discrete lot-sizing and scheduling problem on identical parallel machines. Based on the fact that the machines are identical, we introduce aggregate integer variables instead of individual variables for each machine. For the problem with start-up costs, we show that the inequalities based on a unit flow formulation for each machine can be replaced by a single integer flow formulation without any change in the resulting LP bound. For the resulting integer lot-sizing with start-ups subproblem, we show how inequalities for the unit demand case can be generalized and how an approximate version of the extended formulation of Eppen and Martin can be constructed. The results of some computational experiments carried out to compare the effectiveness of the various mixed-integer programming formulations are presented.     

Assignment problems with changeover cost

We consider some variant models, having changeover cost, of the assignment problem. In these models, multiple assignments to an operator are allowed. In addition to assignment costs, a changeover cost is incurred if an operator does one job after another is completed. Two different types of changeover costs and related two models are considered. Mathematical programming formulations are given for the models. When changeover costs are dependent on the operator but independent of the jobs and are non-negative, a linear programming model is obtained. For the case when changeover costs are dependent on the jobs, a linear integer programming formulation is obtained. We also show that, this problem is strongly NP-hard. A heuristic solution method is suggested for it. Numerical findings on the performance of the method are given.     

Ramsey theory and integrality gap for the independent set problem

We discuss the effectiveness of integer programming for solving large instances of the independent set problem. Typical LP formulations, even strengthened by clique inequalities, yield poor bounds for this problem. We show that a strong bound can be obtained by the use of the so-called rank inequalities, which generalize the clique inequalities. For some problems the clique inequalities imply the rank inequalities, and then a strong bound is guaranteed already by the simpler formulation.     

ILP approaches to the blockmodel problem

Blockmodelling is a method for identifying structural similarities or equivalences between elements which has applications in a variety of contexts, including multiattribute performance assessment. One criterion for forming blocks results in a difficult non-linear integer programme. We give several integer linear programming formulations of this problem and provide comparative computational results. We show that methods of reducing symmetry proposed by Sherali and Smith are not effective in this case and propose an iterative approach in which the size of the problem is reduced.     

On the use of internal rate of return in linear and integer programming

Internal rate of return (IRR) is used as a criterion many investment decisions. For example many issuers of new municipal debt evaluate competitive bids on the basis of IRR. We incorporate IRR into mathematical programming formulations in such a way that the resulting problem becomes linear. This linearization permits linear programming and integer linear programming algorithms to be brought to bear on problems which had heretofore been solved in an iterative, time consuming fashion.     

The partition problem

In this paper we describe several forms of thek-partition problem and give integer programming formulations of each case. The dimension of the associated polytopes and some basic facets are identified. We also give several valid and facet defining inequalities for each of the polytopes.Partial Support from NSF Grants DMS 8606188 and ECS 8800281 is gratefully acknowledged.     

Threshold Boolean form for joint probabilistic constraints with random technology matrix

We develop a new modeling and solution method for stochastic programming problems that include a joint probabilistic constraint in which the multirow random technology matrix is discretely distributed. We binarize the probability distribution of the random variables in such a way that we can extract a threshold partially defined Boolean function (pdBf) representing the probabilistic constraint. We then construct a tight threshold Boolean minorant for the pdBf. Any separating structure of the tight threshold Boolean minorant defines sufficient conditions for the satisfaction of the probabilistic constraint and takes the form of a system of linear constraints. We use the separating structure to derive three new deterministic formulations for the studied stochastic problem, and we derive a set of strengthening valid inequalities. A crucial feature of the new integer formulations is that the number of integer variables does not depend on the number of scenarios used to represent uncertainty. The computational study, based on instances of the stochastic capital rationing problem, shows that the mixed-integer linear programming formulations are orders of magnitude faster to solve than the mixed-integer nonlinear programming formulation. The method integrating the valid inequalities in a branch-and-bound algorithm has the best performance.     

Branch-and-Price Algorithms for the One-Dimensional Cutting Stock Problem

We compare two branch-and-price approaches for the cutting stock problem. Each algorithm is based on a different integer programming formulation of the column generation master problem. One formulation results in a master problem with 0–1 integer variables while the other has general integer variables. Both algorithms employ column generation for solving LP relaxations at each node of a branch-and-bound tree to obtain optimal integer solutions. These different formulations yield the same column generation subproblem, but require different branch-and-bound approaches. Computational results for both real and randomly generated test problems are presented.     

The capacitated multiple allocation hub location problem: Formulations and algorithms

In this paper we consider and present formulations and solution approaches for the capacitated multiple allocation hub location problem. We present a new mixed integer linear programming formulation for the problem. We also construct an efficient heuristic algorithm, using shortest paths. We incorporate the upper bound obtained from this heuristic in a linear-programming-based branch-and-bound solution procedure. We present the results of extensive computational experience with both the heuristic and the exact methods.     

The reformulation of two mixed integer programming problems

Two practical problems are described, each of which can be formulated in more than one way as a mixed integer programming problem. The computational experience with two formulations of each problem is given. It is pointed out how in each case a reformulation results in the associated linear programming problem being more constrained. As a result the reformulated mixed integer problem is easier to solve. The problems are a multi-period blending problem and a mining investment problem.     

Exact Penalty Functions for Nonlinear Integer Programming Problems

In this work, we study exact continuous reformulations of nonlinear integer programming problems. To this aim, we preliminarily state conditions to guarantee the equivalence between pairs of general nonlinear problems. Then, we prove that optimal solutions of a nonlinear integer programming problem can be obtained by using various exact penalty formulations of the original problem in a continuous space.     

The one-warehouse multi-retailer problem: reformulation, classification, and computational results

We consider the one-warehouse multi-retailer problem where a warehouse replenishes multiple retailers with deterministic dynamic demands over a horizon. The problem is to determine when and how much to order to the warehouse and retailers such that the total system-wide costs are minimized. We propose a new (combined transportation and shortest path based) integer programming reformulation for the problem in addition to the echelon stock and transportation based formulations in the literature. We analyze the strength of the LP relaxations of three formulations and show that the new formulation is stronger than others. We also show that the new and transportation based formulations are equivalent for the joint replenishment problem, where the warehouse is a crossdocking facility. We extend all formulations to the case with initial inventory at the warehouse and reveal the relation among their LP relaxations. We present our computational experiments with all formulations over a set of randomly generated test instances.     

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.