Discrete Optimization

El problema de coloreo de grafos es un desafío fundamental en la optimización combinatoria, con aplicaciones en ingeniería civil, industrial y en sistemas, particularmente en la planificación de horarios, asignación de recursos y diseño de redes. En este trabajo se comparan enfoques de búsqueda exhaustiva con algoritmos heurísticos y metaheurísticos para la resolución del problema, evaluando su rendimiento en términos de precisión y eficiencia computacional. Se presentan fundamentos teóricos del coloreo, junto con implementaciones de algoritmos clásicos y contemporáneos. Además, se desarrolla un análisis experimental que evidencia las ventajas y limitaciones de cada estrategia, destacando la aplicabilidad práctica de las heurísticas en instancias de gran escala. Los resultados permiten establecer un marco comparativo robusto y abren la discusión sobre futuras líneas de investigación en optimización combinatoria aplicada.

Many discrete optimization problems can be formulated as either integer linear programming problems or constraint satisfaction problems. Although ILP methods appear to be more powerful, sometimes constraint programming can solve these problems more quickly. This paper describes a problem in which the di erence in performance between the two approaches was particularly marked, since a solution could not be found using ILP. The problem arose in the context of organising a progressive party" at a y achting rally. Some yachts were to be designated hosts; the crews of the remaining yachts would then visit the hosts for six successive half-hour periods. A guest crew could not revisit the same host, and two guest crews could not meet more than once. Additional constraints were imposed by the capacities of the host yachts and the crew sizes of the guests. Integer linear programming formulations which included all the constraints resulted in very large models, and despite trying several di erent strategies, all attempts to nd a solution failed. Constraint programming was tried instead and solved the problem very quickly, with a little manual assistance. Reasons for the success of constraint programming in this problem are identi ed and discussed.

• We study the spread of influenza virus infections on networks of people. • We develop a novel integer programming formulation to minimize the influenza spread. • We develop several enhancement techniques to improve the proposed formulation.

Let A be an m × n integral matrix of rank n. We say that A is bimodular if the maximum of the absolute values of the n × n minors is at most 2. We give a polynomial time algorithm that finds an integer solution for system Ax ≤ b. A polynomial time algorithm for integer program max{cx : Ax ≤ b} is constructed, proceeding on some assumptions.

We consider regret minimization in adversarial deterministic Markov Decision Processes (ADMDPs) with bandit feedback. We devise a new algorithm that pushes the state-of-theart forward in two ways: First, it attains a regret of O(T 2/3 ) with respect to the best fixed policy in hindsight, whereas the previous best regret bound was O(T 3/4 ). Second, the algorithm and its analysis are compatible with any feasible ADMDP graph topology, while all previous approaches required additional restrictions on the graph topology.

We consider regret minimization in adversarial deterministic Markov Decision Processes (ADMDPs) with bandit feedback. We devise a new algorithm that pushes the state-of-theart forward in two ways: First, it attains a regret of O(T 2/3 ) with respect to the best fixed policy in hindsight, whereas the previous best regret bound was O(T 3/4 ). Second, the algorithm and its analysis are compatible with any feasible ADMDP graph topology, while all previous approaches required additional restrictions on the graph topology.

Discrete optimization problems are interesting due to their complexity and applications, particularly in robotics. In this paper, a parallel algorithm that allows finding solutions to these problems, is presented. Then, the modifications that can be applied to it to obtain a second parallel algorithm that finds suboptimal solutions, reducing computation time, are studied. The algorithms proposed are based on two variations of the heuristic search algorithm Best First Search, and are called A* and Weighted A*, respectively. The parallel solutions were implemented using MPI to be run on cluster, taking the N 2 -1 Puzzle as study case. The experimental work focuses on analyzing the speedup and efficiency achieved for various initial instances, varying architecture configuration. Finally, the quality of the solutions found by the optimal and suboptimal algorithms are compared and performance variation is analyzed.

