Strong valid inequalities for Boolean logical pattern generation

0–1 multilinear programming (MP) captures the essence of pattern generation in logical analysis of data (LAD). This paper utilizes graph theoretic analysis of data to discover useful neighborhood properties among data for data reduction and multi-term linearization of the common constraint of an MP pattern generation model in a small number of stronger valid inequalities. This means that, with a systematic way to more efficiently generating Boolean logical patterns, LAD can be used for more effective analysis of data in practice. Mathematical properties and the utility of the new valid inequalities are illustrated on small examples and demonstrated through extensive experiments on 12 real-life data mining datasets.     

Robust planning of blending activities at refineries

Refinery operation planning is a complex task since refinery processes and inventories are tightly interconnected. We study refinery planning when ships are loaded with a blend of components and where arrival times of ships are uncertain. Any delay in ship arrival may result in overfull component tanks which results in less efficient blending alternatives, reduced process operations or even shut downs. We propose a planning approach where we use robust optimization as a decision tool. By using robust optimization uncertainty in arrival times is explicitly dealt with and the resulting plan and schedule will always be feasible. The approach includes a flexible way to describe and model uncertainties. To compare the robust approach with a traditional deterministic approach, we use a simulation process. Computational results from a case study and simulations show that the proposed methodology is substantially better than a deterministic approach.     

A column generation algorithm for tactical timber transportation planning

We present a tactical wood flow model that appears in the context of the Canadian forestry industry, and describe the implementation of a decision support system created for use by an industrial partner. In this problem, mill demands and harvested volumes of a heterogeneous set of log types are given over a multi-period planning horizon. Wood can be stored at the forest roadside before delivery at a financial cost. Rather than solve this as a network linear programme on the basis of out-and-back deliveries, we choose to model this problem as a generalization of a log-truck scheduling problem. By routing and scheduling the trucks in the resolution, this allows us to both anticipate potential backhaul opportunities for cost and fuel savings, and also minimize queuing times at log-loaders, management of which is a major concern in the industry. We model this problem as a mixed integer linear programme and solve it via column generation. The methodology is tested on several case studies.     

Preference scheduling for nurses using column generation

The purpose of this paper is to present a new methodology for scheduling nurses in which several conflicting factors guide the decision process. Unlike manufacturing facilities where standard shifts and days off are the rule, hospitals operate 24 hours a day, 7 days a week and face widely fluctuating demand. A more flexible arrangement for working hours and days off is needed, especially in light of the growing nursing shortage. To improve retention, management must now take into account individual preferences and requests for days off in a way that is perceived as fair, while ensuring sufficient coverage at all times. This multi-objective problem is solved with a column generation approach that combines integer programming and heuristics. The integer program is formulated as a set covering-type problem whose columns correspond to alternative schedules that a nurse can work over the planning horizon. A double swapping heuristic is used to generate the columns. The objective coefficients are determined by the degree to which the individual preferences of a nurse are violated. As part of the computational scheme, feasible solutions are refined to minimize the use of outside nurses, but when gaps in coverage exist, the outside nurses are distributed as evenly as possible over the shifts. The methodology was tested on a series of problems with up to 100 nurses using data provided by a large hospital in the US. The results indicate that high-quality solutions can be obtained within a few minutes in the majority of cases.     

Supermodularity and valid inequalities for quadratic optimization with indicators

Mathematical Programming - We study the minimization of a rank-one quadratic with indicators and show that the underlying set function obtained by projecting out the continuous variables is...     

New valid inequalities for the fixed-charge and single-node flow polytopes

The most effective software packages for solving mixed 0–1linear programs use strong valid linear inequalities derived from polyhedral theory. We introduce a new procedure which enables one to take known valid inequalities for the knapsack polytope, and convert them into valid inequalities for the fixed-charge and single-node flow polytopes. The resulting inequalities are very different from the previously known inequalities (such as flow cover and flow pack inequalities), and define facets under certain conditions.     

New formulations and valid inequalities for a bilevel pricing problem

Consider the problem of maximizing the toll revenue collected on a multi-commodity transportation network. This fits a bilevel framework where a leader sets tolls, while users respond by selecting cheapest paths to their destination. We propose novel formulations of the problem, together with valid inequalities yielding improved algorithms.     

Strong valid inequalities for orthogonal disjunctions and bilinear covering sets

