Multiple depot ring star problem: a polyhedral study and an exact algorithm

The multiple depot ring-star problem (MDRSP) is an important combinatorial optimization problem that arises in optical fiber network design and in applications that collect data using stationary sensing devices and autonomous vehicles. Given the locations of a set of customers and a set of depots, the goal is to (i) find a set of simple cycles such that each cycle (ring) passes through a subset of customers and exactly one depot, (ii) assign each non-visited customer to a visited customer or a depot, and (iii) minimize the sum of the routing costs, i.e., the cost of the cycles and the assignment costs. We present a mixed integer linear programming formulation for the MDRSP and propose valid inequalities to strengthen the linear programming relaxation. Furthermore, we present a polyhedral analysis and derive facet-inducing results for the MDRSP. All these results are then used to develop a branch-and-cut algorithm to obtain optimal solutions to the MDRSP. The performance of the branch-and-cut algorithm is evaluated through extensive computational experiments on several classes of test instances.     

Mathematical programming via the least-squares method

The least-squares method is used to obtain a stable algorithm for a system of linear inequalities as well as linear and nonlinear programming. For these problems the solution with minimal norm for a system of linear inequalities is found by solving the non-negative least-squares (NNLS) problem. Approximate and exact solutions of these problems are discussed. Attention is mainly paid to finding the initial solution to an LP problem. For this purpose an NNLS problem is formulated, enabling finding the initial solution to the primal or dual problem, which may turn out to be optimal. The presented methods are primarily suitable for ill-conditioned and degenerate problems, as well as for LP problems for which the initial solution is not known. The algorithms are illustrated using some test problems.     

Improved integer programming bounds using intersections of corner polyhedra

Consider the relaxation of an integer programming (IP) problem in which the feasible region is replaced by the intersection of the linear programming (LP) feasible region and the corner polyhedron for a particular LP basis. Recently a primal-dual ascent algorithm has been given for solving this relaxation. Given an optimal solution of this relaxation, we state criteria for selecting a new LP basis for which the associated relaxation is stronger. These criteria may be successively applied to obtain either an optimal IP solution or a lower bound on the cost of such a solution. Conditions are given for equality of the convex hull of feasible IP solutions and the intersection of all corner polyhedra.     

Multi-depot Multiple TSP: a polyhedral study and computational results

We study the Multi-Depot Multiple Traveling Salesman Problem (MDMTSP), which is a variant of the very well-known Traveling Salesman Problem (TSP). In the MDMTSP an unlimited number of salesmen have to visit a set of customers using routes that can be based on a subset of available depots. The MDMTSP is an NP-hard problem because it includes the TSP as a particular case when the distances satisfy the triangular inequality. The problem has some real applications and is closely related to other important multi-depot routing problems, like the Multi-Depot Vehicle Routing Problem and the Location Routing Problem. We present an integer linear formulation for the MDMTSP and strengthen it with the introduction of several families of valid inequalities. Certain facet-inducing inequalities for the TSP polyhedron can be used to derive facet-inducing inequalities for the MDMTSP. Furthermore, several inequalities that are specific to the MDMTSP are also studied and proved to be facet-inducing. The partial knowledge of the polyhedron has been used to implement a Branch-and-Cut algorithm in which the new inequalities have been shown to be very effective. Computational results show that instances involving up to 255 customers and 25 possible depots can be solved optimally using the proposed methodology.     

The branch and cut method for the facility location problem with client’s preferences

Numerical study is provided of the methods for solving the facility location problem when the clients choose some suppliers by their own preferences. Various formulations of this problem as an integer linear programming problem are considered. The authors implement a cutting plane method based on the earlier proposed family of valid inequalities which arises from connection with the problem for a pair of matrices. The results of numerical experiment are presented for testing this method. An optimal solution is obtained by the two versions of the branch and cut method with the suggested cutting plane method. The simulated annealing method is proposed for obtaining the upper bounds of the optimal solution used in exact methods. Numerical experiment approves the efficiency of the implemented approach in comparison with the previously available methods.     

Studying the stability of solutions to systems of linear inequalities and constructing separating hyperplanes

We consider the methods for matrix correction or correction of all parameters of systems of linear equations and inequalities. We show that the problem of matrix correction of an inconsistent system of linear inequalities with the nonnegativity condition is reduced to a linear programming problem. Some stability measure is defined for a given solution to a system of linear inequalities as the minimal possible variation of parameters under which this solution does not satisfy the system. The problem of finding the most stable solution to the system is considered. The results are applied to constructing an optimal separating hyperplane in the feature space that is the most stable to the changes of features of the objects.     

A further study on inverse linear programming problems

