Volume 3, Number 1, Winter 2008

EN:

We consider the problem of packing rectangles with profits into a bounded square region so as to maximize their total profit. More specifically, given a set R of n rectangles with positive profits, it is required to pack a subset of them into a unit size square frame [0,1] × [0,1] so that the total profit of the rectangles packed is maximized. For any given positive accuracy [.epsilon] > 0, we present an algorithm that outputs a packing of a subset of R in the augmented square region [1 + [.epsilon]] × [1 + [.epsilon]] with profit value at least (1 − [.epsilon])OPT, where OPT is the maximum profit that can be achieved by packing a subset of R in a unit square frame. The running time of the algorithm is polynomial in n for fixed [.epsilon].

EN:

Many recent convergence results obtained for primal-dual interior-point methods for nonlinear programming, use assumptions of the boundedness of generated iterates. In this paper we replace such assumptions by new assumptions on the NLP problem, develop a modification of a primal-dual interior-point method implemented in software package LOQO and analyze convergence of the new method from any initial guess.

EN:

Let G be a graph, and let e be an edge of G. The main result of this paper is that any instance of the maximum-flow problem on G having e as the “return” edge can be solved in linear time provided G does not have a K3,3 minorcontaining e. The primary tool in proving this result is a new graph decomposition. In particular, it is shown that if G is 3-connected and does not have a K3,3 minor containing e, then it can be decomposed into planar graphs, “almost” planar graphs, and copies of K5.

EN:

In a graph G = (V, E), an identifying code of G (resp. a locating-dominating code of G) is a subset of vertices C ⊆ V such that N[v] ∩ C 6= ∅ for all v ∈ V , and N[u] ∩ C 6= N[v] ∩ C for all u 6= v, u, v ∈ V (resp. u, v ∈ V [integerdivide] C), where N[u] denotes the closed neighbourhood of v, that is N[u] = N(u) ∪ {u}. These codes model fault-detection problems in multiprocessor systems and are also used for designing location-detection schemes in wireless sensor networks. We give here simple reductions which improve results of the paper [I. Charon, O. Hudry, A. Lobstein, Minimizing the Size of an Identifying or Locating-Dominating Code in a Graph is NP-hard, Theoretical Computer Science 290(3) (2003), 2109–2120], and we show that minimizing the size of an identifying code or a locating-dominating code in a graph is APX-hard, even when restricted to graphs of bounded degree. Additionally, we give approximation algorithms for both problems with approximation ratio O(ln |V |) for general graphs and O(1) in the case where the degree of the graph is bounded by a constant.

EN:

Non-negative linear programs with box-constrained uncertainties for all input data and box-constrained variables are considered. The knowledge of upper bounds for dual variables is a useful information e.g. for presolving analysis aimed at the determination of redundant primal variables. The upper bounds of the duals are found by solving a set of special continuous knapsack problems, one for each row constraint.

EN:

Many real-life applications, arising in transportation and telecommunication systems, can be mathematically represented as shortest path problems. The deterministic version of the problem, where a deterministic cost is associated to each arc and the configuration of the network (nodes and arcs) is assumed to be known in advance, is easy to solve and has been extensively studied. However, in real applications, costs are typically not known a priori and may be subject to significant uncertainty. In addition, due to failure, maintenance, natural disasters, weather conditions, etc., some arcs could not be available causing a change of the network configuration. In this paper we introduce a variant of the shortest path problem under uncertainty, that concerns the situation in which for each arc two different states are possible (i.e. operating and failed states) and the aim is to find the path connecting a given pair of nodes with a sufficiently large probability α and such that the total cost is minimized. The problem can be formulated as a large scale integer programming model with knapsack constraints. For its solution a heuristic approach has been designed and implemented. Preliminary numerical experiments have been carried out on a set of randomly generated test problems.

EN:

Minimizing a nondecreasing separable concave cost function over a polyhedral set arises in capacity planning problems where economies of scale and fixed costs are significant, as well as production planning when a learning effect results in decreasing marginal costs. This is an NP-hard combinatorial problem in which the extreme points of the polyhedral set must be enumerated, each of them a local optimum. Branch-and-bound methods have been frequently used to solve these problems. Although it has been shown that in general the bound provided by the surrogate dual is tighter than that of the Lagrangian dual, the latter has generally been preferred because of the apparent computational intractability of the surrogate dual problem. In this paper we describe a branch-and-bound algorithm that exploits the superior surrogate dual bound in a branch-and-bound algorithm without explicitly solving the dual problem. This is accomplished by determining the feasibility of a set of linear inequalities.

EN:

Ji et al. have conjectured that using the matrix form (to represent a basic solution) instead of the Simplex tableau in the dual Simplex method will lead to an algorithm with the time complexity comparable to the Hungarian algorithm for solving the Assignment Problem. In this note we show that both the time complexity and the CPU times of the Ji et al. algorithm are far away from being competitive to the Hungarian algorithm.

EN:

In recent years, a growing range of software technologies has been deployed in the classroom, as a component of business, engineering, and science curricula. These technologies enable a more direct, interactive student involvement in educational or research project development. Within this general framework, we see a strong case for using integrated scientific-technical computing systems. To illustrate this point, we review the key features of Maple, with an emphasis on its optimization model development and solver features. Maple is then used to formulate, solve, and visualize an optimization model example suitable for the classroom.

EN:

We present a review of the book by George J. Klir, Uncertainty and Information: Foundations of Generalized Information Theory, Wiley, Hoboken, New Jersey 2006, ISBN: 0-471-74867-6, 520 pp

EN:

I review the recent book authored by Manfred Drosg, Dealing with Uncertainties, Springer, Berlin Heidelberg New York 2007, ISBN-10 3-3-540-29606-9, ISBN-13 978-3-540-29606-5, which is the English translation of the author’s German book, Der Umgang mit Unsicherheiten, Facultas Universit¨atsverlag, 2006, ISBN 3-85076-748-5