A new mixed integer linear programming model for the multi level uncapacitated facility location problem

This paper considers the multi level uncapacitated facility location problem (MLUFLP). A new mixed integer linear programming (MILP) formulation is presented and validity of this formulation is given. Experimental results are performed on instances known from literature. The results achieved by CPLEX and Gurobi solvers, based on the proposed MILP formulation, are compared to the results obtained by the same solvers on the already known formulations. The results show that CPLEX and Gurobi can optimally solve all small and medium sized instances and even some large-scale instances using the new formulation.     

A global MILP model for FMS scheduling

Flexible manufacturing systems (FMS) require intelligent scheduling strategies to achieve their principal benefit — combining high flexibility with high productivity. A mixed-integer linear programming model (MILP) is presented here for FMS scheduling. The model takes a global view of the problem and specifically takes into account constraints on storage and transportation. Both of these constrained resources are critical for practical FMS scheduling problems and are difficult to model. The MILP model is explained and justified and its complexity is discussed. Two heuristic procedures are developed, based on an analysis of the global MILP model. Computational results are presented comparing the performance of the different solution strategies. The development of iterative global heuristics based on mathematical programming formulations is advocated for a wide class of FMS scheduling problems.     

Kernel Search: An application to the index tracking problem

In this paper we study the problem of replicating the performances of a stock market index, i.e. the so-called index tracking problem, and the problem of out-performing a market index, i.e. the so-called enhanced index tracking problem. We introduce mixed-integer linear programming (MILP) formulations for these two problems. Furthermore, we present a heuristic framework called Kernel Search. We analyze and evaluate the behavior of several implementations of the Kernel Search framework to the solution of the index tracking problem. We show the effectiveness and efficiency of the framework comparing the performances of these heuristics with those of a general-purpose solver. The computational experiments are carried out using benchmark and newly created instances.     

Dynamic programming approximation algorithms for the capacitated lot-sizing problem

This paper provides a new idea for approximating the inventory cost function to be used in a truncated dynamic program for solving the capacitated lot-sizing problem. The proposed method combines dynamic programming with regression, data fitting, and approximation techniques to estimate the inventory cost function at each stage of the dynamic program. The effectiveness of the proposed method is analyzed on various types of the capacitated lot-sizing problem instances with different cost and capacity characteristics. Computational results show that approximation approaches could significantly decrease the computational time required by the dynamic program and the integer program for solving different types of the capacitated lot-sizing problem instances. Furthermore, in most cases, the proposed approximate dynamic programming approaches can accurately capture the optimal solution of the problem with consistent computational performance over different instances.     

A mixed integer linear programming formulation of the maximum betweenness problem

This paper considers the maximum betweenness problem. A new mixed integer linear programming (MILP) formulation is presented and validity of this formulation is given. Experimental results are performed on randomly generated instances from the literature. The results of CPLEX solver, based on the proposed MILP formulation, are compared with results obtained by total enumeration technique. The results show that CPLEX optimally solves instances of up to 30 elements and 60 triples in a short period of time.     

Piecewise polyhedral formulations for a multilinear term

In this paper, we present a mixed-integer linear programming (MILP) formulation of a piecewise, polyhedral relaxation (PPR) of a multilinear term using its convex-hull representation. Based on the PPR’s solution, we also present a MILP formulation whose solutions are feasible for nonconvex, multilinear equations. We then present computational results showing the effectiveness of proposed formulations on standard benchmark nonlinear programs (NLPs) with multilinear terms and compare with a traditional formulation that is built using recursive bilinear groupings of multilinear terms.     

Robust scheduling of parallel machines with sequence-dependent set-up costs

In this paper we propose a robust approach for solving the scheduling problem of parallel machines with sequence-dependent set-up costs. In the literature, several mathematical models and solution methods have been proposed to solve such scheduling problems, but most of which are based on the strong assumption that input data are known in a deterministic way. In this paper, a fuzzy mathematical programming model is formulated by taking into account the uncertainty in processing times to provide the optimal solution as a trade-off between total set-up cost and robustness in demand satisfaction. The proposed approach requires the solution of a non-linear mixed integer programming (NLMIP), that can be formulated as an equivalent mixed integer linear programming (MILP) model. The resulting MILP model in real applications could be intractable due to its NP-hardness. Therefore, we propose a solution method technique, based on the solution of an approximated model, whose dimension is remarkably reduced with respect to the original counterpart. Numerical experiments conducted on the basis of data taken from a real application show that the average deviation of the reduced model solution over the optimum is less than 1.5%.     