In this paper we continue our previous study (Zhang and Liu, J. Comput. Appl. Math. 72 (1996) 261–273) on inverse linear programming problems which requires us to adjust the cost coefficients of a given LP problem as less as possible so that a known feasible solution becomes the optimal one. In particular, we consider the cases in which the given feasible solution and one optimal solution of the LP problem are 0–1 vectors which often occur in network programming and combinatorial optimization, and give very simple methods for solving this type of inverse LP problems. Besides, instead of the commonly used l₁ measure, we also consider the inverse LP problems under l_∞ measure and propose solution methods.     

An Exact Solution to Linear Programming Using an Interior Point Method

This paper presents sufficient conditions for optimality of the Linear programming (LP) problem in the neighborhood of an optimal solution, and applies them to an interior point method for solving the LP problem. We show that after a finite number of iterations, an exact solution to the LP problem is obtained by solving a linear system of equations under the assumptions that the primal and dual problems are both nondegenerate, and that the minimum value is bounded. If necessary, the dual solution can also be found.     

Shipment planning at oil refineries using column generation and valid inequalities

In this paper we suggest an optimization model and a solution method for a shipment planning problem. This problem concerns the simultaneous planning of how to route a fleet of ships and the planning of which products to transport in these ships. The ships are used for moving products from oil refineries to storage depots. There are inventory levels to consider both at the refineries and at the depots. The inventory levels are affected by the process scheduling at the refineries and demand at the depots. The problem is formulated using an optimization model including an aggregated representation of the process scheduling at the refineries. Hence, we integrate the shipment planning and the process scheduling at the refineries. We suggest a solution method based on column generation, valid inequalities, and constraint branching. The solution method is tested on data provided by the Nynas oil refinery company and solutions are obtained within 4 hours, for problem instances of up to 3 refineries, 15 depots, and 4 products when considering a time horizon of 42 days.     

A Dual Simplex Implementation of a Constraint Selection Algorithm for Linear Programming

The constraint selection approach to linear programming begins by solving a relaxed version of the problem using only a few of the original constraints. If the solution obtained to this relaxation satisfies the remaining constraints it is optimal for the original LP. Otherwise, additional constraints must be incorporated in a larger relaxation. The procedure successively generates larger subproblems until an optimal solution is obtained which satisfies all of the original constraints. Computational results for a dual simplex implementation of this technique indicate that solving several small subproblems in this manner is more computationally efficient than solving the original LP using the revised simplex method.     

Integer linear programming models for a cement delivery problem

We consider a cement delivery problem with an heterogeneous fleet of vehicles and several depots. The demands of the customers are typically larger than the capacity of the vehicles which means that most customers are visited several times. This is a split delivery vehicle routing problem with additional constraints. We first propose a two phase solution method that assigns deliveries to the vehicles, and then builds vehicle routes. Both subproblems are formulated as integer linear programming problems. We then show how to combine the two phases in a single integer linear program. Experiments on real life instances are performed to compare the performance of the two solution methods.     

A revisit of numerical approach for solving linear fractional programming problem in a fuzzy environment

In the article, Veeramani and Sumathi [10] presented an interesting algorithm to solve a fully fuzzy linear fractional programming (FFLFP) problem with all parameters as well as decision variables as triangular fuzzy numbers. They transformed the FFLFP problem under consideration into a bi-objective linear programming (LP) problem, which is then converted into two crisp LP problems. In this paper, we show that they have used an inappropriate property for obtaining non-negative fuzzy optimal solution of the same problem which may lead to the erroneous results. Using a numerical example, we show that the optimal fuzzy solution derived from the existing model may not be non-negative. To overcome this shortcoming, a new constraint is added to the existing fuzzy model that ensures the fuzzy optimal solution of the same problem is a non-negative fuzzy number. Finally, the modified solution approach is extended for solving FFLFP problems with trapezoidal fuzzy parameters and illustrated with the help of a numerical example.     

A new approach for solving fully intuitionistic fuzzy transportation problems

In this paper, a well-known network-structured problem called the transportation problem (TP) is considered in an uncertain environment. The transportation costs, supply and demand are represented by trapezoidal intuitionistic fuzzy numbers (TrIFNs) which are the more generalized form of trapezoidal fuzzy numbers involving a degree of acceptance and a degree of rejection. We formulate the intuitionistic fuzzy TP (IFTP) and propose a solution approach to solve the problem. The IFTP is converted into a deterministic linear programming (LP) problem, which is solved using standard LP algorithms. The main contributions of this paper are fivefold: (1) we convert the formulated IFTP into a deterministic classical LP problem based on ordering of TrIFNs using accuracy function; (2) in contrast to most existing approaches, which provide a crisp solution, we propose a new approach that provides an intuitionistic fuzzy optimal solution; (3) in contrast to existing methods that include negative parts in the obtained intuitionistic fuzzy optimal solution and intuitionistic fuzzy optimal cost, we propose a new method that provides non-negative intuitionistic fuzzy optimal solution and optimal cost; (4) we discuss about the advantages of the proposed method over the existing methods for solving IFTPs; (5) we demonstrate the feasibility and richness of the obtained solutions in the context of two application examples.     

