Counting models for two conjunctive forms (2-CF), problem known as #2SAT, is a classic #P-complete problem. We determine different discrete structures on the constrained graph of the 2-CF formula allowing the efficien...
详细信息
An equitable graph coloring is a proper vertex coloring of a graph G where the sizes of the color classes differ by at most one. The equitable chromatic number, denoted by eq(G), is the smallest number k such that G a...
详细信息
An equitable graph coloring is a proper vertex coloring of a graph G where the sizes of the color classes differ by at most one. The equitable chromatic number, denoted by eq(G), is the smallest number k such that G admits such equitable k-coloring. We focus on enumerative algorithms for the computation of eq(G) and propose a general scheme to derive pruning rules for them: We show how the extendability of a partial coloring into an equitable coloring can be modeled via network flows. Thus, we obtain pruning rules which can be checked via flow algorithms. Computational experiments show that the search tree of enumerative algorithms can be significantly reduced in size by these rules and, in most instances, such naive approach even yields a faster algorithm. Moreover, the stability, i.e., the number of solved instances within a given time limit, is greatly improved. Since the execution of flow algorithms at each node of a search tree is time consuming, we derive arithmetic pruning rules (generalized Hall-conditions) from the network model. Adding these rules to an enumerative algorithm yields an even larger runtime improvement.
Bilevel linear optimization problems are the linear optimization problems with two sequential decision steps of the leader and the follower. In this paper, we focus on the ambiguity of coefficients of the follower in ...
详细信息
Bilevel linear optimization problems are the linear optimization problems with two sequential decision steps of the leader and the follower. In this paper, we focus on the ambiguity of coefficients of the follower in his objective function that hinder the leader from exactly calculating the rational response of the follower. Under the assumption that the follower's possible range of the ambiguous coefficient vector is known as a certain convex polytope, the leader can deduce the possible set of rational responses of the follower. The leader further assumes that the follower's response is the worst-case scenario to his objective function, and then makes a decision according to the maximin criteria. We thus formulate the bilevel linear optimization problem with ambiguous objective function of the follower as a special kind of three-level programming problem. In our formulation, we show that the optimal solution locates on the extreme point and propose a solution method based on the enumeration of possible rational responses of the follower. A numerical example is used to illustrate our proposed computational method.
Checkerboard patterns belong to a special class of 2-stage guillotine patterns that require less machine time to be cut. In this paper we propose an enumerative algorithm to generate exact constrained checkerboard pat...
详细信息
Checkerboard patterns belong to a special class of 2-stage guillotine patterns that require less machine time to be cut. In this paper we propose an enumerative algorithm to generate exact constrained checkerboard patterns. At each node of the enumeration tree a constructive procedure is used to generate a feasible pattern. In addition, an upper bound on the objective function value is calculated to decide whether further branching from the node is worth. The algorithm was implemented and computational tests were performed. The test results indicate that the proposed scheme outperforms previous methods of the literature in terms of execution times. (c) 2006 Published by Elsevier Ltd.
Given a directed network G(N;A), the minimum feedback arc set problem is to find a minimal weighted subset of arcs A' subset of A so that G(N;A\A') is acyclic. We first provide a mixed 0-1 integer programming ...
详细信息
Given a directed network G(N;A), the minimum feedback arc set problem is to find a minimal weighted subset of arcs A' subset of A so that G(N;A\A') is acyclic. We first provide a mixed 0-1 integer programming formulation whose LP relaxation can be solved by a strongly polynomial algorithm of complexity O(vertical bar N vertical bar(3) log vertical bar N vertical bar). An enumerative framework is provided which makes use of this relaxation repeatedly. We also provide a result which gives rise to a heuristic algorithm.
A partially enumerative algorithm is presented for the maximum clique problem which is very simple to implement. Computational results for an efficient implementation on an IBM 3090 computer are provided for randomly ...
详细信息
A partially enumerative algorithm is presented for the maximum clique problem which is very simple to implement. Computational results for an efficient implementation on an IBM 3090 computer are provided for randomly generated graphs with up to 3000 vertices and over one million edges. Also provided are exact specifications for test problems to facilitate future comparisons. In addition, the Fortran 77 code of the proposed algorithm is given.
The uniform switching system is the family of non-linear n x m binary arrays constrained such that all columns are from the constant weight k vectors and all rows have weights divisible by p > 0. For this system, w...
详细信息
The uniform switching system is the family of non-linear n x m binary arrays constrained such that all columns are from the constant weight k vectors and all rows have weights divisible by p > 0. For this system, we present a cardinality formula and an enumerative algorithm.
Gas and particulate emissions from ship transportation have been increasing in recent years. In order to mitigate ship emissions near coastal areas, voluntary vessel speed reduction incentive programs (VSRIPs) were pu...
详细信息
Gas and particulate emissions from ship transportation have been increasing in recent years. In order to mitigate ship emissions near coastal areas, voluntary vessel speed reduction incentive programs (VSRIPs) were put in place by a number of ports. This paper studies a schedule design problem faced by liner shipping companies under VSRIPs. It proposes a mixed-integer nonlinear mathematical model for the minimization of the total cost, consisting of fuel cost, as well as operating cost, minus dockage refunds. The model balances three determinants, that is, the compliance of VSRIPs, the speed limit (the maximum physical speed of ships and the upper speed limit imposed by VSRIPs), and the limited number of ships. An enumerative algorithm and a piecewise-linear approximation algorithm are developed, based on some properties of the nonlinear model. The efficiency of the proposed algorithms is validated through extensive computational experiments.
Counting models for a two conjunctive formula (2-CF) F, a problem known as #2SAT, is a classic #P complete problem. Given a 2-CF F as input, its constraint graph G is built. If G is acyclic, then #2SAT(F) can be compu...
详细信息
Counting models for a two conjunctive formula (2-CF) F, a problem known as #2SAT, is a classic #P complete problem. Given a 2-CF F as input, its constraint graph G is built. If G is acyclic, then #2SAT(F) can be computed efficiently. In this paper, we address the case when G has cycles. When is cyclic, we propose a decomposition on the constraint graph G that allows the computation of #2SAT(F) in incremental way. Let T be a cactus graph of G containing a maximal number of independent cycles, and let (T) over bar = (E(G) - E(T)) be a subset of frond edges from G. The clauses in (T) over bar are ordered in connected components {K-1 , . . . , K-r}. Each (G U K-i), i = 1, . . . ,r is a knot (a set of intersected cycles) of the graph. The arrangement of the clauses of (T) over bar allows the decomposition of G in knots and provides a way of computing #2SAT(F) in an incremental way. Our procedure has a bottom-up orientation for the computation of #2SAT(F). It begins with F-0 = T. In each iteration of the procedure, a new clause C-i is an element of(T) over bar is considered in order to form F-i = (Fi-1 boolean AND C-i) and then to compute #2SAT(F-i) based on the computation of #2SAT(Fi-1).
The molecular weight of a protein may be partitioned in different ways as the sum of the molecular weights of its constituent proteins. The problem of enumerating the different decomposition products is equivalent to ...
详细信息
The molecular weight of a protein may be partitioned in different ways as the sum of the molecular weights of its constituent proteins. The problem of enumerating the different decomposition products is equivalent to that of finding different partitions of an integer. In this paper, some computational algorithms for solving this problem are studied, and their efficiency is evaluated.
暂无评论