An algorithm and upper bounds for the weighted maximal planar graph problem

In this paper, we investigate the weighted maximal planar graph (WMPG) problem. Given a complete, edge-weighted, simple graph, the WMPG problem involves finding a subgraph with the highest sum of edge weights that is maximal planar, namely, it can be embedded in the plane without any of its edges intersecting, and no additional edge can be added to the subgraph without violating its planarity. We present a new integer linear programming (ILP) model for this problem. We then develop a cutting-plane algorithm to solve the WMPG problem based on the proposed ILP model. This algorithm enables the problem to be solved more efficiently than previously reported algorithms. New upper bounds are also provided, which are useful in evaluating the quality of heuristic solutions or in generating initial solutions for meta-heuristics. Computational results are reported for a set of 417 test instances of size varying from 6 to 100 nodes including 105 instances from the literature and 312 randomly generated instances. The computational results indicate that instances with up to 24 nodes can be solved optimally in reasonable computational time and the new upper bounds for larger instances significantly improve existing upper bounds.     

A branch-and-price algorithm for the two-stage guillotine cutting stock problem

We investigate the two-stage guillotine two-dimensional cutting stock problem. This problem commonly arises in the industry when small rectangular items need to be cut out of large stock sheets. We propose an integer programming formulation that extends the well-known Gilmore and Gomory model by explicitly considering solutions that are obtained by both slitting some stock sheets down their widths and others down their heights. To solve this model, we propose an exact branch-and-price algorithm. To the best of our knowledge, this is the first contribution with regard to obtaining integer optimal solutions to Gilmore and Gomory model. Extensive results, on a set of real-world problems, indicate that the proposed algorithm delivers optimal solutions for instances with up to 809 items and that the hybrid cutting strategy often yields improved solutions. Furthermore, our computational study reveals that the proposed modelling and algorithmic strategy outperforms a recently proposed arc-flow model-based solution strategy.     

A branch-and-price algorithm to solve the integrated berth allocation and yard assignment problem in bulk ports

In this research, two crucial optimization problems of berth allocation and yard assignment in the context of bulk ports are studied. We discuss how these problems are interrelated and can be combined and solved as a single large scale optimization problem. More importantly we highlight the differences in operations between bulk ports and container terminals which highlights the need to devise specific solutions for bulk ports. The objective is to minimize the total service time of vessels berthing at the port. We propose an exact solution algorithm based on a branch and price framework to solve the integrated problem. In the proposed model, the master problem is formulated as a set-partitioning problem, and subproblems to identify columns with negative reduced costs are solved using mixed integer programming. To obtain sub-optimal solutions quickly, a metaheuristic approach based on critical-shaking neighborhood search is presented. The proposed algorithms are tested and validated through numerical experiments based on instances inspired from real bulk port data. The results indicate that the algorithms can be successfully used to solve instances containing up to 40 vessels within reasonable computational time.     

A space-indexed formulation of packing boxes into a larger box

Current integer programming solvers fail to decide whether 12 unit cubes can be packed into a 1×1×11 box within an hour using the natural relaxation of Chen/Padberg. We present an alternative relaxation of the problem of packing boxes into a larger box, which makes it possible to solve much larger instances.     

New convergent heuristics for 0–1 mixed integer programming

Several hybrid methods have recently been proposed for solving 0–1 mixed integer programming problems. Some of these methods are based on the complete exploration of small neighborhoods. In this paper, we present several convergent algorithms that solve a series of small sub-problems generated by exploiting information obtained from a series of relaxations. These algorithms generate a sequence of upper bounds and a sequence of lower bounds around the optimal value. First, the principle of a linear programming-based algorithm is summarized, and several enhancements of this algorithm are presented. Next, new hybrid heuristics that use linear programming and/or mixed integer programming relaxations are proposed. The mixed integer programming (MIP) relaxation diversifies the search process and introduces new constraints in the problem. This MIP relaxation also helps to reduce the gap between the final upper bound and lower bound. Our algorithms improved 14 best-known solutions from a set of 108 available and correlated instances of the 0–1 multidimensional Knapsack problem. Other encouraging results obtained for 0–1 MIP problems are also presented.     

Adaptively refined dynamic program for linear spline regression

