<html>

  <head>
    <title>
      PARTITION_PROBLEM - The Partition Problem
    </title>
  </head>

  <body bgcolor="#eeeeee" link="#cc0000" alink="#ff3300" vlink="#000055">

    <h1 align = "center">
      PARTITION_PROBLEM <br> The Partition Problem
    </h1>

    <hr>

    <p>
      <b>PARTITION_PROBLEM</b>
      is a FORTRAN77 library which
      seeks solutions of the partition problem, splitting a set of integers into
      two subsets with equal sum.
    </p>

    <h3 align = "center">
      Licensing:
    </h3>

    <p>
      The computer code and data files described and made available on this web page
      are distributed under
      <a href = "../../txt/gnu_lgpl.txt">the GNU LGPL license.</a>
    </p>

    <h3 align = "center">
      Languages:
    </h3>

    <p>
      <b>PARTITION_PROBLEM</b> is available in
      <a href = "../../c_src/partition_problem/partition_problem.html">a C version</a> and
      <a href = "../../cpp_src/partition_problem/partition_problem.html">a C++ version</a> and
      <a href = "../../f_src/partition_problem/partition_problem.html">a FORTRAN90 version</a> and
      <a href = "../../f77_src/partition_problem/partition_problem.html">a FORTRAN77 version</a> and
      <a href = "../../m_src/partition_problem/partition_problem.html">a MATLAB version</a>.
    </p>

    <h3 align = "center">
      Related Data and Programs:
    </h3>

    <p>
      <a href = "../../f77_src/combination_lock/combination_lock.html">
      COMBINATION_LOCK</a>,
      a FORTRAN77 program which
      simulates the process of determining the secret combination of a lock.
    </p>

    <p>
      <a href = "../../f_src/combo/combo.html">
      COMBO</a>,
      a FORTRAN90 library which
      includes many combinatorial routines.
    </p>

    <p>
      <a href = "../../f77_src/knapsack/knapsack.html">
      KNAPSACK</a>,
      a FORTRAN77 library which
      solves a variety of knapsack problems.
    </p>

    <p>
      <a href = "../../f77_src/lamp/lamp.html">
      LAMP</a>,
      a FORTRAN77 library which
      solves linear assignment and matching problems.
    </p>

    <p>
      <a href = "../../f_src/lau_np/lau_np.html">
      LAU_NP</a>,
      a FORTRAN90 library which
      implements heuristic algorithms for various NP-hard combinatorial problems.
    </p>

    <p>
      <a href = "../../datasets/partition_problem/partition_problem.html">
      PARTITION_PROBLEM</a>,
      a dataset directory which
      contains examples of the partition problem, in which a set of numbers is given,
      and it is desired to break the set into two subsets with equal sum.
    </p>

    <p>
      <a href = "../../f77_src/satisfy/satisfy.html">
      SATISFY</a>,
      a FORTRAN77 program which
      demonstrates, for a particular circuit, an exhaustive search
      for solutions of the circuit satisfiability problem.
    </p>

    <p>
      <a href = "../../f77_src/subset/subset.html">
      SUBSET</a>,
      a FORTRAN77 library which
      enumerates, generates, ranks and unranks combinatorial objects
      including combinations, partitions, subsets, index sets, and trees.
    </p>

    <p>
      <a href = "../../f77_src/subset_sum/subset_sum.html">
      SUBSET_SUM</a>,
      a FORTRAN77 library which
      seeks solutions of the subset sum problem.
    </p>

    <p>
      <a href = "../../m_src/subset_sum_tasks/subset_sum_tasks.html">
      SUBSET_SUM_TASKS</a>,
      a MATLAB program which
      runs in parallel, seeking solutions of the subset sum problem.
      Instructions are available on how to run the job, via MATLAB's BATCH facility,
      on a remote system such as Virginia Tech's ITHACA cluster.
    </p>

    <h3 align = "center">
      Reference:
    </h3>

    <p>
      <ol>
        <li>
          Alexander Dewdney,<br>
          The Turing Omnibus,<br>
          Freeman, 1989,<br>
          ISBN13: 9780716781547,<br>
          LC: QA76.D45.
        </li>
        <li>
          Brian Hayes,<br>
          The Easiest Hard Problem,<br>
          American Scientist,<br>
          Volume 90, Number 2, March-April 2002, pages 113-117.
        </li>
        <li>
          Silvano Martello, Paolo Toth,<br>
          Knapsack Problems: Algorithms and Computer Implementations,<br>
          Wiley, 1990,<br>
          ISBN: 0-471-92420-2,<br>
          LC: QA267.7.M37.
        </li>
      </ol>
    </p>

    <h3 align = "center">
      Source Code:
    </h3>

    <p>
      <ul>
        <li>
          <a href = "partition_problem.f">partition_problem.f</a>, the source code.
        </li>
        <li>
          <a href = "partition_problem.sh">partition_problem.sh</a>,
          BASH commands to compile the source code.
        </li>
      </ul>
    </p>

    <h3 align = "center">
      Examples and Tests:
    </h3>

    <p>
      <ul>
        <li>
          <a href = "partition_problem_prb.f">partition_problem_prb.f</a>,
          a sample calling program.
        </li>
        <li>
          <a href = "partition_problem_prb.sh">partition_problem_prb.sh</a>,
          BASH commands to compile and run the sample program.
        </li>
        <li>
          <a href = "partition_problem_prb_output.txt">partition_problem_prb_output.txt</a>,
          the output file.
        </li>
      </ul>
    </p>

    <h3 align = "center">
      List of Routines:
    </h3>

    <p>
      <ul>
        <li>
          <b>I4VEC_COPY</b> copies an I4VEC.
        </li>
        <li>
          <b>I4VEC_DOT_PRODUCT</b> computes the dot product of two I4VEC's.
        </li>
        <li>
          <b>I4VEC_SUM</b> returns the sum of the entries of an I4VEC.
        </li>
        <li>
          <b>PARTITION_BRUTE</b> approaches the partition problem using brute force.
        </li>
        <li>
          <b>PARTITION_COUNT</b> counts the solutions to a partition problem.
        </li>
        <li>
          <b>SUBSET_NEXT</b> computes the subset lexicographic successor.
        </li>
        <li>
          <b>TIMESTAMP</b> prints out the current YMDHMS date as a timestamp.
        </li>
      </ul>
    </p>

    <p>
      You can go up one level to <a href = "../f77_src.html">
      the FORTRAN77 source codes</a>.
    </p>

    <hr>

    <i>
      Last revised on 10 May 2012.
    </i>

    <!-- John Burkardt -->

  </body>

  <!-- Initial HTML skeleton created by HTMLINDEX. -->

</html>
