Adaptive linearized models for optimization of gas networks

We are interested in simulation and optimization of gas networks. Usually, a gas network consists of various components like compressors and valves connected by pipes. The aim is to run the network cost efficiently whereas demands of consumers have to be satisfied. This results in a complex nonlinear mixed integer problem. We address this task with methods provided by discrete optimization. Therefore, the gas dynamics in all pipes and at compressors must be described by piecewise linear constraints. We introduce an adaptive approach for the linearization process to handle the complexity on the one hand and the aimed accuracy on the other and present numerical simulation and optimization results based on our model. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A simulated annealing algorithm for transient optimization in gas networks

In this paper we present a simulated annealing approach for the gas network optimization problem. A gas network consists of a set of pipes to transport the gas from the sources to the sinks whereby gas pressure gets lost due to friction. Further on there are compressors, which increase gas pressure, and valves. The aim is to minimize fuel gas consumption of the compressors whereas demands of consumers have to be satisfied. The problem of transient (time-dependent) optimization of gas networks results in a highly complex mixed integer nonlinear program. We relax the equations describing the gas dynamic in pipes by adding these constraints combined with appropriate penalty factors to the objective function. A suitable neighborhood structure is developed for the relaxed problem where time steps as well as pressure and flow of the gas are decoupled. Our approach convinces with flexibility and very good computational results.     

Mixed integer linear models for the optimization of dynamical transport networks

We introduce a mixed integer linear modeling approach for the optimization of dynamic transport networks based on the piecewise linearization of nonlinear constraints and we show how to apply this method by two examples, transient gas and water supply network optimization. We state the mixed integer linear programs for both cases and provide numerical evidence for their suitability.     

Decomposition for adjustable robust linear optimization subject to uncertainty polytope

We present in this paper a general decomposition framework to solve exactly adjustable robust linear optimization problems subject to polytope uncertainty. Our approach is based on replacing the polytope by the set of its extreme points and generating the extreme points on the fly within row generation or column-and-row generation algorithms. The novelty of our approach lies in formulating the separation problem as a feasibility problem instead of a max–min problem as done in recent works. Applying the Farkas lemma, we can reformulate the separation problem as a bilinear program, which is then linearized to obtained a mixed-integer linear programming formulation. We compare the two algorithms on a robust telecommunications network design under demand uncertainty and budgeted uncertainty polytope. Our results show that the relative performance of the algorithms depend on whether the budget is integer or fractional.     

The transportation problem with exclusionary side constraints and two branch-and-bound algorithms

The transportation problem with exclusionary side constraints, a practical distribution and logistics problem, is formulated as a 0–1 mixed integer programming model. Two branch-and-bound (B&B) algorithms are developed and implemented in this study to solve this problem. Both algorithms use the Driebeek penalties to strengthen the lower bounds so as to fathom some of the subproblems, to peg variables, and to guide the selection of separation variables. One algorithm also strongly exploits the problem structure in selecting separation variables in order to find feasible solutions sooner. To take advantage of the underlying network structure of the problem, the algorithms employ the primal network simplex method to solve network relaxations of the problem. A computational experiment was conducted to test the performance of the algorithms and to characterize the problem difficulty. The commercial mixed integer programming software CPLEX and an existing special purpose algorithm specifically designed for this problem were used as benchmarks to measure the performance of the algorithms. Computational results show that the new algorithms completely dominate the existing special purpose algorithm and run from two to three orders of magnitude faster than CPLEX.     

Simple solution methods for separable mixed linear and quadratic knapsack problem

Quadratic knapsack problem has a central role in integer and nonlinear optimization, which has been intensively studied due to its immediate applications in many fields and theoretical reasons. Although quadratic knapsack problem can be solved using traditional nonlinear optimization methods, specialized algorithms are much faster and more reliable than the nonlinear programming solvers. In this paper, we study a mixed linear and quadratic knapsack with a convex separable objective function subject to a single linear constraint and box constraints. We investigate the structural properties of the studied problem, and develop a simple method for solving the continuous version of the problem based on bi-section search, and then we present heuristics for solving the integer version of the problem. Numerical experiments are conducted to show the effectiveness of the proposed solution methods by comparing our methods with some state of the art linear and quadratic convex solvers.     