This paper is motivated by the fact that mixed integer nonlinear programming is an important and difficult area for which there is a need for developing new methods and software for solving large-scale problems. Moreover, both fundamental building blocks, namely mixed integer linear programming and nonlinear programming, have seen considerable and steady progress in recent years. Wishing to exploit expertise in these areas as well as on previous work in mixed integer nonlinear programming, this work represents the first step in an ongoing and ambitious project within an open-source environment. COIN-OR is our chosen environment for the development of the optimization software. A class of hybrid algorithms, of which branch and bound and polyhedral outer approximation are the two extreme cases, is proposed and implemented. Computational results that demonstrate the effectiveness of this framework are reported, and a library of mixed integer nonlinear problems that exhibit convex continuous relaxations is made publicly available.

A cactus graph is a connected graph in which every block is either an edge or a cycle. In this paper, we consider several problems of graph theory and developed optimal algorithms to solve such problems on cactus graphs. The running time of these algorithms is O(n), where n is the total number of vertices of the graph. The cactus graph has many applications in real life problems, especially in radio communication system.

A cactus graph is a connected graph in which every block is either an edge or a cycle. In this paper we give a brief idea how t design some optimal algorithms on cactus graphs in O(n) time, where n is the total number of vertices of the graph. The cactus graph has many applications in real life pro blems, specially in radio communication system.

A cactus graph is a connected graph in which every block is either an edge or a cycle. In this paper, we consider several problems of graph theory and developed optimal algorithms to solve such problems on cactus graphs. The running time of these algorithms is O(n), where n is the total number of vertices of the graph. The cactus graph has many applications in real life problems, especially in radio communication system.

In our recent research, we implemented an enhancement of Ant Colony Optimization incorporating the socio-cognitive dimension of perspective taking. Our initial results suggested that increasing the diversity of ant population -introducing different pheromones, different species and dedicated inter-species relations -yielded better results. In this paper, we explore the diversity issue by introducing novel diversity measurement strategies for ACO. Based on these strategies we compare both classic ACO and its socio-cognitive variation.

“Theory of Conservation of Optima and Complexity” by Oscar Riveros just dropped — and it’s one of the cleanest, most rigorous pieces I’ve seen in years on the geometric approach to combinatorial optimization and P vs NP.
In 21 pages it does something genuinely new: it isolates five precise layers that any geometric representation must satisfy to legitimately claim it turns an NP-complete problem into a polynomial-time solvable one:

explicit binary encoding
exact representation (with linear cost lifting)
correct optimal support
strong exactness (polynomial extractor from continuous optimum to combinatorial solution)
uniform polynomial fidelity + controlled representational growth

It proves the key theorems (exact conservation of arg min, linear criterion for cost lifting, affine equivalence transport, and a fully typed complexity transfer theorem) and then delivers the first honest sufficient scheme for turning “my new polytope solves STSP ⇒ P = NP” into an actual theorem instead of hand-wavy intuition.
No hype. Just a crystal-clear formal contract that every future extended-formulation or pedigree-polytope paper will now have to meet.
If you work on polyhedral combinatorics, TSP, or the geometric side of complexity, this is required reading. It doesn’t solve P vs NP — but it finally tells us exactly what would constitute a valid solution.

A very common question appearing in resource management is: what is the optimal way of behaviour of the agents and distribution of limited resources. This paper addresses the following question: Is there at least one form of cooperation that satisfies interests of all players better than competition? This research is based on results proving the existence of a non-empty K-core, that is, the set of allocations acceptable for the family K of all feasible coalitions, for the case when this family is a set of subtrees of a tree. A wide range of real situations in resource management, which include optimal water, gas and electricity allocation problems, can be modeled using this class of games, whose K-core is non-empty due to the acyclic structure of the associated networks. Thus, the present research is pursuing two goals: 1. optimality and 2. stability. Firstly, we suggest to players to unify their resources and then we optimize the total payoff using some standard LP technique. The same unification and optimization can be done for any coalition of players, not only for the total one. However, players may object unification of resources. It may happen when a feasible coalition can guarantee a better result for every coalitionist. Here we obtain some stability conditions which ensure that this cannot happen for some family K. Such families were characterized by Boros, Gurvich and Vasin [4] as Berge's normal hypergraphs. Thus, we obtain a solution which is optimal and stable. From practical point of view, we suggest a distribution of profit that would cause no conflict between players.

