Determination of optimal vertices from feasible solutions in unimodular linear programming

In this paper we consider a linear programming problem with the underlying matrix unimodular, and the other data integer. Given arbitrary near optimum feasible solutions to the primal and the dual problems, we obtain conditions under which statements can be made about the value of certain variables in optimal vertices. Such results have applications to the problem of determining the stopping criterion in interior point methods like the primal—dual affine scaling method and the path following methods for linear programming.This author's research is partially supported by NSF grant DDM-8921835 and Airforce Grant AFSOR-88-0088.     

Max Horn SAT and the minimum cut problem in directed hypergraphs

In this paper we consider the Maximum Horn Satisfiability problem, which is reduced to the problem of finding a minimum cardinality cut on a directed hypergraph. For the latter problem, we propose different IP formulations, related to three different definitions of hyperpath weight. We investigate the properties of their linear relaxations, showing that they define a hierarchy. The weakest relaxation is shown to be equivalent to the relaxation of a well known IP formulation of Max Horn SAT, and to a max-flow problem on hypergraphs. The tightest relaxation, which is a disjunctive programming problem, is shown to have integer optimum. The intermediate relaxation consists in a set covering problem with a possible exponential number of constraints. This latter relaxation provides an approximation of the convex hull of the integer solutions which, as proven by the experimental results given, is much tighter than the one known in the literature. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Corresponding author.     

Exact and heuristic procedures for the material handling circular flow path design problem

In this study we develop optimization, decomposition, and heuristic procedures to design a unidirectional loop flow pattern along with the pickup and delivery station locations for unit load automated material handling vehicles. The layout of the facility is fixed, the edges on the boundary of the manufacturing cells are candidates to form the unidirectional loop flow path, and a set of nodes located at an intermediate point on each edge are candidates for pickup and delivery stations of the cell formed by those edges. The objective is to minimize the total loaded and empty vehicle trip distances. The empty vehicle dispatching policy underlying the model is the shortest trip distance first. A binary integer programming model describes the problem of determining the flow path and locations of the pickup and delivery stations in which we then provide a decomposition procedure based on a loop enumeration strategy coupled with a streamlined integer linear programming model. It is shown that only a small proportion of all loops have to be enumerated to reach an optimum. Therefore a truncated version of this algorithm should yield a good heuristic. Finally we propose a neighbourhood search heuristic method and report on its performance.     

Order selection on a single machine with high set-up costs

We study the problem of allocating a limited quantity of a single manufacturing resource to produce a subset of possible part-types. Customer orders require one or more part-types. We assume that revenue is received for an order only if it is completely filled, and that set-up costs and order revenues dominate the variable costs of production. We present a heuristic for the solution of our problem, as well as families of cutting-planes for an integer programming formulation. Computational results on a set of random test problems indicate that the heuristic is quite effective in producing near optimal solutions. The cutting-planes appear to be quite useful in reducing the number of linear programming solutions required by branch-and-bound.     

The Solution of a Railway Locomotive Scheduling Problem

A method is described for finding a minimum cost set of schedules for railway locomotives to work a given set of trains. The times at which the trains start may be fixed or variable. A heuristic method, based on a linear programming model, is described. This gives good integer solutions to the problem.     

A single machine scheduling problem with availability constraints and sequence-dependent setup costs

We study a single machine scheduling problem with availability constraints and sequence-dependent setup costs, with the aim of minimizing the makespan. To the authors’ knowledge, this problem has not been treated as such in the operations research literature. We derive in this paper a mixed integer programming model to deal with such scheduling problem. Computational tests showed that commercial solvers are capable of solving only small instances of the problem. Therefore, we propose two ways for reducing the execution time, namely a valid inequality that strengthen the linear relaxation and an efficient heuristic procedure that provides a starting feasible solution to the solver. A substantial gain is achieved both in terms of the linear programming relaxation bound and in terms of the time to obtain an integer optimum when we use the enhanced model in conjunction with providing to the solver the solution obtained by the proposed heuristic.     