On relaxations of the max k-cut problem formulations

A tight continuous relaxation is a crucial factor in solving mixed integer formulations of many NP-hard combinatorial optimization problems. The (weighted) max k-cut problem is a fundamental combinatorial optimization problem with multiple notorious mixed integer optimization formulations. In this paper, we explore four existing mixed integer optimization formulations of the max k-cut problem. Specifically, we show that the continuous relaxation of a binary quadratic optimization formulation of the problem is: (i) stronger than the continuous relaxation of two mixed integer linear optimization formulations and (ii) at least as strong as the continuous relaxation of a mixed integer semidefinite optimization formulation. We also conduct a set of experiments on multiple sets of instances of the max k-cut problem using state-of-the-art solvers that empirically confirm the theoretical results in item (i). Furthermore, these numerical results illustrate the advances in the efficiency of global non-convex quadratic optimization solvers and more general mixed integer nonlinear optimization solvers. As a result, these solvers provide a promising option to solve combinatorial optimization problems. Our codes and data are available on GitHub.     

Collision computation of moving bodies

In this paper, an explicit mathematical representation of n-dimensional bodies moving in translation along general trajectories is derived. This representation is used to find out if two moving bodies are going to collide. An optimization problem is developed for finding the time and location of collision. We consider the special cases of linear and piece-wise linear trajectories. The collision in this case can be obtained by solving a linear program or a sequence of linear programs, respectively. The problem of finding the collision time and location of several moving bodies is cast as an integer programming problem. A comprehensive simulation study shows that this approach requires much lesser computation time when compared with the current approach of finding the collision between all pairs of bodies.     

Automatic identification of embedded network rows in large-scale optimization models

The solution of a large-scale linear, integer, or mixed integer programming problem is often facilitated by the exploitation of special structure in the model. This paper presents heuristic algorithms for identifying embedded network rows within the coefficient matrix of such models. The problem of identifying a maximum-size embedded pure network is shown to be among the class of NP-hard problems. The polynomially-bounded, efficient algorithms presented here do not guarantee network sets of maximum size. However, upper bounds on the size of the maximum network set are developed and used to show that our algorithms identify embedded networks of close to maximum size. Computational tests with large-scale, real-world models are presented.     

LP-Based Heuristic Algorithms for Interconnecting Token Rings via Source Routing Bridges

We develop a method to determine the topology of a network that interconnects a number of token rings using source routing bridges. The purpose is to compute a topology that provides low response delays for network users at a minimal cost of bridge installations. We formulate this network design problem as a mixed binary integer linear program. We develop effective heuristic algorithms. The algorithms exploit the topology and routing solutions of the linear programming relaxation in a sophisticated manner which we believe is new in the literature. The model incorporates performance issues, such as network stability, bridge overflow, back pressure effect and broadcast storm, that are specific to the underlying communication technology. By formally incorporating these performance issues, we tighten the model formulation and improve the quality of the LP bound considerably. Computational results are reported for problems with up to 20 token rings and 190 potential bridge locations.     

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.     

天然气稳态运行优化的混合整数模型及其算法

天然气稳态运行优化问题的难点在于网络结构复杂、规模大、目标函数及约束高度非线性.针对其混合整数非线性规划模型,基于网络约简和线性化技术,建立了线性近似模型,并提出一种新的求解算法.将新算法用于优化我国西部天然气管网系统,结果表明所提算法是有效的.     

Cutting plane algorithms for the inverse mixed integer linear programming problem

We present cutting plane algorithms for the inverse mixed integer linear programming problem (InvMILP), which is to minimally perturb the objective function of a mixed integer linear program in order to make a given feasible solution optimal.     

Column enumeration based decomposition techniques for a class of non-convex MINLP problems