In this work we propose a new distributed evolutionary algorithm that uses a proactive strategy to adapt its migration policy and the mutation rate. The proactive decision is carried out locally in each subpopulation based on the entropy of that subpopulation. In that way, each subpopulation can change their own incoming flow of individuals by asking their neighbors for more frequent or less frequent migrations in order to maintain the genetic diversity at a desired level. Moreover, this proactive strategy is reinforced by adapting the mutation rate while the algorithm is searching for the problem solution. All these strategies avoid the subpopulations to get trapped into local minima. We conduct computational experiments on large instances of the NK landscape problem which have shown that our proactive approach outperforms traditional dEAs, particularly for not highly rugged landscapes, in which it does not only reaches the most accurate solutions, but it does the fastest.Fil: Salt...

Parallel genetic algorithms (PGAs) have been traditionally used to overcome the intense use of CPU and memory that serial GAs show in complex problems. Non-parallel GAs can be classified into two classes: panmictic and structured-population algorithms. The difference lies in whether any individual in the population can mate with any other one or not. In this work, they are both considered as two reproductive loop types executed in the islands of a parallel distributed GA. Our aim is to extend the existing studies from more conventional sequential islands to other kinds of evolution. A key issue in such a coarse grain PGA is the migration policy, since it governs the exchange of individuals among the islands. This paper investigates the influence of migration frequency and migrant selection in a ring of islands running either steady-state, generational, or cellular GAs. A diversity analysis is also offered from an entropy point of view. The study uses different problem types, namely easy, deceptive, multimodal, NP-Complete, and epistatic search landscapes in order to provide a wide spectrum of problem difficulties to support the results. Large isolation values and random selection of the migrants are demonstrated as providing a larger probability of success and a smaller number of visited points. Also, interesting observations on the relative performance of the different models are offered, as well as we point out the considerable benefits that can accrue from asynchronous migration.

Ant Colony Optimization (ACO) has been successfully applied to those combinatorial optimization problems which can be translated into a graph exploration. Artificial ants build solutions step by step adding solution components that are represented by graph nodes. The existing ACO algorithms are suitable when the graph is not very large (thousands of nodes) but is not useful when the graph size can be a challenge for the computer memory and cannot be completely generated or stored in it. In this paper we study a new ACO model that overcomes the difficulties found when working with a huge construction graph. In addition to the description of the model, we analyze in the experimental section one technique used for dealing with this huge graph exploration. The results of the analysis can help to understand the meaning of the new parameters introduced and to decide which parameterization is more suitable for a given problem. For the experiments we use one real problem with capital importance in Software Engineering: refutation of safety properties in concurrent systems. This way, we foster an innovative research line related to the application of ACO to formal methods in Software Engineering.

Simulation models and discrete optimization models are oftentimes used together in a variety of ways. In this paper, we discuss the issues that modelers must address in cases where simulation models are used to test a discrete mathematical programming optimization model's performance in a stochastic environment. The issues arise during validation of simulation models, when checking agreement between deterministic optimization results and simulation models operating under deterministic conditions. In our case, the issues are derived from validating simulation models that are used to test the performance of scheduling and resource allocation models (integer and mixed-integer programming optimization models) under various types of uncertainty. While the concerns we describe are from our work in the logistics domain (cross-docking operations), they are relevant to a wide variety of problem domains. In addition to describing the issues, we offer suggestions on how modelers might address the concerns.

Simulation models and discrete optimization models are oftentimes used together in a variety of ways. In this paper, we discuss the issues that modelers must address in cases where simulation models are used to test a discrete mathematical programming optimization model's performance in a stochastic environment. The issues arise during validation of simulation models, when checking agreement between deterministic optimization results and simulation models operating under deterministic conditions. In our case, the issues are derived from validating simulation models that are used to test the performance of scheduling and resource allocation models (integer and mixed-integer programming optimization models) under various types of uncertainty. While the concerns we describe are from our work in the logistics domain (cross-docking operations), they are relevant to a wide variety of problem domains. In addition to describing the issues, we offer suggestions on how modelers might address the concerns.

