The viewshed problem: a theoretical analysis and a new algorithm for finding the viewshed of a given point on a triangulated terrain

We give a comprehensive theoretical treatment for calculating the viewshed of a given point, present an analytical solution to the viewshed problem and a new algorithm for finding the viewshed on a triangulated terrain. We implement our algorithm on a real terrain. Some algorithms make use of the horizon information of the terrain to calculate … Read more

Cutting Plane Algorithms for 0-1 Programming Based on Cardinality Cuts

Abstract: We present new valid inequalities for 0-1 programming problems that work in similar ways to well known cover inequalities. Discussion and analysis of these cuts is followed by their revision and use in integer programming as a new generation of cuts that excludes not only portions of polyhedra containing noninteger points, also parts with … Read more

Cardinality Cuts: New Cutting Planes for 0-1 Programming

We present new valid inequalities that work in similar ways to well known cover inequalities.The differences exist in three aspects. First difference is in the generation of the inequalities. The method used in generation of the new cuts is more practical in contrast to classical cover inequalities. Second difference is the more general applicability, i.e., … Read more

A Lagrangean Relaxation and Decomposition Algorithm for the Video Placement and Routing Problem

Video on Demand (VoD) is a technology used to provide a number of programs to a number of users on request. In developing a VoD system, a fundamental problem is load balancing, which is further characterized by optimally placing videos to a number of predefined servers and routing the user program requests to available resources. … Read more

On separating cover inequalities for the multidimensional knapsack problem

We propose a simple and sufficiently fast separation procedure to identify cover inequalities for the multidimensional knapsack problem. It is based on the solution of a conventional integer programming model. Solving this kind of integer programs are usually considered expensive and the proposed method may have been overlooked because of this assumption. The results of … Read more

Search and Cut: New Class of Cutting Planes for 0-1 Programming

The basic principle of the cutting plane techniques is to chop away the portions of the solution space of the linear programming relaxation of an integer program that contain no integer solutions. this is true for both Gomory’s cutting planes, and other more recent cuts based on valid inequalities. Obtaining a partial or full description … Read more