We propose a decomposition algorithm for a special class of nonconvex mixed integer nonlinear programming problems which have an assignment constraint. If the assignment decisions are decoupled from the remaining constraints of the optimization problem, we propose to use a column enumeration approach. The master problem is a partitioning problem whose objective function coefficients are computed via subproblems. These problems can be linear, mixed integer linear, (non-)convex nonlinear, or mixed integer nonlinear. However, the important property of the subproblems is that we can compute their exact global optimum quickly. The proposed technique will be illustrated solving a cutting problem with optimum nonlinear programming subproblems.     

Some models for water distribution systems

In this paper the results of our investigation of methods and algorithms for operative and dynamical control of water distribution systems are presented. Our investigation was directed to the distribution system equipped with a variety of components—pipes, consumers, valves and the inner water store (a reservoir) as the most important one. The final model of the optimization problem containing all necessary restrictions is so complex that it is impossible to solve it without some special techniques. In the presented study we propose a multilevel approach based on the idea of aggregation of the pipelines network. In the paper the method of determination of aggregated model of the network is presented. The usefulness of this method in the optimization of water supply systems is examined. Based on an aggregated network model one determines optimal strategies for control of pumping stations. The optimization model consists of a linear objective function and quadratic constraints. A nonlinear mixed integer programming problem which is solved by modified branch and bound method is obtained.     

First-order hybrid Petri nets. An application to distributed manufacturing systems

In this paper we consider Hybrid Petri Nets (HPNs), a particular formalism that combines fluid and discrete event dynamics. We first provide a survey of the main HPN models that have been presented in the literature in the last decades. Then, we focus on a particular HPN model, namely the First-Order Hybrid Petri Net (FOHPN) model, whose continuous dynamics are piece-wise constant. Here the problem of designing an optimal controller simply requires solving on-line an appropriate linear integer programming problem. In this paper we show how FOHPNs can efficiently represent the concurrent activities of Distributed Manufacturing Systems (DMS), and some interesting optimization problems are also solved via numerical simulation.     

Heuristics Based on Partial Enumeration for the Unrelated Parallel Processor Scheduling Problem

The classical deterministic scheduling problem of minimizing the makespan on unrelated parallel processors is known to be NP-hard in the strong sense. Given the mixed integer linear model with binary decision variables, this paper presents heuristic algorithms based on partial enumeration. Basically, they consist in the construction of mixed integer subproblems, considering the integrality of some subset of variables, formulated using the information obtained from the solution of the linear relaxed problem. Computational experiments are reported for a collection of test problems, showing that some of the proposed algorithms achieve better solutions than other relevant approximation algorithms published up to now.     

Design of a wind farm collection network when several cable types are available

In this article we consider a real-world problem submitted to us by the Hatch company. This problem consists of designing a collection network for a wind farm, assuming that the locations of the turbines and the potential cables are known, several cable types are available, and the cost of the energy that dissipates through the cables is known. We propose a mixed integer quadratic programme to model the network design problem and then linearize the quadratic programme because the latter is too difficult to solve using a standard mathematical programming software. We describe several classes of inequalities that strengthen the resulting mixed integer linear programme. Finally we use real-world data supplied by Hatch to carry out computational experiments with several versions of our model.     

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.     

LP extreme points and cuts for the fixed-charge network design problem

Many design decisions in transporation, communication, and manufacturing planning can be modeled as problems of routing multiple commodities between various origin and destination nodes of a directed network. Each arc of the network is uncapacitated and carries a fixed charge as well as a cost per unit of flow. We refer to the general problem of selecting a subset of arcs and routing the required multi-commodity flows along the chosen arcs at a minimum total cost as the fixed charge network design problem. This paper focuses on strenghthening the linear programming relaxation of a path-flow formulation for this problem. The considerable success achieved by researchers in solving many related design problems with algorithms that use strong linear programming-based lower bounds motivates this study. We first develop a convenient characterization of fractional extreme points for the network design linear programming relaxation. An auxiliary graph introduced for this characterization also serves to generate two families of cuts that exclude some fractional solutions without eliminating any feasible integer solutions. We discuss a separation procedure for one class of inequalities and demonstrate that many of our results generalize known properties of the plant location problem. Supported in part by grant number ECS-831-6224 of the National Science Foundation.