90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Refine
Document Type
- ZIB-Report (4)
Language
- English (4)
Has Fulltext
- yes (4) (remove)
Is part of the Bibliography
- no (4)
Keywords
- Network Design (4) (remove)
Institute
Rising traffic in telecommunication networks lead to rising energy costs for the network operators. Meanwhile, increased flexibility of the networking hardware may help to realize load-adaptive operation of the networks to cut operation costs. To meet network operators’ concerns over stability, we propose to switch network configurations only a limited number of times per day. We present a method for the integrated computation of optimal switching times and network configurations that alternatingly solves mixed-integer programs and constrained shortest cycle problems in a certain graph. Similarly to the Branch & Bound Algorithm, it uses lower and upper bounds on the optimum value and allows for pivoting strategies to guide the computation and avoid the solution of irrelevant subproblems. The algorithm can act as a framework to be adapted and applied to suitable problems of different origin.
One quarter of Europe’s energy demand is provided by natural gas distributed through a vast pipeline network covering the whole of Europe. At a cost of 1 million Euros per kilometer the extension of the European pipeline network is already a multi billion Euro business. Therefore, automatic planning tools that support the decision process are desired. We model the topology extension problem in gas networks by a mixed-integer nonlinear program (MINLP). This gives rise to a so-called active transmission problem, a continuous nonlinear non-convex feasibility problem which emerges from the MINLP model by fixing all integral variables. In this article we offer novel sufficient conditions for proving the infeasibility of this active transmission problem. These conditions can be expressed in the form of a mixed-integer program (MILP), i.e., the infeasibility of a non-convex NLP can be certified by solving an MILP. These results provide an efficient bounding procedure in a branch-and-bound algorithm. Our computational results demonstrate a substantial speed-up for the necessary computations.
We consider a nonlinear nonconvex network design problem that arises in the extension of natural gas transmission networks. Given is such network with active and passive components, that is, valves, compressors, pressure regulators (active) and pipelines (passive), and a desired amount of flow at certain specified entry and exit nodes of the network. Besides flow conservation constraints in the nodes the flow must fulfill nonlinear nonconvex pressure loss constraints on the arcs subject to potential values (i.e., pressure levels) in both end nodes of each arc. Assume that there does not exist a feasible flow that fulfills all physical constraints and meets the desired entry and exit amounts. Then a natural question is where to extend the network by adding pipes in the most economic way such that this flow becomes feasible. Answering this question is computationally demanding because of the difficult problem structure. We use mixed-integer nonlinear programming techniques that rely on an outer approximation of the overall problem, and a branching on decision variables. We formulate a new class of valid inequalities (or cutting planes) which reduce the overall solution time when added to the formulation. We demonstrate the computational merits of our approach on test instances.
The industrial treatment of waste paper in order to regain valuable
fibers from which recovered paper can be produced, involves several
steps of preparation. One important step is the separation of stickies
that are normally attached to the paper. If not properly separated,
remaining stickies reduce the quality of the recovered paper or even
disrupt the production process. For the mechanical separation process
of fibers from stickies a separator screen is used. This machine has
one input feed and two output streams, called the accept and the
reject. In the accept the fibers are concentrated, whereas the reject
has a higher concentration of stickies. The machine can be controlled
by setting its reject rate. But even when the reject rate is set
properly, after just a single screening step, the accept still has too
many stickies, or the reject too many fibers. To get a proper
separation, several separators have to be assembled into a
network. From a mathematical point of view this problem can be seen as
a multi-commodity network flow design problem with a nonlinear,
controllable distribution function at each node. We present a
nonlinear mixed-integer programming model for the simultaneous
selection of a subset of separators, the network's topology, and the
optimal setting of each separator.
Numerical results are obtained via
different types of linearization of the nonlinearities and the use of
mixed-integer linear solvers, and compared with state-of-the-art
global optimization software.