Optimization-based mapping framework for parallel applications
16
Citation
60
Reference
10
Related Paper
Citation Trend
Keywords:
Solver
Matrix (chemical analysis)
Context. In this paper, we consider a well-known university scheduling problem. Such tasks are solved several times a year in every educational institution. The problem of constructing an optimal schedule remains open despite numerous studies in this area. This is due to the complexity of the corresponding optimization problem, in particular, its significant dimension. This complicates its numerical solution with existing optimization methods. Scheduling models also need improvement. Thus, schedule optimization is a complex computational problem and requires the development of new methods for solving it.
Objective. Improvement of optimization models for timetabling at the university and the use of new effective methods to solve them.
Method. We use the exact quadratic regularization method to solve timetabling optimization problems. Exact quadratic regularization allows transforming complex optimization models with Boolean variables into the problem of maximizing the vector norm on a convex set. We use the efficient direct dual interior point method and dichotomy method to solve this problem. This method has shown significantly better results in solving many complex multimodal problems. This is confirmed by many comparative computational experiments. The exact quadratic regularization method is even more effective in solving timetabling problems. This optimization method is used for the first time for this class of problems, so it required the development of adequate algorithmic support.
Results. We propose a new, simpler timetabling optimization model that can be easily implemented software in Excel with the OpenSolver, RoskSolver, and others. We give a small example of building a schedule and describe step-by-step instructions for obtaining the optimal solution.
Conclusions. An efficient new technology developed for university timetable, which is simple to implement and does not require the development of special software. The efficiency of the technology is ensured by the use of a new method of exact quadratic regularization.
L-reduction
Interior point method
Cite
Citations (0)
ABSTRACT The Multiple Knapsack problem (MKP) is a hard combinatorial optimization problem with large application, which embraces many practical problems from different domains, like cargo loading, cutting stock, bin-packing, financial and other management, etc. It also arise as a subproblem in several more complex problems like vehicle routing problem and the algorithms to solve these problems will benefit from any improvement in the field of MKP. The aim of this paper is to compare different kind of heuristic models, statics and dynamics. The heuristics are used by an Ant Colony Optimization (ACO) algorithm to construct solutions to the MKP. KEYWORDS combinatorial optimization, multiple knapsack problem, heuristics 1. INTRODUCTION Combinatorial optimization is the process of finding the best, or optimal solution for problems with a discrete set of feasible solutions. Applications arise in numerous settings involving operations management and logistics. The economic impact of combinatorial optimization is profound, affecting diverse sectors. While much progress has been made in finding exact solutions to some Combinatorial Optimization Problems (COPs), many hard combinatorial problems are still not solved exactly in a reasonable time and require good heuristic methods. The aim of heuristic methods for COPs is to quickly produce good-quality solutions. Modern heuristics include simulated annealing [7], genetic algorithms [4], tabu search [5], ant colony optimization [2,3]. In many practical problems they have proved to be effective and efficient approaches, being flexible to accommodate variations in problem structure and in the objectives considered for the evaluation of solutions. For all these reasons, metaheuristics have probably been one of the most stimulating research topics in optimization for the last two decades. The ACO algorithm were inspired by the observation of real ant colonies. Ants are social insects, that is , insects that live in colonies and whose behavior is directed more to the survival of the colony as a whole than to that of a single individual component of the colony. An important and interesting aspect of ant colonies is how ants can find the shortest path between food sources and their nest. ACO is the recently developed, population-based approach which has been successfully applied to several NP-hard COPs. One of its main ideas is the indirect communication among the individuals of a colony of agents, called ``artificial'' ants, based on an analogy with trails of a chemical substance, called pheromone which real ants use for communication. ACO uses a colony of artificial ants that behaves as cooperative agents in a mathematical space where they are allowed to search and reinforce pathways (solutions) in order to find the optimal ones. Unlike the real-life case, these pathways might contain very complex information. When constructing an initial solution, at each step ants compute a set of feasible moves and select the best one according to some probabilistic rules. These rules are based on the heuristic information and pheromone trail level. The higher value of the pheromone and the heuristic information, the more profitable is to select this move and resume the search. In this paper ACO algorithm for MKP is investigated. The MKP is an important real-life problem. Problems from different industrial fields, can be interpreted like knapsack problem. When the ACO algorithm is applied MKP gives a possibility to use varied heuristic informations. We have concentrated on
Heuristics
Bin packing problem
Vehicle Routing Problem
Cite
Citations (10)
Network experiments of many types, especially emulation, require the ability to map virtual resources requested by an experimenter onto available physical resources. These resources include hosts, routers, switches, and the links that connect them. Experimenter requests, such as nodes with special hardware or software, must be satisfied, and bottleneck links and other scarce resources in the physical topology should be conserved when physical resources are shared. In the face of these constraints, this mapping becomes an NP-hard problem. Yet, in order to prevent mapping time from becoming a serious hindrance to experimentation, this process cannot consume an excessive amount of time.In this paper, we explore this problem, which we call the network testbed mapping problem .We describe the interesting challenges that characterize it, and explore its applications to emulation and other spaces, such as distributed simulation. We present the design, implementation, and evaluation of a solver for this problem, which is in production use on the Netbed shared network testbed. Our solver builds on simulated annealing to find very good solutions in a few seconds for our historical workload, and scales gracefully on large well-connected synthetic topologies.
Testbed
Solver
Cite
Citations (230)
Despite significant advances on distributed continuous-time optimization of multi-agent networks, there is still lack of an efficient algorithm to achieve the goal of distributed optimization at a pre-specified time. Herein, we design a specified-time distributed optimization algorithm for connected agents with directed topologies to collectively minimize the sum of individual objective functions subject to an equality constraint. With the designed algorithm, the settling time of distributed optimization can be exactly predefined. The specified selection of such a settling time is independent of not only the initial conditions of agents, but also the algorithm parameters and the communication topologies. Furthermore, the proposed algorithm can realize specified-time optimization by exchanging information among neighbours only at discrete sampling instants and thus reduces the communication burden. In addition, the equality constraint is always satisfied during the whole process, which makes the proposed algorithm applicable to online solving distributed optimization problems such as economic dispatch. For the special case of undirected communication topologies, a reduced-order algorithm is also designed. Finally, the effectiveness of the theoretical analysis is justified by numerical simulations.
Cite
Citations (0)
Solver
Smoothing
Theory of computation
Cite
Citations (1)
The particular structure of the assignment problem made of it a very popular subject of study and an important research tool in operations research and management science.In addition to the importance that the assignment problem represents in its own, it can appear as a relaxation of more complex combinatorial optimization problems.That is why the assignment problem has received great attention from the operations research community.The assignment problem may appear as an optimization problem with multiple objectives.In this paper, we address the problem of efficiency of feasible solutions of a multicriteria assignment problem.It is done in two steps.In the first step, we determine whether or not a given feasible solution of a multicriteria assignment problem is efficient.In a second step, if the feasible solution is not efficient, we provide an efficient solution that dominates it.The proposed method consists of transforming the original problem into an assignment problem with side constraints for which solution techniques already exist.
Cite
Citations (7)
Abstract Decision making problems in areas such as R&D project selection, facility layout design, capital budgeting, resource allocation, communication network design, and scheduling are more than often formulated as assignment problems with quadratic objective functions in 0-1 variables. Although quadratic assignment problems are formulated as mathematical optimization problems, the solution algorithms that have been suggested in the literature are usually heuristic. The scarcity of exact solution techniques is attributed to the presence of large numbers of 0-1 variables as well as to the optimization of a nonlinear objective function expressed in 0-1 variables. This paper suggests a reformulation method that linearizes the quadratic objective functions in assignment problems and reduces the number of 0-1 variables one has to deal with in the optimization process. The new reformulation leads to use of commercially available codes to solve the resulting mixed-integer linear programming problem. Computational experience with this new reformulation is also discussed.
Cite
Citations (21)
Robust optimization (RO) has become a central framework to handle the uncertainty that arises in the parameters of optimization
problems. While classical RO results can efficiently handle linear programs for a large variety of uncertainty sets, the situation is more
complex for optimization problems involving discrete decisions. Efficient exact or approximate solution algorithms for such problems
must exploit the combinatorial structure of the problems at hand.
This thesis uses the budgeted uncertainty set, introduced by Bertsimas and Sim in (2003,2004), to address scheduling problems, vehicle routing
problems, constrained shortest path problems, and lot-sizing problems. We address the resulting robust combinatorial optimization problems along two complementary set of tools: exact and approximate combinatorial algorithms, and decomposition algorithms based on integer
programming formulations. In addition to the results specific to each problem, we present an extension of the budgeted uncertainty that is
motivated by a connection with probabilistic constraints.
Robust Optimization
Benders' decomposition
Cite
Citations (0)
optimization problems currently occupy an important place in the scientific community. Intuitively, an optimization problem can be seen as a search problem that consists in exploring a space containing the set of all feasible solutions, in order to find the optimal solution. The traveling salesman problem (TSP), considered as a classical example of combinatorial optimization problem, is considered as an NP-complete problem. In this work we will divide the solution of combinatorial optimization problems into three classes: continuous Hopfield network (CHN), ant colony optimization (ACO) and exact methods programmed in Cplex. The solution of a CHN optimization problem is based on a certain energy or Lyapunov function, which decreases as the system evolves until it reaches a local minimum value. Ant colony optimization to solve the traveling salesman problem (TSP) is inspired by the foraging behavior of ants. As a special case, and in order to test these methods, some computational experiments solving the TSP are also included.
Extremal optimization
Parallel metaheuristic
Cite
Citations (11)