We consider approximate strong equilibria (SE) in strategic job scheduling games with two uniformly related machines. Jobs are assigned to machines, and each job wishes to minimize its cost, given by the completion time of the machine it is assigned to. Finding a Nash equilibrium (NE) in this game is simple. However, NE-configurations are not stable against coordinated deviations of several jobs. Various measures can be used to evaluate how well an NE-configuration approximates SE. A schedule is said to be an α-SE if there is no coalitional deviation such that every member of the coalition reduces its cost by a factor greater than α. We show that any pure NE on two related machines of speed ratio s is a s 2 +s-1 4 -SE, and provide a matching lower bound. In addition, we show that the LPT (Longest Processing Time) algorithm provides a better approximation ratio than a general NE, in particular, any LPT schedule is a 1.1011-SE. This is in contrast to the LS (List Scheduling) greedy algorithm for which the improvement ratio of coalitional deviations can be arbitrarily large. In addition, we design a fully polynomial time approximation scheme (FPTAS), which computes an NE that is a We also provide bounds for two other measures of approximate SE, considering the supremum possible improvement of a deviating job and the maximal increase in the cost of non-coalition members, and show that checking whether a specific schedule is an SE is co-NP-complete, which motivates the study of approximate strong equilibria. Finally, we consider multiple machines. We show that any pure NE on m related machines is a 2-SE. We give improved results for identical machines, and in particular, we show that any pure NE is a 1.32-SE.

The paper discusses several extensions of the recursive representation of the flow shop scheduling problem. It is shown that recursive functions make it possible to describe multiple extensions in a single problem. The paper considers altogether six extensions. The examples consider three types of recursive functions: functions associated with the machine, functions that adjust the procession time based on constraints, and functions that control the feasibility of the schedule. The structure of the superpositions of these functions is presented, and also descriptions of several objective functions by recursive functions are presented. Then the general requirements for a recursive function are formulated and its properties are described. Finally, a demonstration of the formulation of new problems is provided using examples of simple flow shop extensions and branch and bound optimization.

Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g. , payment of royalties). Copies may be requested from IBM T.

In this paper, the MINLP problem for the optimal synthesis of process networks is modeled as a discrete optimization problem involving logic disjunctions with nonlinear equations and pure logic relations. The logic disjunctions allow the conditional modeling of equations (e.g. if a unit is selected, apply mass/heat balances; otherwise, set the flow variables to zero). It is first shown that this framework for representing discrete optimization problems greatly simplifies the step of modeling. The outer approximation algorithm is then used as a basis to derive a new logic-based OA solution method which naturally gives rise to NLP sub-problems that avoid zero flows and a disjunctive LP master problem. The initial NLP sub-problems, that provide linearizations for all the terms in the disjunctions, are selected through a set-covering problem for which we consider both the cases of disjunctive and conjunctive normal form logic. The master problem, on the other hand, is converted to mixed-integer form using a convex-hull representation. Furthermore, based on some interesting relations of outer approximation with generalized Benders decomposition, it is also shown that it is possible to derive a logic-based method for the latter algorithm. The proposed algorithm has been tested on several structural optimization problems, including a flowsheet example showing distinct advantages in robustness and computational efficiency when compared to standard MINLP models and algorithms.

An induced matching M of a graph G is a set of pairwise non-adjacent edges such that their end-vertices induce a 1-regular subgraph. An induced matching M is maximal if no other induced matching contains M. The MINIMUM MAXIMAL INDUCED MATCHING problem asks for a minimum maximal induced matching in a given graph. The problem is known to be NP-complete. Here we show that, if P = NP, for any ε > 0, this problem cannot be approximated within a factor of n 1-ε in polynomial time, where n denotes the number of vertices in the input graph. The result holds even if the graph in question is restricted to being bipartite. For the related problem of finding an induced matching of maximum size (MAXIMUM INDUCED MATCHING), it is shown that, if P = NP, for any ε > 0, the problem cannot be approximated within a factor of n 1/2-ε in polynomial time. Moreover, we show that MAXIMUM INDUCED MATCHING is NP-complete for planar line graphs of planar bipartite graphs.

