the perceptron algorithm for linear programming, arising from machine learning, has been around since the 1950s. While not a polynomial-time algorithm, it is useful in practice due to its simplicity and robustness. In...
详细信息
ISBN:
(纸本)9783319592503;9783319592497
the perceptron algorithm for linear programming, arising from machine learning, has been around since the 1950s. While not a polynomial-time algorithm, it is useful in practice due to its simplicity and robustness. In 2004, Dunagan and Vempala showed that a randomized rescaling turns the perceptron method into a polynomial time algorithm, and later Pena and Soheili gave a deterministic rescaling. In this paper, we give a deterministic rescaling for the perceptron algorithm that improves upon the previous rescaling methods by making it possible to rescale much earlier. this results in a faster running time for the rescaled perceptron algorithm. We will also demonstrate that the same rescaling methods yield a polynomial time algorithm based on the multiplicative weights update method. this draws a connection to an area that has received a lot of recent attention in theoretical computer science.
the 'exact subgraph' approach was recently introduced as a hierarchical scheme to get increasingly tight semidefinite programming relaxations of several NP-hard graph optimization problems. Solving these relax...
详细信息
ISBN:
(数字)9783030179533
ISBN:
(纸本)9783030179533;9783030179526
the 'exact subgraph' approach was recently introduced as a hierarchical scheme to get increasingly tight semidefinite programming relaxations of several NP-hard graph optimization problems. Solving these relaxations is a computational challenge because of the potentially large number of violated subgraph constraints. We introduce a computational framework for these relaxations designed to cope withthese difficulties. We suggest a partial Lagrangian dual, and exploit the fact that its evaluation decomposes into two independent subproblems. this opens the way to use the bundle method from non-smoothoptimization to minimize the dual function. Computational experiments on the Max-Cut, stable set and coloring problem show the efficiency of this approach.
the simplex algorithm is one of the most popular algorithms to solve linear programs (LPs). Starting at an extreme point solution of an LP, it performs a sequence of basis exchanges (called pivots) that allows one to ...
详细信息
ISBN:
(纸本)9783031598340;9783031598357
the simplex algorithm is one of the most popular algorithms to solve linear programs (LPs). Starting at an extreme point solution of an LP, it performs a sequence of basis exchanges (called pivots) that allows one to move to a better extreme point along an improving edge-direction of the underlying polyhedron. A key issue in the simplex algorithm's performance is degeneracy, which may lead to a (potentially long) sequence of basis exchanges which do not change the current extreme point solution. In this paper, we prove that it is always possible to limit the number of consecutive degenerate pivots that the simplex algorithm performs to n - m - 1, where n is the number of variables and m is the number of equality constraints of a given LP in standard equality form.
We study the convex hull of the feasible set of the semi-continuous knapsack problem, in which the variables belong to the union of two intervals. Besides being important in its own right, the semi-continuous knapsack...
详细信息
ISBN:
(纸本)3540221131
We study the convex hull of the feasible set of the semi-continuous knapsack problem, in which the variables belong to the union of two intervals. Besides being important in its own right, the semi-continuous knapsack problem is a relaxation of general mixed-integerprogramming. We show how strong inequalities that are valid for the semi-continuous knapsack polyhedron can be derived and used as cuts in a branch-and-cut scheme for mixed-integerprogramming anal problems with semi-continuous variables. We present computational results that demonstrate the effectiveness of these inequalities, which we call collectively semi-continuous cuts. Our computational experience also shows that dealing with semi-continuous constraints directly in the branch-and-cut algorithm through a specialized branching scheme and semi-continuous cuts is considerably more practical than the "textbook" approach of modeling semi-continuous constraints through the introduction of auxiliary binary variables in the model.
Time-cost trade-off problem (TCTP) is one of the most important aspects of construction project planning and control. Construction planners must select appropriate resources, including crew size, equipment, methods an...
详细信息
ISBN:
(纸本)7560323553
Time-cost trade-off problem (TCTP) is one of the most important aspects of construction project planning and control. Construction planners must select appropriate resources, including crew size, equipment, methods and technologies to perform tasks of a construction project. In general, there is a trade-off between time and cost to complete a task;the less expensive the resources, the long it takes. Such problems are difficult to solve because they do not have unique solutions. then it is essential for contracting organizations to carefully evaluate various approaches to attaining an optimal time-cost equilibrium. Existing methods for time-cost trade-off analysis can be categorized into three areas: mathematical programming models, heuristic methods and global search algorithms. Mathematical programming models and heuristic methods are not efficient enough for large scale networks (hundreds of activities or more). During the last decade, evolutionary methods such as genetic algorithms (GAs) and improved GAs have been used extensively for the construction time-cost trade-off analysis. More recently, ant colony optimization algorithms (ACOA), which are evolutionary methods based on the foraging behavior of ants, have been successfully applied to a number of benchmark combinatorialoptimization problems. the multiobjective model for TCTP proposed in this paper is powered by techniques using ACOA. One of the main goals of this paper is to investigate the applicability of an alternative intelligent search method in time-cost optimization. By incorporating withthe, modified adaptive weight approach (MAWA), the proposed model finds out the optimal solution and defines the Pareto front. the concept of the ACOA-based multiobjective TCTP model is implemented by a computer program, and a test example is conducted. the results indicate that the ACOA is proven to be an efficient means for searching optimal solutions in time-cost trade-off problems, and the model could assist de
Minimum cut problems are among the most classical problems in combinatorialoptimization and are used in a wide set of applications. Some of the best-known efficiently solvable variants include global minimum cuts, mi...
详细信息
ISBN:
(纸本)9783030179533;9783030179526
Minimum cut problems are among the most classical problems in combinatorialoptimization and are used in a wide set of applications. Some of the best-known efficiently solvable variants include global minimum cuts, minimum s-t cuts, and minimum odd cuts in undirected graphs. We study a problem class that can be seen to generalize the above variants, namely finding congruency-constrained minimum cuts, i.e., we consider cuts whose number of vertices is congruent to r modulo m, for some integers r and m. Apart from being a natural generalization of odd cuts, congruency-constrained minimum cuts exhibit an interesting link to a long-standing open problem in integerprogramming, namely whether integer programs described by an integer constraint matrix with bounded subdeterminants can be solved efficiently. We develop a new contraction technique inspired by Karger's celebrated contraction algorithm for minimum cuts, that, together with further insights, leads to a polynomial time randomized approximation scheme for congruency-constrained minimum cuts for any constant modulus m. Instead of contracting edges of the original graph, we use splitting-off techniques to create an auxiliary graph on a smaller vertex set, which is used for performing random edge contractions. this way, a well-structured distribution of candidate pairs of vertices to be contracted is obtained, where the involved pairs are generally not connected by an edge. As a byproduct, our technique reveals new structural insights into near-minimum odd cuts, and, more generally, near-minimum congruency-constrained cuts.
the paper studies the following question: to what extent traffic throughput of a wireless sensor network (WSN) can be increased when dynamic assignment of modulation and coding schemes (MCS) is applied. We assume a TD...
详细信息
We investigate hypergraphic LP relaxations for the Steiner tree problem, primarily the partition LP relaxation introduced by Konemann et al. [Math. programming, 2009]. Specifically, we are interested in proving upper ...
详细信息
ISBN:
(纸本)9783642130359
We investigate hypergraphic LP relaxations for the Steiner tree problem, primarily the partition LP relaxation introduced by Konemann et al. [Math. programming, 2009]. Specifically, we are interested in proving upper bounds on the integrality gap of this LP, and studying its relation to other linear relaxations. Our results are the following. Structural results: We extend the technique of uncrossing, usually applied to families of sets, to families of partitions. As a consequence we show that any basic feasible solution to the partition LP formulation has sparse support. Although the number of variables could be exponential, the number of positive variables is at most the number of terminals. Relations with other relaxations: We show the equivalence of the partition LP relaxation with other known hypergraphic relaxations. We also show that these hypergraphic relaxations are equivalent to the well studied bidirected cut relaxation, if the instance is quasibipartite. Integrality gap upper bounds: We show an upper bound of root 3 = 1.729 on the integrality gap of these hypergraph relaxations in general graphs. In the special case of uniformly qmisibipartite instances, we show an improved upper bound of 73/60 = 1.216. By our equivalence theorem, the latter result implies an improved upper bound for the bidirected cut relaxation as well.
We propose a hybrid approach for solving the resource-constrained project scheduling problem which is an extremely hard to solve combinatorialoptimization problem of practical relevance. Jobs have to be scheduled on ...
详细信息
ISBN:
(纸本)9783642135194
We propose a hybrid approach for solving the resource-constrained project scheduling problem which is an extremely hard to solve combinatorialoptimization problem of practical relevance. Jobs have to be scheduled on (renewable) resources subject to precedence constraints such that the resource capacities are never exceeded and the latest completion time of all jobs is minimized. the problem has challenged researchers from different communities, such as integerprogramming (IP), constraint programming (CP), and satisfiability testing (SAT). Still, there are instances with 60 jobs which have not been solved for many years. the currently best known approach, LAZYFD, is a hybrid between CP and SAT techniques. In this paper we propose an even stronger hybridization by integrating all the three areas, IP, CP, and SAT, into a single branch-and-bound scheme. We show that lower bounds from the linear relaxation of the IP formulation and conflict analysis are key ingredients for pruning the search tree. First computational experiments show very promising results. For five instances of the well-known PSPLIB we report an improvement of lower bounds. Our implementation is generic, thus it can be potentially applied to similar problems as well.
Scheduling problems in the forest industry have received significant attention in the recent years and have contributed many challenging applications for optimization technologies. this paper proposes a solution metho...
详细信息
ISBN:
(数字)9783540681557
ISBN:
(纸本)9783540681540
Scheduling problems in the forest industry have received significant attention in the recent years and have contributed many challenging applications for optimization technologies. this paper proposes a solution method based on constraint programming and mathematical programming for a log-truck scheduling problem. the problem consists of scheduling the transportation of logs between forest areas and wood-mills, as well as routing the fleet of vehicles to satisfy these transportation requests. the objective is to minimize the total cost of non-productive activities such as waiting time of trucks and forest log-loaders and the empty driven distance of vehicles. We propose a constraint programming model to address the combined scheduling and routing problem and an integerprogramming model to deal withthe optimization of deadheads.
暂无评论