The linear spline regression problem is to determine a piecewise linear function for estimating a set of given points while minimizing a given measure of misfit or error. This is a classical problem in computational statistics and operations research; dynamic programming was proposed as a solution technique more than 40 years ago by Bellman and Roth (J Am Stat Assoc 64:1079–1084, 1969). The algorithm requires a discretization of the solution space to define a grid of candidate breakpoints. This paper proposes an adaptive refinement scheme for the grid of candidate breakpoints in order to allow the dynamic programming method to scale for larger instances of the problem. We evaluate the quality of solutions found on small instances compared with optimal solutions determined by a novel integer programming formulation of the problem. We also consider a generalization of the linear spline regression problem to fit multiple curves that share breakpoint horizontal coordinates, and we extend our method to solve the generalized problem. Computational experiments verify that our nonuniform grid construction schemes are useful for computing high-quality solutions for both the single-curve and two-curve linear spline regression problem.     

A decomposition approach for the integrated vehicle-crew-roster problem with days-off pattern

The integrated vehicle-crew-roster problem with days-off pattern aims to simultaneously determine minimum cost vehicle and daily crew schedules that cover all timetabled trips and a minimum cost roster covering all daily crew duties according to a pre-defined days-off pattern. This problem is formulated as a new integer linear programming model and is solved by a heuristic approach based on Benders decomposition that iterates between the solution of an integrated vehicle-crew scheduling problem and the solution of a rostering problem. Computational experience with data from two bus companies in Portugal and data from benchmark vehicle scheduling instances shows the ability of the approach for producing a variety of solutions within reasonable computing times as well as the advantages of integrating the three problems.     

Exact Algorithm for the Surrogate Dual of an Integer Programming Problem: Subgradient Method Approach

One of the critical issues in the effective use of surrogate relaxation for an integer programming problem is how to solve the surrogate dual within a reasonable amount of computational time. In this paper, we present an exact and efficient algorithm for solving the surrogate dual of an integer programming problem. Our algorithm follows the approach which Sarin et al. (Ref. 8) introduced in their surrogate dual multiplier search algorithms. The algorithms of Sarin et al. adopt an ad-hoc stopping rule in solving subproblems and cannot guarantee the optimality of the solutions obtained. Our work shows that this heuristic nature can actually be eliminated. Convergence proof for our algorithm is provided. Computational results show the practical applicability of our algorithm.     

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.

     

The bilevel knapsack problem with stochastic right-hand sides

We introduce the bilevel knapsack problem with stochastic right-hand sides, and provide necessary and sufficient conditions for the existence of an optimal solution. When the leader’s decisions can take only integer values, we present an equivalent two-stage stochastic programming reformulation with binary recourse. We develop a branch-and-cut algorithm for solving this reformulation, and a branch-and-backtrack algorithm for solving the scenario subproblems. Computational experiments indicate that our approach can solve large instances in a reasonable amount of time.     

A Lagrangian heuristic algorithm for a public healthcare facility location problem

We consider a healthcare facility location problem in which there are two types of patients, low-income patients and middle- and high-income patients. The former can use only public facilities, while the latter can use both public facilities and private facilities. We focus on the problem of determining locations of public healthcare facilities to be established within a given budget and allocating the patients to the facilities for the objective of maximizing the number of served patients while considering preference of the patients for the public and private facilities. We present an integer programming formulation for the problem and develop a heuristic algorithm based on Lagrangian relaxation and subgradient optimization methods. Results of computational experiments on a number of problem instances show that the algorithm gives good solutions in a reasonable computation time and may be effectively used by the healthcare authorities of the government.     

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.     

Two-stage quadratic integer programs with stochastic right-hand sides

We consider two-stage quadratic integer programs with stochastic right-hand sides, and present an equivalent reformulation using value functions. We propose a two-phase solution approach. The first phase constructs value functions of quadratic integer programs in both stages. The second phase solves the reformulation using a global branch-and-bound algorithm or a level-set approach. We derive some basic properties of value functions of quadratic integer programs and utilize them in our algorithms. We show that our approach can solve instances whose extensive forms are hundreds of orders of magnitude larger than the largest quadratic integer programming instances solved in the literature.     

Computational experience with an interior point algorithm on the satisfiability problem