An induced matching M of a graph G is a set of pairwise non-adjacent edges such that their end-vertices induce a 1-regular subgraph. An induced matching M is maximal if no other induced matching contains M. The MINIMUM MAXIMAL INDUCED MATCHING problem asks for a minimum maximal induced matching in a given graph. The problem is known to be NP-complete. Here we show that, if P = NP, for any ε > 0, this problem cannot be approximated within a factor of n 1-ε in polynomial time, where n denotes the number of vertices in the input graph. The result holds even if the graph in question is restricted to being bipartite. For the related problem of finding an induced matching of maximum size (MAXIMUM INDUCED MATCHING), it is shown that, if P = NP, for any ε > 0, the problem cannot be approximated within a factor of n 1/2-ε in polynomial time. Moreover, we show that MAXIMUM INDUCED MATCHING is NP-complete for planar line graphs of planar bipartite graphs.

The structure of a complex system at any given moment is conveniently described as a graph, the nodes of which correspond to the "on" elements of the system, and the arcs to their "on" connections. We will then understand the management of the system structure as determining the sequence and moments of restructuring the system graph over a certain period. Problems of structure management include planning the development of the structure, usually associated with the lengthy, multi-stage creation of large-scale systems: production, fuel and energy, organizational problems of planning a complex of works, etc. A Boolean approach is usually used to describe such problems, and discrete optimization methods are used for their solution. In this article, the methodology for modeling the aforementioned systems is extended to a slightly different class of problems, characterized by the repeated switching on and off of system elements and connections over a certain period. Similar problems arise in the management of production with multi-variant technology, planning the schedule of equipment repairs, etc. In particular, the problem of scheduling an oil refining plant (ORP), which will be used to illustrate the main provisions of this article, can apparently be considered quite general in the class under consideration.

In this paper we present a synthesis of the two phase method for the biobjective assignment problem. The method, which is a general technique to solve multiobjective combinatorial optimization (MOCO) problems, has been introduced by Ulungu in 1993. However, no complete description of the method to find all efficient solutions of the biobjective assignment problem (that allows an independent implementation) has been published. First, we present a complete description of a two phase method for the biobjective assignment problem, with an improved upper bound. Second, a combination of this method with a population based heuristic using path relinking is proposed to improve computational performance. Third, we propose a new technique for the second phase with a ranking approach. All of the methods have been tested on instances of varying size and range of objective function coefficients. We discuss the obtained results and explain our observations based on the distribution of objective function values.

We consider a continuous supply chain network consisting of buffering queues and processors first articulated by and analyzed subsequently by [1] and [4]. A model was proposed for such network by [23] using a system of coupling partial differential equations and ordinary differential equations. In this article, we propose an alternative approach based on a variational method to formulate the network dynamics. We also derive, based on the variational method, an algorithm that guarantees numerical stability, allows for rigorous error estimates, and facilitates efficient computations. A class of network flow optimization problems are formulated as mixed integer programs (MIP). The proposed numerical algorithm and the corresponding MIP are compared theoretically and numerically with existing ones , which demonstrates the modeling and computational advantages of the variational approach.

Minimally nonideal matrices are a key to understanding when the set covering problem can be solved using linear programming. The complete classification of minimally nonideal matrices is an open problem. One of the most important results on these matrices comes from a theorem of Lehman, which gives a property of the core of a minimally nonideal matrix. Cornuejols and Novick gave a conjecture on the possible cores of minimally nonideal matrices. This paper disproves their conjecture by constructing a new infinite family of square minimally nonideal matrices. In particular, we show that there exists a minimally nonideal matrix with r ones in each row and column for any r>=3.

This paper introduces an expanded version of the Invasive Weed Optimization algorithm (exIWO) distinguished by the hybrid strategy of the search space exploration proposed by the authors. The algorithm is evaluated by solving three well-known optimization problems: minimization of numerical functions, feature selection, and the Mona Lisa TSP Challenge as one of the instances of the traveling salesman problem. The achieved results are compared with analogous outcomes produced by other optimization methods reported in the literature.