In this paper, we derive a closed-form characterization of the convex hull of a generic nonlinear set, when this convex hull is completely determined by orthogonal restrictions of the original set. Although the tools used in this construction include disjunctive programming and convex extensions, our characterization does not introduce additional variables. We develop and apply a toolbox of results to check the technical assumptions under which this convexification tool can be employed. We demonstrate its applicability in integer programming by providing an alternate derivation of the split cut for mixed-integer polyhedral sets and finding the convex hull of certain mixed/pure-integer bilinear sets. We then extend the utility of the convexification tool to relaxing nonconvex inequalities, which are not naturally disjunctive, by providing sufficient conditions for establishing the convex extension property over the non-negative orthant. We illustrate the utility of this result by deriving the convex hull of a continuous bilinear covering set over the non-negative orthant. Although we illustrate our results primarily on bilinear covering sets, they also apply to more general polynomial covering sets for which they yield new tight relaxations.     

Facets and valid inequalities for the time-dependent travelling salesman problem

The Time-Dependent Travelling Salesman Problem (TDTSP) is a generalization of the traditional TSP where the travel cost between two cities depends on the moment of the day the arc is travelled. In this paper, we focus on the case where the travel time between two cities depends not only on the distance between them, but also on the position of the arc in the tour. We consider two formulations proposed in the literature, we analyze the relationship between them and derive several families of valid inequalities and facets. In addition to their theoretical properties, they prove to be very effective in the context of a Branch and Cut algorithm.     

Optimizing glass coating lines: MIP model and valid inequalities

Glass coating is a specific transformation aiming at improving glass performance. The work presented in this paper deals with the determination of the optimal configuration of the production lines used to perform this operation. We propose a first MIP formulation of the problem and then discuss several types of valid inequalities for improving it. The main idea is to exploit explicit or implicit binary exclusion constraints to derive stronger valid inequalities: the maximal clique constraints. Efficient (polynomial time) separation algorithms exploiting special structure of the problem are described, giving rise to a cutting-plane generation procedure for strengthening the initial formulation. The computational study carried out shows that, with the enhanced formulation, good solutions can be obtained within reasonable computation times using currently available integer programming software.     

A column generation approach for the route planning problem in fourth party logistics

In this paper, we address the route planning problem in fourth party logistics (4PL). The problem calls for the selection of the logistics companies by a 4PL provider to optimize the routes of delivering goods through a transportation network. The concept of 4PL emerged in response to the shortfall in services capabilities of traditional third party logistics and has been proven to be capable of integrating logistics resources in order to fulfill complex transportation demands. A mixed-integer programming model is established for the planning problem with setup cost and edge cost discount policies which are commonly seen in practice. We propose a column generation approach combined with graph search heuristic to efficiently solve the problem. The good performance in terms of the solution quality and computational efficiency of our approach is shown through extensive numerical experiments on various scales of test instances. Impacts of cost policies on routing decision are also investigated and managerial insights are drawn.     

Formulations and valid inequalities for the node capacitated graph partitioning problem

We investigate the problem of partitioning the nodes of a graph under capacity restriction on the sum of the node weights in each subset of the partition. The objective is to minimize the sum of the costs of the edges between the subsets of the partition. This problem has a variety of applications, for instance in the design of electronic circuits and devices. We present alternative integer programming formulations for this problem and discuss the links between these formulations. Having chosen to work in the space of edges of the multicut, we investigate the convex hull of incidence vectors of feasible multicuts. In particular, several classes of inequalities are introduced, and their strength and robustness are analyzed as various problem parameters change.     

Strong formulations for mixed integer programs: valid inequalities and extended formulations

 We examine progress over the last fifteen years in finding strong valid inequalities and tight extended formulations for simple mixed integer sets lying both on the ``easy' and ``hard' sides of the complexity frontier. Most progress has been made in studying sets arising from knapsack and single node flow sets, and a variety of sets motivated by different lot-sizing models. We conclude by citing briefly some of the more intriguing new avenues of research. Received: January 15, 2003 / Accepted: April 10, 2003 Published online: May 28, 2003 Key words. mixed integer programming – strong valid inequalities – convex hull – extended formulations – single node flow sets – lot-sizing This paper presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian State, Prime Minister's Office, Science Policy Programming. The scientific responsibility is assumed by the authors. Research carried out with financial support of the project TMR-DONET nr. ERB FMRX–CT98–0202 of the European Union.     

Comparison of bundle and classical column generation

