ORBi Collection: Quantitative methods in economics & management
http://hdl.handle.net/2268/71
The Collection's search engineSearch this channelsearch
http://orbi.ulg.ac.be/simple-search
A bi-objective model for intermodal transport
http://hdl.handle.net/2268/205453
Title: A bi-objective model for intermodal transport
<br/>
<br/>Author, co-author: Mostert, Martine; Limbourg, SabineIntermodal network design: a three-mode bi-objective model applied to the case of Belgium
http://hdl.handle.net/2268/205111
Title: Intermodal network design: a three-mode bi-objective model applied to the case of Belgium
<br/>
<br/>Author, co-author: Mostert, Martine; Caris, An; Limbourg, Sabine
<br/>
<br/>Abstract: Freight transport planning is nowadays encouraged to align with environmental objectives. Among those, climate change is of particular interest for many countries. In its White Paper on Transport, the European Commission considers intermodal transport as a potential solution for reducing environmental impacts. In order to make good strategic transport decisions, realistic decision support models for freight transport networks must be developed, so that insights can be derived for the different stakeholders of the transportation chain. This research proposes a bi-objective mathematical formulation which takes into account economic and environmental objectives, on a road and intermodal network with three modes of transport (road, intermodal rail, and intermodal inland waterways), and in which economies of scale of intermodal transport can be considered. With this model better fitting reality, an application to the Belgian case study provides practical information on how flows, terminal types and locations vary depending on the chosen policy, on the integration or not of economies of scale, on costs or emissions modifications and on the number of terminals to locate. Results show that the chosen policy influences the terminal type and the intermodal market share. The study also highlights the interest of intermodal transport on short distances, and the risk of flow exchanges inside the intermodal market share, rather than between road and intermodal transport.A class of valid inequalities for multilinear 0-1 optimization problems
http://hdl.handle.net/2268/204587
Title: A class of valid inequalities for multilinear 0-1 optimization problems
<br/>
<br/>Author, co-author: Rodriguez Heck, Elisabeth; Crama, YvesQuadratic reformulations of nonlinear binary optimization problems
http://hdl.handle.net/2268/204497
Title: Quadratic reformulations of nonlinear binary optimization problems
<br/>
<br/>Author, co-author: Crama, YvesA column generation approach to job grouping for flexible manufacturing systems
http://hdl.handle.net/2268/204061
Title: A column generation approach to job grouping for flexible manufacturing systems
<br/>
<br/>Author, co-author: Crama, Yves; Oerlemans, Alwin G.
<br/>
<br/>Abstract: A flexible manufacturing system consists of a number of NC-machines, linked by automated material handling devices, that perform the various operations required to manufacture parts. Each operation requires different tools. These tools are stored in a limited capacity tool magazine attached to each machine. When it becomes necessary to add or remove tools from the tool magazine, the machine may have to be shut down for a setup. In this paper, we study a model which aims at minimizing the number of setups. We assume that N jobs must be processed on a machine. Each job requires a certain set of tools, which have to be present in the tool magazine of the machine when the job is executed. The magazine has a total capacity of C tools. We say that a group (subset, batch) of jobs is feasible if, together, these jobs do not require more than C tools. The job grouping problem is to partition the jobs into a minimum number of feasible groups. The problem can be formulated as a set covering problem. We solve the linear relaxation of this formulation in order to obtain tight lower bounds. Since the number of variables is potentially huge, we use a column generation approach. The column generation subproblem turns out to be NP-hard; we solve it by enumeration. We also describe some fast and simple heuristics for the job grouping problem. The result of our computational experiments is that the lower bound is extremely strong. The quality of the heuristic solutions is in general very good too. We also investigate a more general multiple-machine model in which each tool may occupy several slots in the tool magazines.On the strength of relaxations of multidimensional knapsack problems
http://hdl.handle.net/2268/204060
Title: On the strength of relaxations of multidimensional knapsack problems
<br/>
<br/>Author, co-author: Crama, Yves; Mazzola, Joseph B.
<br/>
<br/>Abstract: Branch-and-bound algorithms for integer programming problems typically employ bounds derived from well-known relaxations, such as the Lagrangian, surrogate, or composite relaxations. Although the bounds derived from these relaxations are stronger than the bound obtained from the linear programming relaxation (LPR), in the case of multidimensional knapsack problems, i.e., integer programming problems with nonnegative objective-function and constraint coefficients, the improvement in the bound that can be realized using these relaxations is limited. In particular, we show that the improvement in the quality of the bound using any of these relaxations cannot exceed the magnitude of the largest coefficient in the objective function, nor can it exceed one-half of the optimal objective-function value of LPR. This implies, for example, that for those problem classes in which all of the objective-function coefficients are equal to 1, the bound derived from the surrogate relaxation cannot be better than the bound obtained by simply rounding the LPR bound. Awareness of these properties is important in the development of algorithms, since this class of problems subsumes many well-known integer programming problems.Berge-acyclic multilinear 0-1 optimization problems
http://hdl.handle.net/2268/204059
Title: Berge-acyclic multilinear 0-1 optimization problems
<br/>
<br/>Author, co-author: Buchheim, Christoph; Crama, Yves; Rodriguez Heck, ElisabethLes problèmes “riches” de tournées de véhicules
http://hdl.handle.net/2268/203869
Title: Les problèmes “riches” de tournées de véhicules
<br/>
<br/>Author, co-author: Limbourg, SabineLa compétitivité du transport intermodal
http://hdl.handle.net/2268/203868
Title: La compétitivité du transport intermodal
<br/>
<br/>Author, co-author: Limbourg, SabineApproximation algorithms for integer covering problems via greedy column generation
http://hdl.handle.net/2268/203417
Title: Approximation algorithms for integer covering problems via greedy column generation
<br/>
<br/>Author, co-author: Crama, Yves; Van de Klundert, Joris
<br/>
<br/>Abstract: Many combinatorial optimization problems can be formulated as covering problems. In some cases, this covering formulation is not polynomial in the input size of the original problem. In order to solve the problem approximately one can apply the greedy algorithm to the covering formulation. In this case, the column generation subproblem is to determine which column the greedy algorithm chooses. This problem might be NP-hard in itself. We propose a modification of the greedy algorithm in which the column generation subproblem is solved approximately, within a factor α. We derive upper bounds for the worst case ratio of this algorithm and related polynomial approximation algorithms.Complexity of product positioning and ball intersection problems
http://hdl.handle.net/2268/203415
Title: Complexity of product positioning and ball intersection problems
<br/>
<br/>Author, co-author: Crama, Yves; Hansen, Pierre; Jaumard, Brigitte
<br/>
<br/>Abstract: The product positioning problem consists in choosing the attributes of a new product in such a way as to maximize its market share, i.e., to attract a maximum number of customers. Mathematically, the problem can be formulated as follows: given a set of balls (with respect to some norm) and a weight associated to each ball, find a point which maximizes the sum of the weights of the balls containing it. The complexity of this problem is investigated in the case of the L∞ and of the Euclidean norms. In both cases, the problem is proved to be NP-hard, but to be polynomially solvable when the dimension of the space is fixed.Valid inequalities and facets for a hypergraph model of the nonlinear knapsack and FMS part-selection problems
http://hdl.handle.net/2268/203414
Title: Valid inequalities and facets for a hypergraph model of the nonlinear knapsack and FMS part-selection problems
<br/>
<br/>Author, co-author: Crama, Yves; Mazzola, Joseph B.
<br/>
<br/>Abstract: This paper defines the dense subhypergraph problem (DSP), which provides a modelling framework for the nonlinear knapsack problem and other well-known problems arising in areas such as capital budgeting, flexible manufacturing system production planning, repair-kit selection, and compiler construction. We define several families of valid inequalities and state conditions under which these inequalities are facet-defining for DSP. We also explore the polyhedral structure of the cardinality-constrained DSP. Finally, we examine a special case of this problem that arises, for example, within the context of Lagrangian decomposition. For this case, we present a complete description of the convex hull of the feasible region.Models for machine-part grouping in cellular manufacturing
http://hdl.handle.net/2268/203079
Title: Models for machine-part grouping in cellular manufacturing
<br/>
<br/>Author, co-author: Crama, Yves; Oosten, Maarten
<br/>
<br/>Abstract: For cellular manufacturing strategies to succeed, the productive system first has to be divided into highly independent cells. This means that a partition of the machines into machine groups, a partition of the parts into part families, and a matching between the machine groups and the part families have to be simultaneously determined. Mathematically, this question can be expressed as the problem of finding a near block diagonal permutation of the machine-part incidence matrix. Research on such grouping problems has primarily concentrated on the design of heuristics. Different grouping efficiency criteria have been proposed to express the quality of the groupings proposed by these heuristics. This paper is concerned with mathematical programming approaches to the formation of production cells. Existing models are reviewed and their features are briefly discussed. An alternative model is proposed, which allows for the formulation of various constraints and grouping efficiency criteria. Finally, some test problems are used to support the claim that this model may be adequate for the solution to optimality of the cell formation problem.The component retrieval problem in printed circuit board assembly
http://hdl.handle.net/2268/203078
Title: The component retrieval problem in printed circuit board assembly
<br/>
<br/>Author, co-author: Crama, Yves; Flippo, Olaf E.; Van de Klundert, Joris; Spieksma, Frits C.R.
<br/>
<br/>Abstract: The minimization of the makespan of a printed circuit board assembly process is a complex problem. Decisions involved in this problem concern the specification of the order in which components are to be placed on the board, and the assignment of component types to the feeder slots of the placement machine. If some component types are assigned to multiple feeder slots, then the additional problem emerges of selecting, for each placement on the board, the feeder slot from which the related component type is to be retrieved. In this paper, we consider this Component Retrieval Problem for placement machines that operate in a similar way as the Fuji CP II. We explain why a simple forward dynamic programming scheme cannot provide an efficient solution to this problem, thereby invalidating the correctness of an earlier published approach. We then present a polynomial algorithm that solves the problem to optimality. The analysis of the Component Retrieval Problem is greatly facilitated by its reformulation as a longest path problem in a PERT/CPM network with design aspects. Finding the minimal makespan of the assembly process thus amounts to identifying a design for which the longest path in the induced network is shortest. As an alternative interpretation, the Component Retrieval Problem can be viewed as a shortest path problem with side-constraints. The complexity of these network problems is analysed, and it is proven that the polynomial solvability of the Component Retrieval Problem is caused by the specific structure it inflicts on the arc lengths in the network. In the absence of this structure, the network problems are shown to be NP- hard in general.Scheduling jobs of equal length: complexity, facets and computational results
http://hdl.handle.net/2268/202812
Title: Scheduling jobs of equal length: complexity, facets and computational results
<br/>
<br/>Author, co-author: Crama, Yves; Spieksma, Frits C.R.
<br/>
<br/>Abstract: The following problem was originally motivated by a question arising in the automated assembly of printed circuit boards. Given aren jobs, which have to be performed on a single machine within a fixed timespan [0,T], subdivided into T unit-length subperiods. The processing time (or length) of each job equals p,p ∈ ℕ. The processing cost of each job is an arbitrary function of its start-time. The problem is to schedule all jobs so as to minimize the sum of the processing costs.
This problem is proved to be NP-hard, already for p=2 and 0–1 processing costs. On the other hand, when T=np+c, with c constant, the problem can be solved in polynomial time. A partial polyhedral description of the set of feasible solutions is presented. In particular, two classes of facet-defining inequalities are described, for which the separation problem is polynomially solvable. Also, we exhibit a class of objective functions for which the inequalities in the LP-relaxation guarantee integral solutions.
Finally, we present a simple cutting plane algorithm and report on its performance on randomly generated problem instances.Production Planning in Automated Manufacturing
http://hdl.handle.net/2268/202760
Title: Production Planning in Automated Manufacturing
<br/>
<br/>Author, co-author: Crama, Yves; Oerlemans, Alwin G.; Spieksma, Frits C.R.The polytope of block diagonal matrices and complete bipartite partitionings
http://hdl.handle.net/2268/202758
Title: The polytope of block diagonal matrices and complete bipartite partitionings
<br/>
<br/>Author, co-author: Crama, Yves; Oosten, Maarten
<br/>
<br/>Abstract: Motivated by a fundamental clustering problem arising in several areas (production management, marketing, numerical analysis, etc.), we investigate the facial structure of the polytope whose extreme points are all 0–1 block diagonal matrices. For this polytope, general properties of facet-defining inequalities are investigated and specific families of facets are identified. Various techniques for lifting or combining facet-defining inequalities into new ones are also presented. Throughout the paper, a block diagonal matrix is regarded as the adjacency matrix of a disjoint union of complete bipartite graphs. The presentation and the derivation of the results heavily rely on this graph-theoretic interpretation.The assembly of printed circuit boards: A case with multiple machines and multiple board types
http://hdl.handle.net/2268/202757
Title: The assembly of printed circuit boards: A case with multiple machines and multiple board types
<br/>
<br/>Author, co-author: Crama, Yves; Flippo, Olaf E.; Van de Klundert, Joris; Spieksma, Frits C.R.
<br/>
<br/>Abstract: In this paper a typical situation arising in the assembly of printed circuit boards is investigated. The planning problem we face is how to assemble boards of different types using a single line of placement machines. From a practical viewpoint, the multiplicity of board types adds significantly to the complexity of the problem, which is already very hard to solve in the case of a single board type. In addition, relatively few studies deal with the multiple board type case. We propose a solution procedure based on a hierarchical decomposition of the planning problem. An important subproblem in this decomposition is the so-called feeder rack assignment problem. By taking into account as much as possible the individual board type characteristics (as well as the machine characteristics) we heuristically solve this problem. The remaining subproblems are solved using constructive heuristics and local search methods. The solution procedure is tested on real-life instances. It turns out that, in terms of the makespan, we can substantially improve the current solutions.Combinatorial optimization models for production scheduling in automated manufacturing systems
http://hdl.handle.net/2268/202658
Title: Combinatorial optimization models for production scheduling in automated manufacturing systems
<br/>
<br/>Author, co-author: Crama, Yves
<br/>
<br/>Abstract: Production planning and scheduling models arising in automated manufacturing environments exhibit several features not encountered in models developed for traditional production systems. For instance, models of automated facilities typically include tooling constraints which reflect the possibility for a machine to use different tools in order to perform successive operations, within limits imposed by the size of the tool magazine. Also, these models often account for the existence of flexible material handling systems whose activities must be synchronized with the machining operations in order to optimize system utilization. In this paper, we describe a few interesting combinatorial optimization problems proposed in this framework, we point to their relationships with models investigated in seemingly remote areas, and we identify a number of
challenging open problems.Hitting or avoiding balls in Euclidean space
http://hdl.handle.net/2268/202636
Title: Hitting or avoiding balls in Euclidean space
<br/>
<br/>Author, co-author: Crama, Yves; Ibaraki, Toshihide
<br/>
<br/>Abstract: We investigate the algorithmic complexity of several geometric problems of the following type: given a "feasible" box and a collection of balls in Euclidean space, find a feasible point which is covered by as few or, respectively, by as many balls as possible. We establish that all these problems are NP-hard in their most general version. We derive tight lower and upper bounds on the complexity of their one-dimensional versions. Finally, we show that all these problems can be solved in polynomial time when the dimension of the space is fixed.