The expanded Invasive Weed Optimization algorithm (exIWO) is an optimization metaheuristic modelled on the original IWO version created by the researchers from the University of Tehran. The authors of the present paper have extended the exIWO algorithm introducing a set of both deterministic and nondeterministic strategies of individuals’ selection. The goal of the project was to evaluate the exIWO by testing its usefulness for solving some test instances of the traveling salesman problem (TSP) taken from the TSPLIB collection which allows comparing the experimental results with optimal values. Keywords—Expanded Invasive Weed Optimization algorithm (exIWO), Traveling Salesman Problem (TSP), heuristic approach, inversion operator.

An ensemble of random unistochastic (orthostochastic) matrices is defined by taking squared moduli of elements of random unitary (orthogonal) matrices distributed according to the Haar measure on U(N) (or O(N)). An ensemble of symmetric unistochastic matrices is obtained with use of unitary symmetric matrices pertaining to the circular orthogonal ensemble. We study the distribution of complex eigenvalues of bistochastic, unistochastic and orthostochastic matrices in the complex plane. We compute averages (entropy, traces) over the ensembles of unistochastic matrices and present inequalities concerning the entropies of products of bistochastic matrices.

In this paper we introduce the Ameso optimization problem, a special class of discrete optimization problems. We establish its basic properties and investigate the relation between Ameso optimization and the convex optimization. Further, we design an algorithm to solve a multi-dimensional Ameso problem by solving a sequence of one-dimensional Ameso problems. Finally, we demonstrate how the knapsack problem can be solved using the Ameso optimization framework.

La resolucion de problemas para la vida cotidiana ha sido uno de los usos que se le da a la ciencia. La ingenieria ha resuelto varios problemas, por ejemplo minimizar costos, recorridos y secuencias, entre otros, los cuales son considerados problemas de optimizacion combinatoria. Las tecnicas metaheuristicas son algoritmos que ayudan a encontrar soluciones a los problemas combinatorios complejos. En este articulo se estudia el metodo de recocido simulado para la solucion de estos problemas, se describe la metodologia de este proceso y se muestran tres aplicaciones del metodo de recocido simulado dentro de algunas facultades de la UAEM, en el area de materiales, de hidraulica y logistica. Se concluye que el algoritmo meteheuristico de recodido simulado tiene una vasta aplicacion con buenos resultados en muchos tipos de problemas cotidianos.

During the past decades, the study and the control of boundary layer separation have motivated lots of research projects within a wide part of the scientific community, in close interactions with the aeronautical industrial network. In order to develop an energetically efficient strategy to control separation, it is interesting and effective to formulate active flow control problems in terms of optimization problems. In this context we propose here to derive Reduced-Order Models based on Proper Orthogonal Decomposition (POD ROM) that can reproduce with a sufficient degree of reliability the spatio-temporal dynamics of separated flows. As a matter of fact, the growing interest for these models comes from their potential role as surrogate models, in the resolution of large-scale constrained optimization problems that are frequently encountered in flow control. The general approach consists in substituting the high-fidelity model of Navier-Stokes equations by an approximated model that captures the essential features of the original dynamics, and furthermore is cheaper to compute. POD, which is the optimal decomposition in terms of energy, can be used to describe the flow in a low dimensional subspace spanned by a few number of dominant modes. However, it can happen that the traditional POD-Galerkin approach results in a poorly accurate or unstable POD ROM. Thus in this work various calibration methods are set up and compared to improve the efficiency of this model. The main idea behind the calibration framework proposed here is to determine in the POD ROM system of equations, auxiliary parameters that are computed by resolving appropriate constrained minimization problems. Finally the calibration methods are assessed for three flow configurations of different complexity: the wake flow behind a circular cylinder simulated by DNS at R e = 200; the separated flow on the upper-surface of an

The paper is devoted to a model of compact cyclic edge-coloring of graphs. This variant of edge-coloring finds its applications in modeling schedules in production systems, in which production proceeds in a cyclic way. We point out optimal colorings for some graph classes and we construct graphs which cannot be colored in a compact cyclic manner. Moreover, we prove some theoretical properties of considered coloring model such as upper bounds on the number of colors in optimal compact cyclic coloring.