When a column generation approach is applied to decomposable mixed integer programming problems, it is standard to formulate and solve the master problem as a linear program. Seen in the dual space, this results in the algorithm known in the nonlinear programming community as the cutting-plane algorithm of Kelley and Cheney-Goldstein. However, more stable methods with better theoretical convergence rates are known and have been used as alternatives to this standard. One of them is the bundle method; our aim is to illustrate its differences with Kelley’s method. In the process we review alternative stabilization techniques used in column generation, comparing them from both primal and dual points of view. Numerical comparisons are presented for five applications: cutting stock (which includes bin packing), vertex coloring, capacitated vehicle routing, multi-item lot sizing, and traveling salesman. We also give a sketchy comparison with the volume algorithm. This research has been supported by Inria New Investigation Grant “Convex Optimization and Dantzig-Wolfe Decomposition”.     

The symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities

The graphical relaxation of the Traveling Salesman Problem is the relaxation obtained by requiring that the salesman visit each city at least once instead of exactly once. This relaxation has already led to a better understanding of the Traveling Salesman polytope in Cornuéjols, Fonlupt and Naddef (1985). We show here how one can compose facet-inducing inequalities for the graphical traveling salesman polyhedron, and obtain other facet-inducing inequalities. This leads to new valid inequalities for the Symmetric Traveling Salesman polytope. This paper is the first of a series of three papers on the Symmetric Traveling Salesman polytope, the next one studies the strong relationship between that polytope and its graphical relaxation, and the last one applies all the theoretical developments of the two first papers to prove some new facet-inducing results.This work was initiated while the authors were visiting the Department of Statistics and Operations Research of New York University, and continued during several visits of the first author at IASI.     

Branch-and-price for staff rostering: An efficient implementation using generic programming and nested column generation

We present a novel generic programming implementation of a column-generation algorithm for the generalized staff rostering problem. The problem is represented as a generalized set partitioning model, which is able to capture commonly occurring problem characteristics given in the literature. Columns of the set partitioning problem are generated dynamically by solving a pricing subproblem, and constraint branching in a branch-and-bound framework is used to enforce integrality. The pricing problem is formulated as a novel three-stage nested shortest path problem with resource constraints that exploits the inherent problem structure. A very efficient implementation of this pricing problem is achieved by using generic programming principles in which careful use of the C++ pre-processor allows the generator to be customized for the target problem at compile-time. As well as decreasing run times, this new approach creates a more flexible modeling framework that is well suited to handling the variety of problems found in staff rostering. Comparison with a more-standard run-time customization approach shows that speedups of around a factor of 20 are achieved using our new approach. The adaption to a new problem is simple and the implementation is automatically adjusted internally according to the new definition. We present results for three practical rostering problems. The approach captures all features of each problem and is able to provide high-quality solutions in less than 15 minutes. In two of the three instances, the optimal solution is found within this time frame.     

A coupled column generation,mixed integer approach to optimal planning of intensity modulated radiation therapy for cancer

Approximately 40% of all U.S. cancer cases are treated with radiation therapy. In Intensity-Modulated Radiation Therapy (IMRT) the treatment planning problem is to choose external beam angles and their corresponding intensity maps (showing how the intensity varies across a given beam) to maximize tumor dose subject to the tolerances of surrounding healthy tissues. Dose, like temperature, is a quantity defined at each point in the body, and the distribution of dose is determined by the choice of treatment parameters available to the planner. In addition to absolute dose limits in healthy tissues, some tissues have at least one dose-volume restriction that requires a fraction of its volume to not exceed a specified tighter threshold level for damage. There may also be a homogeneity limit for the tumor that restricts the allowed spread of dose across its volume. We formulate this planning problem as a mixed integer program over a coupled pair of column generation processes -- one designed to produce intensity maps, and a second specifying protected area choices for tissues under dose-volume restrictions. The combined procedure is shown to strike a balance between computing an approximately optimal solution and bounding its maximum possible suboptimality that we believe holds promise for implementations able to offer the power and flexibility of mixed-integer linear programming models on instances of practical scale.A portion of the work of Dr. Langer, Mr. Thai and Dr. Preciado-Walters was supported by National Science Foundation grant ECS-0120145 and National Cancer Institute 1R41CA91688-01. Dr. Rardin is participated while on rotation as Program Director for Operations Research and Service Enterprise Engineering at the National Science Foundation.     

A heuristic for the long-term electricity generation planning problem using the Bloom and Gallant formulation

Long-term power planning is a stochastic problem often confronted by electrical utilities in liberalized markets. One can model it for profit maximization—using market-price estimation functions for each interval—by posing it as a quadratic programming problem with some linear equalities and an exponential number of load-matching linear inequality constraints.     

Linear formulations and valid inequalities for a classic location problem with congestion: a robust optimization application

This study investigates a classic stochastic location problem in a service system with immobile servers that are represented by M/G/1 queues. It shows that