RE: Re: Need your help again to clarify output, how to get reduced variables & value ?

Messages in this topic (5) Reply (via web post) | Start a new topic

.

Martin,
The first page of google “Modeling Sudoku with Integer Programs “
has several nice hits. I like these 3.
www.math.nus.edu.sg/~matkbn/Sudoku-IP.ppt
www.cofc.edu/~langvillea/Sudoku/sudoku2.pdf
http://opus.kobv.de/zib/volltexte/2005/884/pdf/ZR-05-51.pdf

The first shows a pure binary IP formulation and some generalizations of the
problem.
The second is an analysis for a class project. It mentions finding all
solutions.
The third gives a very compact zimpl expression for the constraints. Zimpl
can be used directly in lp_solve via XLI_ZIMPL.

Maybe for your problem you can replace the =0 constraints involving small
integers with a similar trick for binaries labeling them. That leaves the
LP matrix with only 0,1 coefficients. It might be unimodular or lucky and
the relaxed solution might have only integer values and you are done
immediately with no Branch and Bound.

William
________________________________________
From: lp_solve%40yahoogroups.com">lp_solveyahoogroups.com [mailto: lp_solve%40yahoogroups.com">lp_solveyahoogroups.com] On Behalf
Of William H. Patton
Sent: Sunday, June 15, 2008 1:33 PM
To: lp_solve%40yahoogroups.com">lp_solveyahoogroups.com
Subject: RE: [lp_solve] Re: Need your help again to clarify output, how to
get reduced variables & value ?

Here is a nice short description of some B&B heuristics that help on Sudoku.

http://artige.com/SSolver.htm#BG
 
 
,___

Messages in this topic (6) Reply (via web post) | Start a new topic

.