A Note on Redundancy and Linear Parametric Programming

A simple redundancy criterion for a system of linear inequalities is given. Considering a linear programming problem with linear inequality constraints the sensitivity analysis of the optimal solution of the right-hand side in combination with the redundancy criterion can help to identify redundant inequalities (constraints). The redundancy criterion is applied to a linear parametric problem which is enlarged by an auxiliary condition such as "stop the parametric procedure when a chosen constraint becomes redundant".     

Lower bounds for the two-stage uncapacitated facility location problem

In the two-stage uncapacitated facility location problem, a set of customers is served from a set of depots which receives the product from a set of plants. If a plant or depot serves a product, a fixed cost must be paid, and there are different transportation costs between plants and depots, and depots and customers. The objective is to locate plants and depots, given both sets of potential locations, such that each customer is served and the total cost is as minimal as possible. In this paper, we present a mixed integer formulation based on twice-indexed transportation variables, and perform an analysis of several Lagrangian relaxations which are obtained from it, trying to determine good lower bounds on its optimal value. Computational results are also presented which support the theoretical potential of one of the relaxations.     

Creating Advanced Bases For Large Scale Linear Programs Exploiting Embedded Network Structure

In this paper, we investigate how an embedded pure network structure arising in many linear programming (LP) problems can be exploited to create improved sparse simplex solution algorithms. The original coefficient matrix is partitioned into network and non-network parts. For this partitioning, a decomposition technique can be applied. The embedded network flow problem can be solved to optimality using a fast network flow algorithm. We investigate two alternative decompositions namely, Lagrangean and Benders. In the Lagrangean approach, the optimal solution of a network flow problem and in Benders the combined solution of the master and the subproblem are used to compute good (near optimal and near feasible) solutions for a given LP problem. In both cases, we terminate the decomposition algorithms after a preset number of passes and active variables identified by this procedure are then used to create an advanced basis for the original LP problem. We present comparisons with unit basis and a well established crash procedure. We find that the computational results of applying these techniques to a selection of Netlib models are promising enough to encourage further research in this area.     

The discrete facility location problem with balanced allocation of customers

We consider a discrete facility location problem where the difference between the maximum and minimum number of customers allocated to every plant has to be balanced. Two different Integer Programming formulations are built, and several families of valid inequalities for these formulations are developed. Preprocessing techniques which allow to reduce the size of the largest formulation, based on the upper bound obtained by means of an ad hoc heuristic solution, are also incorporated. Since the number of available valid inequalities for this formulation is exponential, a branch-and-cut algorithm is designed where the most violated inequalities are separated at every node of the branching tree. Both formulations, with and without the improvements, are tested in a computational framework in order to discriminate the most promising solution methods. Difficult instances with up to 50 potential plants and 100 customers, and largest easy instances, can be solved in one CPU hour.     

Lagrangian heuristics for the two-echelon,single-source,capacitated facility location problem

Facility location problems form an important class of integer programming problems, with application in the distribution and transportation industries. In this paper we are concerned with a particular type of facility location problem in which there exist two echelons of facilities. Each facility in the second echelon has limited capacity and can be supplied by only one facility (or depot) in the first echelon. Each customer is serviced by only one facility in the second echelon. The number and location of facilities in both echelons together with the allocation of customers to the second-echelon facilities are to be determined simultaneously. We propose a mathematical model for this problem and consider six heuristics based on Lagrangian relaxation for its solution. To solve the dual problem we make use of a subgradient optimization procedure. We present numerical results for a large suite of test problems. These indicate that the lower-bounds obtained from some relaxations have a duality gap which frequently is one third of the one obtained from traditional linear programming relaxation. Furthermore, the overall solution time for the heuristics are less than the time to solve the LP relaxation.     

Bilevel programming and the separation problem

In recent years, branch-and-cut algorithms have become firmly established as the most effective method for solving generic mixed integer linear programs (MILPs). Methods for automatically generating inequalities valid for the convex hull of solutions to such MILPs are a critical element of branch-and-cut. This paper examines the nature of the so-called separation problem, which is that of generating a valid inequality violated by a given real vector, usually arising as the solution to a relaxation of the original problem. We show that the problem of generating a maximally violated valid inequality often has a natural interpretation as a bilevel program. In some cases, this bilevel program can be easily reformulated as a simple single-level mathematical program, yielding a standard mathematical programming formulation for the separation problem. In other cases, no such polynomial-size single-level reformulation exists unless the polynomial hierarchy collapses to its first level (an event considered extremely unlikely in computational complexity theory). We illustrate our insights by considering the separation problem for two well-known classes of valid inequalities.