Frequency optimization in public transportation systems: Formulation and metaheuristic approach

We study the transit frequency optimization problem, which aims to determine the time interval between subsequent buses for a set of public transportation lines given by their itineraries, i.e., sequences of stops and street sections. The solution should satisfy a given origin–destination demand and a constraint on the available fleet of buses. We propose a new mixed integer linear programming (MILP) formulation for an already existing model, originally formulated as a nonlinear bilevel one. The proposed formulation is able to solve to optimality real small-sized instances of the problem using MILP techniques. For solving larger instances we propose a metaheuristic which accuracy is estimated by comparing against exact results (when possible). Both exact and approximated approaches are tested by using existing cases, including a real one related to a small-city which public transportation system comprises 13 lines. The magnitude of the improvement of that system obtained by applying the proposed methodologies, is comparable with the improvements reported in the literature, related to other real systems. Also, we investigate the applicability of the metaheuristic to a larger-sized real case, comprising more than 130 lines.     

Models and solution techniques for production planning problems with increasing byproducts

We consider a production planning problem where the production process creates a mixture of desirable products and undesirable byproducts. In this production process, at any point in time the fraction of the mixture that is an undesirable byproduct increases monotonically as a function of the cumulative mixture production up to that time. The mathematical formulation of this continuous-time problem is nonconvex. We present a discrete-time mixed-integer nonlinear programming (MINLP) formulation that exploits the increasing nature of the byproduct ratio function. We demonstrate that this new formulation is more accurate than a previously proposed MINLP formulation. We describe three different mixed-integer linear programming (MILP) approximation and relaxation models of this nonconvex MINLP, and we derive modifications that strengthen the linear programming relaxations of these models. We also introduce nonlinear programming formulations to choose piecewise-linear approximations and relaxations of multiple functions that share the same domain and use the same set of break points in the domain. We conclude with computational experiments that demonstrate that the proposed formulation is more accurate than the previous formulation, and that the strengthened MILP approximation and relaxation models can be used to obtain provably near-optimal solutions for large instances of this nonconvex MINLP. Experiments also illustrate the quality of the piecewise-linear approximations produced by our nonlinear programming formulations.     

On solving a large-scale problem on facility location and customer assignment with interaction costs along a time horizon

A 0-1 quadratic programming model is presented for solving the strategic problem of timing the location of facilities and the assignment of customers to facilities in a multi-period setting. It is assumed that all parameters are known and, on the other hand, the quadratic character of the objective function is due to considering the interaction cost incurred by the joint assignment of customers belonging to different categories to a facility at a period. The plain use of a state-of-the-art MILP engine with capabilities for dealing with quadratic terms does not give any advantage over the matheuristic algorithm proposed in this work. In fact, the MILP engine was frequently running out of memory before reaching optimality for the equivalent mixed 0-1 linear formulation, being its best lower bound at that time instant too far from the incumbent solution for the large-sized instances which we have worked with. As an alternative, a fix-and-relax algorithm is presented. A deep computational comparison between MILP alternatives is performed, such that fix-and-relax provides a solution value very close to (and, frequently, a better than) the one provided by the MILP engine. The time required by fix-and-relax is very affordable, being frequently two times smaller than the time required by the MILP engine.     

Integrated revenue management approaches for capacity control with planned upgrades

In many service industries, firms offer a portfolio of similar products based on different types of resources. Mismatches between demand and capacity can therefore often be managed by using product upgrades. Clearly, it is desirable to consider this possibility in the revenue management systems that are used to decide on the acceptance of requests. To incorporate upgrades, we build upon different dynamic programming formulations from the literature and gain several new structural insights that facilitate the control process under certain conditions. We then propose two dynamic programming decomposition approaches that extend the traditional decomposition for capacity control by simultaneously considering upgrades as well as capacity control decisions. While the first approach is specifically suited for the multi-day capacity control problem faced, for example, by hotels and car rental companies, the second one is more general and can be applied in arbitrary network revenue management settings that allow upgrading. Both approaches are formally derived and analytically related to each other. It is shown that they give tighter upper bounds on the optimal solution of the original dynamic program than the well-known deterministic linear program. Using data from a major car rental company, we perform computational experiments that show that the proposed approaches are tractable for real-world problem sizes and outperform those disaggregated, successive planning approaches that are used in revenue management practice today.     