The "roof dual" of a QUBO (Quadratic Unconstrained Binary Optimization) problem has been introduced in [P.L. Hammer, P. Hansen, B. Simeone, Roof duality, complementation and persistency in quadratic 0-1 optimization, Mathematical Programming 28 (1984) 121-155]; it provides a bound to the optimum value, along with a polynomial test of the sharpness of this bound, and (due to a "persistency" result) it also determines the values of some of the variables at the optimum. In this paper we provide a graph-theoretic approach to provide bounds, which includes as a special case the roof dual bound, and show that these bounds can be computed in O(n 3 ) time by using network flow techniques. We also obtain a decomposition theorem for quadratic pseudo-Boolean functions, improving the persistency result of [P.L. Hammer, P. Hansen, B. Simeone, Roof duality, complementation and persistency in quadratic 0-1 optimization, Mathematical Programming 28 (1984) 121-155]. Finally, we show that the proposed bounds (including roof duality) can be applied in an iterated way to obtain significantly better bounds. Computational experiments on problems up to thousands of variables are presented.

A robust multi-period model is proposed to minimize the energy consumption of IP networks, while guaranteeing the satisfaction of uncertain traffic demands. Energy savings are achieved by putting into sleep mode cards and chassis. The study of the solution robustness shows that there is a trade-off between energy consumption and the solutions conservatism degree. The model allows this trade-off to be tuned by simply modifying a single parameter per link. The multi-period optimization is constrained by inter-period limitations necessary to guarantee network stability. Both, exact and heuristic methods are proposed. Results show that up to 60% of the energy savings can be achieved for realistic test scenarios in networks operated with flow-based routing protocols (i.e. MPLS) and with a good level of robustness to traffic variations.

The bicriteria problem is an important problem in multiobjective optimization that has been extensively studied in the literature. Practical applications and algorithmic investigations of this problem are numerous. We have developed an efficient interactive solution framework for solving bicriteria integer programming problems. In this framework, a decision maker is assumed to have an implicit utility function of the objectives he wishes to maximize, and the function is considered to be pseudoconcave and nondecreasing. The decision-maker's preference structure is assessed using pairwise comparison questions, and the problem is' solved by an interactive branch-and-bound method, in which the decision maker participates in the solution process. The bicriteria problem has several special properties, and the solution framework employs several algorithmic components that exploit these properties leading to an efficient solution process. In this article, we report on a detailed performance investigation carried out on the solution framework. The results show that the proposed approach is viable for solving practical problems of medium size with nonlinear utility functions.

The crossing number of a graph is the minimum number of edge crossings in any drawing of the graph in the plane. Extensive research has produced bounds on the crossing number and exact formulae for special graph classes, yet the crossing numbers of graphs such as K 11 or K 9,11 are still unknown. Finding the crossing number is NP-hard for general graphs and no practical algorithm for its computation has been published so far. We present an integer linear programming formulation that is based on a reduction of the general problem to a restricted version of the crossing number problem in which each edge may be crossed at most once. We also present cutting plane generation heuristics and a column generation scheme. As we demonstrate in a computational study, a branch-and-cut algorithm based on these techniques as well as recently published preprocessing algorithms can be used to successfully compute the crossing number for small-to medium-sized general graphs for the first time.

The crossing number of a graph is the minimum number of edge crossings in any drawing of the graph in the plane. Extensive research has produced bounds on the crossing number and exact formulae for special graph classes, yet the crossing numbers of graphs such as K 11 or K 9,11 are still unknown. Finding the crossing number is NP-hard for general graphs and no practical algorithm for its computation has been published so far. We present an integer linear programming formulation that is based on a reduction of the general problem to a restricted version of the crossing number problem in which each edge may be crossed at most once. We also present cutting plane generation heuristics and a column generation scheme. As we demonstrate in a computational study, a branch-and-cut algorithm based on these techniques as well as recently published preprocessing algorithms can be used to successfully compute the crossing number for small-to medium-sized general graphs for the first time.