An ILP based hierarchical global routing approach for VLSI ASIC design

The use of integrated circuits in high-performance computing, telecommunications, and consumer electronics has been growing at a very fast pace. The level of integration as measured by the number of logic gates in a chip has been steadily rising due to the rapid progress in processing and interconnect technology. The interconnect delay in VLSI circuits has become a critical determiner of circuit performance. As a result, circuit layout is starting to play a more important role in today’s chip designs. Global routing is one of the key sub-problems of circuit layout which involves finding an approximate path for the wires connecting the elements of the circuit without violating resource constraints. In this paper, several integer programming (ILP) based global routing models are fully investigated and explored. The resulting ILP problem is relaxed and solved as a linear programming (LP) problem followed by a rounding heuristic to obtain an integer solution. Experimental results obtained show that the proposed combined WVEM (wirelength, via, edge capacity) model can optimize several global routing objectives simultaneously and effectively. In addition, several hierarchical methods are combined with the proposed flat ILP based global router to reduce the CPU time by about 66% on average for edge capacity model (ECM).     

Solving Large Airline Crew Scheduling Problems: Random Pairing Generation and Strong Branching

The airline crew scheduling problem is the problem of assigning crew itineraries to flights. We develop a new approach for solving the problem that is based on enumerating hundreds of millions random pairings. The linear programming relaxation is solved first and then millions of columns with best reduced cost are selected for the integer program. The number of columns is further reduced by a linear programming based heuristic. Finally an integer solution is obtained with a commercial integer programming solver. The branching rule of the solver is enhanced with a combination of strong branching and a specialized branching rule. The algorithm produces solutions that are significantly better than ones found by current practice.     

Solving a capacitated hub location problem

In this paper we address a problem consisting of determining the routes and the hubs to be used in order to send, at minimum cost, a set of commodities from sources to destinations in a given capacitated network. The capacities and costs of the arcs and hubs are given, and the arcs connecting the hubs are not assumed to create a complete graph. We present a mixed integer linear programming formulation and describe two branch-and-cut algorithms based on decomposition techniques. We evaluate and compare these algorithms on instances with up to 25 commodities and 10 potential hubs. One of the contributions of this paper is to show that a Double Benders’ Decomposition approach outperforms the standard Benders’ Decomposition, which has been widely used in recent articles on similar problems. For larger instances we propose a heuristic approach based on a linear programming relaxation of the mixed integer model. The heuristic turns out to be very effective and the results of our computational experiments show that near-optimal solutions can be derived rapidly.     

Branching on hyperplane methods for mixed integer linear and convex programming using adjoint lattices

We present branching-on-hyperplane methods for solving mixed integer linear and mixed integer convex programs. In particular, we formulate the problem of finding a good branching hyperplane using a novel concept of adjoint lattice. We also reformulate the problem of rounding a continuous solution to a mixed integer solution. A worst case complexity of a Lenstra-type algorithm is established using an approximate log-barrier center to obtain an ellipsoidal rounding of the feasible set. The results for the mixed integer convex programming also establish a complexity result for the mixed integer second order cone programming and mixed integer semidefinite programming feasibility problems as a special case. Our results motivate an alternative reformulation technique and a branching heuristic using a generalized (e.g., ellipsoidal) norm reduced basis available at the root node.     

A fast algorithm for near cost optimal line plans

We consider the design of line plans in public transport at a minimal total cost. Both, linear and nonlinear integer programming are adequate and intuitive modeling approaches for this problem. We present a heuristic variable fixing procedure which builds on problem knowledge from both techniques. We derive and compare lower bounds from different linearizations in order to assess the quality of our solutions. The involved integer linear programs are strengthened by means of problem specific valid inequalities. Computational results with practical data from the Dutch Railways indicate that our algorithm gives excellent solutions within minutes of computation time.     

A column generation heuristic for the two-dimensional two-staged guillotine cutting stock problem with multiple stock size

