The following operators can be used to better focus your queries.
( ) , AND, OR, NOT, W/#
? single char wildcard, not at start
* multi char wildcard, not at start
(Cat? OR feline) AND NOT dog?
Cat? W/5 behavior
(Cat? OR feline) AND traits
Cat AND charact*
This guide provides a more detailed description of the syntax that is supported along with examples.
This search box also supports the look-up of an IP.com Digital Signature (also referred to as Fingerprint); enter the 72-, 48-, or 32-character code to retrieve details of the associated file or submission.
Concept Search - What can I type?
For a concept search, you can enter phrases, sentences, or full paragraphs in English. For example, copy and paste the abstract of a patent application or paragraphs from an article.
Concept search eliminates the need for complex Boolean syntax to inform retrieval. Our Semantic Gist engine uses advanced cognitive semantic analysis to extract the meaning of data. This reduces the chances of missing valuable information, that may result from traditional keyword searching.
When matching problems are used to solve the Traveling Salesman Problem it is necessary to force specific arcs to appear in their solutions. This article shows an efficient means to accomplish this.
English (United States)
This text was extracted from a PDF file.
This is the abbreviated version, containing approximately
52% of the total text.
Page 1 of 2
Means for Forcing Arcs in Solutions to Matching Problems
When matching problems are used to solve the Traveling Salesman Problem
it is necessary to force specific arcs to appear in their solutions. This article
shows an efficient means to accomplish this.
The algorithm forces arcs to belong to a solution of a weighted bipartite
matching. The bipartite weighted matching problem is a problem in which there is
a bipartite graph with N source nodes, N sink nodes, and edges (i, j) where i is a
source node and j is a sink node. Each edge carries a weight wt(i, j). The
objective is to find a maximum matching of minimum weight. A matching is a
subset of edges with the property that no sink or source node touches more than
one edge in the matching. A maximal matching is a matching that contains as
many edges as possible.
When this algorithm is used in branch-and-bound contexts such as in the
solution to the Traveling Salesman Problem , the algorithm is started with an
initial set of arcs, some of which can be broken and some of which cannot be
broken. The branch-and-bound control also forces some arcs to be of infinite
weight. The latter constraint is relatively easy to incorporate into an algorithm,
because it is enforced by setting the weight of the corresponding arc to a very
large value. Forcing an arc to be included is not so easy to do. If the weight is
set to 0, the arc may not necessarily appear in every solution. If the weight is set
to a large negative value, the algorithm may fail because it cannot deal properly
with negative edges.
One possible approach is to set all other edges from the source node to
infinite weight and to set all other edges that enter the sink node to infinite
weight. This method works adequately, and is used in practice. However, the
work required is proportional to the number of nodes in the bipartite graph.
The new method is more efficient. It takes advantage of the fact that
algorithms for solving weighted-bipartite matchings treat edges in a matching as
edges whose removal can reduce the cost of the matching by th...