A column generation approach to train timetabling on a corridor

We propose heuristic and exact algorithms for the (periodic and non-periodic) train timetabling problem on a corridor that are based on the solution of the LP relaxation of an ILP formulation in which each variable corresponds to a full timetable for a train. This is in contrast with previous approaches to the same problem, which were based on ILP formulations in which each variable is associated with a departure and/or arrival of a train at a specific station in a specific time instant, whose LP relaxation is too expensive to be solved exactly. Experimental results on real-world instances of the problem show that the proposed approach is capable of producing heuristic solutions of better quality than those obtained by these previous approaches, and of solving some small-size instances to proven optimality.      

Exact and heuristic algorithms for the Travelling Salesman Problem with Multiple Time Windows and Hotel Selection

We introduce and study the Travelling Salesman Problem with Multiple Time Windows and Hotel Selection (TSP-MTWHS), which generalises the well-known Travelling Salesman Problem with Time Windows and the recently introduced Travelling Salesman Problem with Hotel Selection. The TSP-MTWHS consists in determining a route for a salesman (eg, an employee of a services company) who visits various customers at different locations and different time windows. The salesman may require a several-day tour during which he may need to stay in hotels. The goal is to minimise the tour costs consisting of wage, hotel costs, travelling expenses and penalty fees for possibly omitted customers. We present a mixed integer linear programming (MILP) model for this practical problem and a heuristic combining cheapest insert, 2-OPT and randomised restarting. We show on random instances and on real world instances from industry that the MILP model can be solved to optimality in reasonable time with a standard MILP solver for several small instances. We also show that the heuristic gives the same solutions for most of the small instances, and is also fast, efficient and practical for large instances.     

Twenty years of linear programming based portfolio optimization

Markowitz formulated the portfolio optimization problem through two criteria: the expected return and the risk, as a measure of the variability of the return. The classical Markowitz model uses the variance as the risk measure and is a quadratic programming problem. Many attempts have been made to linearize the portfolio optimization problem. Several different risk measures have been proposed which are computationally attractive as (for discrete random variables) they give rise to linear programming (LP) problems. About twenty years ago, the mean absolute deviation (MAD) model drew a lot of attention resulting in much research and speeding up development of other LP models. Further, the LP models based on the conditional value at risk (CVaR) have a great impact on new developments in portfolio optimization during the first decade of the 21st century. The LP solvability may become relevant for real-life decisions when portfolios have to meet side constraints and take into account transaction costs or when large size instances have to be solved. In this paper we review the variety of LP solvable portfolio optimization models presented in the literature, the real features that have been modeled and the solution approaches to the resulting models, in most of the cases mixed integer linear programming (MILP) models. We also discuss the impact of the inclusion of the real features.     

Models and algorithms for three-stage two-dimensional bin packing

We consider the three-stage two-dimensional bin packing problem (2BP) which occurs in real-world applications such as glass, paper, or steel cutting. We present new integer linear programming formulations: models for a restricted version and the original version of the problem are developed. Both only involve polynomial numbers of variables and constraints and effectively avoid symmetries. Those models are solved using CPLEX. Furthermore, a branch-and-price (B&P) algorithm is presented for a set covering formulation of the unrestricted problem, which corresponds to a Dantzig-Wolfe decomposition of the polynomially-sized model. We consider column generation stabilization in the B&P algorithm using dual-optimal inequalities. Fast column generation is performed by applying a hierarchy of four methods: (a) a fast greedy heuristic, (b) an evolutionary algorithm, (c) solving a restricted form of the pricing problem using CPLEX, and finally (d) solving the complete pricing problem using CPLEX. Computational experiments on standard benchmark instances document the benefits of the new approaches: The restricted version of the integer linear programming model can be used to quickly obtain near-optimal solutions. The unrestricted version is computationally more expensive. Column generation provides a strong lower bound for 3-stage 2BP. The combination of all four pricing algorithms and column generation stabilization in the proposed B&P framework yields the best results in terms of the average objective value, the average run-time, and the number of instances solved to proven optimality.     

