90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Refine
Year of publication
- 2013 (24) (remove)
Document Type
- ZIB-Report (23)
- Master's Thesis (1)
Language
- English (24)
Has Fulltext
- yes (24)
Is part of the Bibliography
- no (24)
Keywords
- Mixed-Integer Nonlinear Programming (4)
- Relaxations (2)
- System Dynamics; Mixed-Integer Nonlinear Optimization (2)
- branch-and-bound (2)
- Bounds Strengthening (1)
- Combinatorial Optimization, Robust Optimization, Multiband Robustness, Network Design (1)
- Connected Facility Location, Branch-and-Cut, FTTx Deployment (1)
- Cutting Planes (1)
- Data Uncertainty (1)
- Duality (1)
Institute
We propose a novel optimization model for resource assignment in heterogeneous wireless network. The model adopts two objective functions maximizing the number of served users and the minimum granted utility at once. A distinctive feature of our new model is to consider two consecutive time slots, in order to include handover as an additional decision dimension.
Furthermore, the solution algorithm that we propose refines a heuristic solution approach recently proposed in literature, by considering a real joint optimization of the considered resources. The simulation study shows that the new model leads to a significant reduction in handover frequency, when compared to a traditional scheme based on maximum SNR.
Recently, parallel computing environments have become significantly popular. In order to obtain the benefit of using parallel computing environments, we have to deploy our programs for these effectively. This paper focuses on a parallelization of SCIP (Solving Constraint Integer Programs), which is a MIP solver and constraint integer programming framework available in source code. There is a parallel extension of SCIP named ParaSCIP, which parallelizes SCIP on massively parallel distributed memory computing environments. This paper describes FiberSCIP, which is yet another parallel extension of SCIP to utilize multi-threaded parallel computation on shared memory computing environments, and has the following contributions: First, the basic concept of having two parallel extensions and the relationship between them and the parallelization framework provided by UG (Ubiquity Generator) is presented, including an implementation of deterministic parallelization. Second, the difficulties to achieve a good performance that utilizes all resources on an actual computing environment and the difficulties of performance evaluation of the parallel solvers are discussed. Third, a way to evaluate the performance of new algorithms and parameter settings of the parallel extensions is presented. Finally, current performance of FiberSCIP for solving mixed-integer linear programs (MIPs) and mixed-integer non-linear programs (MINLPs) in parallel is demonstrated.
Sports rankings are obtained by applying a system of rules to evaluate the
performance of the participants in a competition.
We consider rankings that result from assigning an ordinal rank to each
competitor according to their performance.
We develop an integer programming model for rankings that allows us
to calculate the number of points needed to guarantee
a team the ith position, as well as the minimum number of points
that could yield the ith place.
The model is very general and can thus be applied to many types of sports.
We discuss examples coming from football (soccer), ice hockey, and
Formula~1. We answer various questions and debunk a few myths along the way.
Are 40 points enough to avoid relegation in the Bundesliga?
Do 95 points guarantee the participation of a team in the NHL playoffs?
Moreover, in the season restructuration currently under consideration in the NHL,
will it be easier or harder to access the playoffs?
Is it possible to win the Formula~1 World Championship without winning at least one race
or without even climbing once on the podium?
Finally, we observe that the optimal solutions of the aforementioned model
are associated to extreme situations which are unlikely to happen. Thus,
to get closer to realistic scenarios, we enhance the model by adding some
constraints inferred from the results of the previous years.
We introduce a new variant of the connected facility location problem that allows for modeling mixed deployment strategies (FTTC/FTTB/FTTH) in the design of local access telecommunication networks. Several mixed integer programming models and valid inequalities are presented. Computational studies on realistic instances from three towns in Germany are provided.
We present a novel heuristic algorithm to identify feasible solutions of a mixed-integer nonlinear programming problem arising in natural gas transportation: the selection of new pipelines to enhance the network's capacity to a desired level in a cost-efficient way. We solve this problem in a linear programming based branch-and-cut approach, where we deal with the nonlinearities by linear outer approximation and spatial branching. At certain nodes of the branching tree, we compute a KKT point for a nonlinear relaxation. Based on the information from the KKT point we alter some of the integer variables in a locally promising way. We describe this heuristic for general MINLPs and then show how to tailor the heuristic to exploit our problem-specific structure. On a test set of real-world instances, we are able to increase the chance of identifying feasible solutions by some order of magnitude compared to standard MINLP heuristics that are already built in the general-purpose MINLP solver SCIP.
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.
We consider reoptimization (i.e. the solution of a problem based on information available from solving a similar problem) for branch-and-bound algorithms and propose a generic framework to construct a reoptimizing branch-and-bound algorithm.
We apply this to an elevator scheduling algorithm solving similar subproblems to generate columns using branch-and-bound. Our results indicate that reoptimization techniques can substantially reduce the running times of the overall algorithm.
Two fundamental mathematical formulations for railway timetabling are compared on a common set of sample problems, representing both multiple track high density services in Europe and single track bidirectional operations in North America. One formulation, ACP, enforces against conflicts by constraining time intervals between trains, while the other formulation, HGF, monitors physical occupation of controlled track segments. The results demonstrate that both ACP and HGF return comparable solutions in the aggregate, with some significant differences in select instances, and a pattern of significant differences in performance and constraint enforcement overall.
In this paper we study the cost-optimal deployment of optical access networks considering variants of the problem such as fiber to the home (FTTH), fiber to the building (FTTB), fiber to the curb (FTTC), or fiber to the neighborhood (FTTN). We identify the combinatorial structures of the most important sub-problems arising in this area and model these, e.g., as capacitated facility location, concentrator location, or Steiner tree problems. We discuss modeling alternatives as well. We finally construct a “unified” integer programming model that combines all sub-models and provides a global view of all these FTTx problems. We also summarize computational studies of various special cases.
The System Dynamics (SD) methodology is a framework for modeling and simulating
the dynamic behavior of socioeconomic systems. Characteristic for the
description of such systems is the occurrence of feedback loops together with
stocks and flows. The mathematical equations that describe the system are
usually nonlinear. Therefore seemingly simple systems can show a nonintuitive,
nonpredictable behavior over time. Controlling a dynamical system means to
define a desired final state in which the system should be, and to specify
potential interventions from outside that should keep the system on the right
track. The central question is how to compute such globally optimal control for
a given SD model. We propose a branch-and-bound approach that is based on a
bound propagation method, primal heuristics, and spatial branching. We apply our
new SD-control method to a small System Dynamics model, that describes the
evolution of a social-economic system over time. We examine the problem of
steering this system on a sustainable consumption path.