We consider a two-dimensional cutting stock problem where stock of different sizes is available, and a set of rectangular items has to be obtained through two-staged guillotine cuts. We propose a heuristic algorithm, based on column generation, which requires as its subproblem the solution of a two-dimensional knapsack problem with two-staged guillotines cuts. A further contribution of the paper consists in the definition of a mixed integer linear programming model for the solution of this knapsack problem, as well as a heuristic procedure based on dynamic programming. Computational experiments show the effectiveness of the proposed approach, which obtains very small optimality gaps and outperforms the heuristic algorithm proposed by Cintra et al. [3].     

Optimising a nonlinear utility function in multi-objective integer programming

In this paper we develop an algorithm to optimise a nonlinear utility function of multiple objectives over the integer efficient set. Our approach is based on identifying and updating bounds on the individual objectives as well as the optimal utility value. This is done using already known solutions, linear programming relaxations, utility function inversion, and integer programming. We develop a general optimisation algorithm for use with k objectives, and we illustrate our approach using a tri-objective integer programming problem.     

Integer programming formulations and efficient local search for relaxed correlation clustering

Relaxed correlation clustering (RCC) is a vertex partitioning problem that aims at minimizing the so-called relaxed imbalance in signed graphs. RCC is considered to be an NP-hard unsupervised learning problem with applications in biology, economy, image recognition and social network analysis. In order to solve it, we propose two linear integer programming formulations and a local search-based metaheuristic. The latter relies on auxiliary data structures to efficiently perform move evaluations during the search process. Extensive computational experiments on existing and newly proposed benchmark instances demonstrate the superior performance of the proposed approaches when compared to those available in the literature. While the exact approaches obtained optimal solutions for open problems, the proposed heuristic algorithm was capable of finding high quality solutions within a reasonable CPU time. In addition, we also report improving results for the symmetrical version of the problem. Moreover, we show the benefits of implementing the efficient move evaluation procedure that enables the proposed metaheuristic to be scalable, even for large-size 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.     

Solving large-scale maximum expected covering location problems by genetic algorithms: A comparative study

This paper compares the performance of genetic algorithms (GAs) on large-scale maximum expected coverage problems to other heuristic approaches. We focus our attention on a particular formulation with a nonlinear objective function to be optimized over a convex set. The solutions obtained by the best genetic algorithm are compared to Daskin's heuristic and the optimal or best solutions obtained by solving the corresponding integer linear programming (ILP) problems. We show that at least one of the GAs yields optimal or near-optimal solutions in a reasonable amount of time.     

A sequential integer programming method for discontinuous labor tour scheduling

General set-covering formulations (GSCFs) of labor tour scheduling problems have recently received substantial attention in the research literature. The most successful heuristic approaches to these problems have used the linear programming (LP) solution to the GSCF as a starting point and subsequently applied heuristic augmentation and improvement procedures to obtain feasible integer solutions. Integer programming (IP) methods eliminate the need for augmentation and improvement procedures, but have generally been considered intractable for large GSCFs. In this paper we present a sequential mixed-integer programming (SMIP) heuristic for discontinuous (< 24 hours/day) tour-scheduling problems which takes advantage of the structure of the GSCF. The new heuristic substantially outperformed two prominent LP-based methods across 432 full-time workforce test problems, yielding optimal solutions for 429 of the problems. For a set of 36 test problems associated with a mixed-workforce scheduling environment that allowed both full-time and part-time employees with varying levels of cost and productivity, the SMIP heuristic yielded solution costs that were significantly better than previously published costs obtained with competitive methods.     

The multiple container loading cost minimization problem

In the shipping and transportation industry, there are several types of standard containers with different dimensions and different associated costs. In this paper, we examine the multiple container loading cost minimization problem (MCLCMP), where the objective is to load products of various types into containers of various sizes so as to minimize the total cost. We transform the MCLCMP into an extended set cover problem that is formulated using linear integer programming and solve it with a heuristic to generate columns. Experiments on standard bin-packing instances show our approach is superior to prior approaches. Additionally, since the optimal solutions for existing test data is unknown, we propose a technique to generate test data with known optimal solutions for MCLCMP.