Mixed-Integer Linear Programming Formulations for the Software Clustering Problem

The clustering problem has an important application in software engineering, which usually deals with large software systems with complex structures. To facilitate the work of software maintainers, components of the system are divided into groups in such a way that the groups formed contain highly-interdependent modules and the independent modules are placed in different groups. The measure used to analyze the quality of the system partition is called Modularization Quality (MQ). Designers represent the software system as a graph where modules are represented by nodes and relationships between modules are represented by edges. This graph is referred in the literature as Module Dependency Graph (MDG). The Software Clustering Problem (SCP) consists in finding the partition of the MDG that maximizes the MQ. In this paper we present three new mathematical programming formulations for the SCP. Firstly, we formulate the SCP as a sum of linear fractional functions problem and then we apply two different linearization procedures to reformulate the problem as Mixed-Integer Linear Programming (MILP) problems. We discuss a preprocessing technique that reduces the size of the original problem and develop valid inequalities that have been shown to be very effective in tightening the formulations. We present numerical results that compare the formulations proposed and compare our results with the solutions obtained by the exhaustive algorithm supported by the freely available Bunch clustering tool, for benchmark problems.     

Modeling demand management strategies for evacuations

Evacuations are massive operations that create heavy travel demand on road networks some of which are experiencing major congestions even with regular traffic demand. Congestion in traffic networks during evacuations, can be eased either by supply or demand management actions. This study focuses on modeling demand management strategies of optimal departure time, optimal destination choice and optimal zone evacuation scheduling (also known as staggered evacuation) under a given fixed evacuation time assumption. The analytical models are developed for a system optimal dynamic traffic assignment problem, so that their characteristics can be studied to produce insights to be used for large-scale solution algorithms. While the first two strategies were represented in a linear programming (LP) model, evacuation zone scheduling problem inevitable included integers and resulted in a mixed integer LP (MILP) one. The dual of the LP produced an optimal assignment principle, and the nature of the MILP formulations revealed clues about more efficient heuristics. The discussed properties of the models are also supported via numerical results from a hypothetical network example.     

Chance constrained programming models for refinery short-term crude oil scheduling problem

The main objective of this work is to put forward chance constrained mixed-integer nonlinear stochastic and fuzzy programming models for refinery short-term crude oil scheduling problem under demands uncertainty of distillation units. The scheduling problem studied has characteristics of discrete events and continuous events coexistence, multistage, multiproduct, nonlinear, uncertainty and large scale. At first, the two models are transformed into their equivalent stochastic and fuzzy mixed-integer linear programming (MILP) models by using the method of Quesada and Grossmann [I. Quesada, I E. Grossmann, Global optimization of bilinear process networks with multicomponent flows, Comput. Chem. Eng. 19 (12) (1995) 1219–1242], respectively. After that, the stochastic equivalent model is converted into its deterministic MILP model through probabilistic theory. The fuzzy equivalent model is transformed into its crisp MILP model relies on the fuzzy theory presented by Liu and Iwamura [B.D. Liu, K. Iwamura, Chance constrained programming with fuzzy parameters, Fuzzy Sets Syst. 94 (2) (1998) 227–237] for the first time in this area. Finally, the two crisp MILP models are solved in LINGO 8.0 based on scheduling time discretization. A case study which has 267 continuous variables, 68 binary variables and 320 constraints is effectively solved with the solution approaches proposed.     

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.     

SVM classification for imbalanced data sets using a multiobjective optimization framework

Classification of imbalanced data sets in which negative instances outnumber the positive instances is a significant challenge. These data sets are commonly encountered in real-life problems. However, performance of well-known classifiers is limited in such cases. Various solution approaches have been proposed for the class imbalance problem using either data-level or algorithm-level modifications. Support Vector Machines (SVMs) that have a solid theoretical background also encounter a dramatic decrease in performance when the data distribution is imbalanced. In this study, we propose an L ₁-norm SVM approach that is based on a three objective optimization problem so as to incorporate into the formulation the error sums for the two classes independently. Motivated by the inherent multi objective nature of the SVMs, the solution approach utilizes a reduction into two criteria formulations and investigates the efficient frontier systematically. The results indicate that a comprehensive treatment of distinct positive and negative error levels may lead to performance improvements that have varying degrees of increased computational effort.