Re: [Help-glpk] order restrictions

[Robbie Morrison]

Hi Patrik

------------------------------------------------------------
To:           Andrew Makhorin <address@hidden>
Subject:      Re: [Help-glpk] order restrictions
From:         Patrik Dufresne <address@hidden>
Date:         Thu, 1 Nov 2012 10:54:13 -0400
------------------------------------------------------------

> I want to try the minisat option with glpsol, but it's
> not available in my version of glpsol provided by
> debian.
>
>   $ glpsol --version
>   GLPSOL: GLPK LP/MIP Solver, v4.45
>
> Is it a 4.47 feature ?

Yes.

>From http://en.wikibooks.org/wiki/GLPK/Using_GLPSOL#Options

  Options for CNF-SAT satisfiability problems:

  --cnf filename     read CNF-SAT problem in DIMACS format from filename
  --wcnf filename    write CNF-SAT problem in DIMACS format to filename
  --minisat          solve CNF-SAT problem with glp_infeas1 solver
  --objbnd bound     add inequality bounds to 0-1 feasibility problem
(assumes --minisat)

>From the release notes (part only):

  The new API routine glp_intfeas1 was added to the
  package.  This routine is a tentative implementation
  of the integer (0-1) feasibility solver based on the
  CNF-SAT solver (which currently is MiniSat). It may
  be used in the same way as glp_intopt to find either
  any integer feasible solution or a solution, for
  which the objective function is not worse than the
  specified value. Detailed description of this routine
  can be found in the document "CNF Satisfiability
  Problem", which is included in the distribution (see
  doc/cnfsat.pdf).

  The following two options were added to glpsol:

  --minisat       translate 0-1 feasibility problem to
                  CNF-SAT problem and solve it with
                  glp_intfeas1/MiniSat (if the problem
                  instance is already in CNF-SAT
                  format, no translation is performed)

  --objbnd bound  add inequality obj <= bound
                  (minimization) or obj >= bound
                  (maximization) to 0-1 feasibility
                  problem (this option assumes
                  --minisat)

  The paint-by-numbers puzzle model (pbn.mod) included
  in the distribution is a nice example of the 0-1
  feasibility problem, which can be efficiently solved
  with glp_intfeas1/MiniSat. This model along with a
  brief instruction (pbn.pdf) and benchmark examples
  from <webpbn.com> encoded in GNU MathProg (*.dat)
  can be found in subdirectory examples/pbn/.

Robbie
---
Robbie Morrison
PhD student -- policy-oriented energy system simulation
Institute for Energy Engineering (IET)
Technical University of Berlin (TU-Berlin), Germany
University email (redirected) : address@hidden
Webmail (preferred)           : address@hidden
[from Webmail client]