We apply the zero-one integer programming algorithm described in Karmarkar [12] and Karmarkar, Resende and Ramakrishnan [13] to solve randomly generated instances of the satisfiability problem (SAT). The interior point algorithm is briefly reviewed and shown to be easily adapted to solve large instances of SAT. Hundreds of instances of SAT (having from 100 to 1000 variables and 100 to 32,000 clauses) are randomly generated and solved. For comparison, we attempt to solve the problems via linear programming relaxation with MINOS.     

Using a Hybrid Genetic-Algorithm/Branch and Bound Approach to Solve Feasibility and Optimization Integer Programming Problems

The satisfiability problem in forms such as maximum satisfiability (MAX-SAT) remains a hard problem. The most successful approaches for solving such problems use a form of systematic tree search. This paper describes the use of a hybrid algorithm, combining genetic algorithms and integer programming branch and bound approaches, to solve MAX-SAT problems. Such problems are formulated as integer programs and solved by a hybrid algorithm implemented within standard mathematical programming software. Computational testing of the algorithm, which mixes heuristic and exact approaches, is described.     

An linear programming based lower bound for the simple assembly line balancing problem

The simple assembly line balancing problem is a classical integer programming problem in operations research. A set of tasks, each one being an indivisible amount of work requiring a number of time units, must be assigned to workstations without exceeding the cycle time. We present a new lower bound, namely the LP relaxation of an integer programming formulation based on Dantzig–Wolfe decomposition. We propose a column generation algorithm to solve the formulation. Therefore, we develop a branch-and-bound algorithm to exactly solve the pricing problem. We assess the quality of the lower bound by comparing it with other lower bounds and the best-known solution of the various instances from the literature. Computational results show that the lower bound is equal to the best-known objective function value for the majority of the instances. Moreover, the new LP based lower bound is able to prove optimality for an open problem.     

A branch and bound algorithm for the maximum diversity problem

This article begins with a review of previously proposed integer formulations for the maximum diversity problem (MDP). This problem consists of selecting a subset of elements from a larger set in such a way that the sum of the distances between the chosen elements is maximized. We propose a branch and bound algorithm and develop several upper bounds on the objective function values of partial solutions to the MDP. Empirical results with a collection of previously reported instances indicate that the proposed algorithm is able to solve all the medium-sized instances (with 50 elements) as well as some large-sized instances (with 100 elements). We compare our method with the best previous linear integer formulation solved with the well-known software Cplex. The comparison favors the proposed procedure.     

The balanced minimum evolution problem under uncertain data

We investigate the Robust Deviation Balanced Minimum Evolution Problem (RDBMEP), a combinatorial optimization problem that arises in computational biology when the evolutionary distances from taxa are uncertain and varying inside intervals. By exploiting some fundamental properties of the objective function, we present a mixed integer programming model to exactly solve instances of the RDBMEP and discuss the biological impact of uncertainty on the solutions to the problem. Our results give perspective on the mathematics of the RDBMEP and suggest new directions to tackle phylogeny estimation problems affected by uncertainty.     

A simplex social spider algorithm for solving integer programming and minimax problems

In this paper, we propose a new hybrid social spider algorithm with simplex Nelder-Mead method in order to solve integer programming and minimax problems. We call the proposed algorithm a Simplex Social Spider optimization (SSSO) algorithm. In the the proposed SSSO algorithm, we combine the social spider algorithm with its powerful capability of performing exploration, exploitation, and the Nelder-Mead method in order to refine the best obtained solution from the standard social spider algorithm. In order to investigate the general performance of the proposed SSSO algorithm, we test it on 7 integer programming problems and 10 minimax problems and compare against 10 algorithms for solving integer programming problems and 9 algorithms for solving minimax problems. The experiments results show the efficiency of the proposed algorithm and its ability to solve integer and minimax optimization problems in reasonable time.     

A hybrid imperialist competitive algorithm for minimizing makespan in a multi-processor open shop

In this paper a new mixed-integer linear programming (MILP) model is proposed for the multi-processor open shop scheduling (MPOS) problems to minimize the makespan with considering independent setup time and sequence dependent removal time. A hybrid imperialist competitive algorithm (ICA) with genetic algorithm (GA) is presented to solve this problem. The parameters of the proposed algorithm are tuned by response surface methodology (RSM). The performance of the algorithm to solve small, medium and large sized instances of the problem is evaluated by introducing two performance metrics. The quality of obtained solutions is compared with that of the optimal solutions for small sized instances and with the lower bounds for medium sized instances. Also some computational results are presented for large sized instances.