Search results for "Integer"

Restricted compositions and permutations: from old to new Gray codes

2011

Any Gray code for a set of combinatorial objects defines a total order relation on this set: x is less than y if and only if y occurs after x in the Gray code list. Let @? denote the order relation induced by the classical Gray code for the product set (the natural extension of the Binary Reflected Gray Code to k-ary tuples). The restriction of @? to the set of compositions and bounded compositions gives known Gray codes for those sets. Here we show that @? restricted to the set of bounded compositions of an interval yields still a Gray code. An n-composition of an interval is an n-tuple of integers whose sum lies between two integers; and the set of bounded n-compositions of an interval si…

Comment on “A simple way to incorporate uncertainty and risk into forest harvest scheduling”

2017

In a recent research article, Robinson et al. (2016) described a method of estimating uncertainty of harvesting outcomes by analyzing the historical yield to the associated prediction for a large number of harvest operations. We agree with this analysis, and consider it a useful tool to integrate estimates of uncertainty into the optimization process. The authors attempt to manage the risk using two different methods, based on deterministic integer linear programming. The first method focused on maximizing the 10th quantile of the distribution of predicted volume subject to area constraint, while the second method focused on minimizing the variation of total quantity of volume harvested sub…

Landowner preferences and conservation prioritization: response to Nielsen et al.

2017

Decorous combinatorial lower bounds for row layout problems

2020

Abstract In this paper we consider the Double-Row Facility Layout Problem (DRFLP). Given a set of departments and pairwise transport weights between them the DRFLP asks for a non-overlapping arrangement of the departments along both sides of a common path such that the weighted sum of the center-to-center distances between the departments is minimized. Despite its broad applicability in factory planning, only small instances can be solved to optimality in reasonable time. Apart from this even deriving good lower bounds using existing integer programming formulations and branch-and-cut methods is a challenging problem. We focus here on deriving combinatorial lower bounds which can be compute…

Mathematical models for a cutting problem in the glass manufacturing industry

2021

Abstract The glass cutting problem proposed for the ROADEF 2018 challenge is a two-dimensional, three-stage guillotine cutting process, with an additional cut to obtain pieces in some specific situations. However, it is not a standard problem because it includes specific constraints. The sheets produced in the glass manufacturing process have defects that make them different and have to be used in order. The pieces to be cut are grouped into subsets and the pieces from each subset must be cut in order. We approach the problem by developing and solving integer linear models. We start with the basic model, which includes the essential features of the problem, as a classical three-stage cuttin…

Decomposition and Mean-Field Approach to Mixed Integer Optimal Compensation Problems

2016

Mixed integer optimal compensation deals with optimization problems with integer- and real-valued control variables to compensate disturbances in dynamic systems. The mixed integer nature of controls could lead to intractability in problems of large dimensions. To address this challenge, we introduce a decomposition method which turns the original n-dimensional optimization problem into n independent scalar problems of lot sizing form. Each of these problems can be viewed as a two-player zero-sum game, which introduces some element of conservatism. Each scalar problem is then reformulated as a shortest path one and solved through linear programming over a receding horizon, a step that mirro…

Alignment-free sequence comparison using absent words

2018

Sequence comparison is a prerequisite to virtually all comparative genomic analyses. It is often realised by sequence alignment techniques, which are computationally expensive. This has led to increased research into alignment-free techniques, which are based on measures referring to the composition of sequences in terms of their constituent patterns. These measures, such as $q$-gram distance, are usually computed in time linear with respect to the length of the sequences. In this paper, we focus on the complementary idea: how two sequences can be efficiently compared based on information that does not occur in the sequences. A word is an {\em absent word} of some sequence if it does not oc…

Reverse-safe data structures for text indexing

2021

We introduce the notion of reverse-safe data structures. These are data structures that prevent the reconstruction of the data they encode (i.e., they cannot be easily reversed). A data structure D is called z-reverse-safe when there exist at least z datasets with the same set of answers as the ones stored by D. The main challenge is to ensure that D stores as many answers to useful queries as possible, is constructed efficiently, and has size close to the size of the original dataset it encodes. Given a text of length n and an integer z, we propose an algorithm which constructs a z-reverse-safe data structure that has size O(n) and answers pattern matching queries of length at most d optim…

Variable Fixing for Two-Arc Sequences in Branch-Price-and-Cut Algorithms on Path-Based Models

2020

Variable fixing by reduced costs is a popular technique for accelerating the solution process of mixed-integer linear programs. For vehicle-routing problems solved by branch-price-and-cut algorithms, it is possible to fix to zero the variables associated with all routes containing at least one arc from a subset of arcs determined according to the dual solution of a linear relaxation. This is equivalent to removing these arcs from the network used to generate the routes. In this paper, we extend this technique to routes containing sequences of two arcs. Such sequences or their arcs cannot be removed directly from the network because routes traversing only one arc of a sequence might still b…

A more efficient cutting planes approach for the green vehicle routing problem with capacitated alternative fuel stations

2021

AbstractThe Green Vehicle Routing Problem with Capacitated Alternative Fuel Stations assumes that, at each station, the number of vehicles simultaneously refueling cannot exceed the number of available pumps. The state-of-the-art solution method, based on the generation of all feasible non-dominated paths, performs well only with up to 2 pumps. In fact, it needs cloning the paths between every pair of pumps. To overcome this issue, in this paper, we propose new path-based MILP models without cloning paths, for both the scenario with private stations (i.e., owned by the fleet manager) and that with public stations. Then, a more efficient cutting plane approach is designed for addressing both…