NEOS - Integer Programming
https://neos-guide.org/taxonomy/term/10
enRubik's Cube Solver
https://neos-guide.org/content/rubikscube
<div class="field field-name-body field-type-text-with-summary field-label-hidden view-mode-rss"><div class="field-items"><div class="field-item even" property="content:encoded"><style>
<!--/*--><![CDATA[/* ><!--*/
h3 { text-decoration: underline; font-size: 1.5em; text-transform: uppercase; }
.indent { padding: 10px; }
.center-block { margin: auto; width: 80%; }
pre { padding: 2em; background-color: #eee; }
.rspace{ padding-right: 2em; }
/*--><!]]>*/
</style><script src="https://ajax.googleapis.com/ajax/libs/jquery/2.2.4/jquery.min.js"></script><script src="https://neos-server.org/neos/js/neos.js"></script><script type="text/javascript">
<!--//--><![CDATA[// ><!--
var gams_model;
$(function () {
$.get("/sites/default/files/guide_rubiks.gms", function (data) {
gams_model = data;
});
});
function resetInput() {
document.getElementById('email_ad').value = '';
document.getElementById('rubiks_cube').value = '';
document.getElementById('job_num').value = '';
document.getElementById('job_pass').value = '';
}
function createJobXML(category, solver) {
var email_address = document.getElementById('email_ad').value;
var xmlHead = "<document>\n<category>" + category +
"<\/category>\n<solver>" + solver + "<\/solver><inputMethod>GAMS<\/inputMethod>\n" +
"<email>" + email_address + "<\/email>\n<model><![CDATA[";
var xmlTail = "\]\]><\/model>\n<options>feasopt 1<\/options>\n<\/document>";
var jobXML = xmlHead + document.getElementById('rubiks_cube').value + "\n" + gams_model + xmlTail;
return(jobXML);
}
function solveCube() {
var job_xml = createJobXML('milp', 'CPLEX');
NEOSSubmitString(job_xml, function (submit) {
if (submit.error)
throw(submit.error);
printResults(submit.job_number, submit.password)
})
}
function printResults(number,pass) {
document.getElementById("job_num").value = number;
document.getElementById("job_pass").value = pass;
}
//--><!]]>
</script><h3>Problem Description</h3>
<p>The Rubik's cube is a three-dimensional combination puzzle invented by Emo Rubik in 1974. The physical version of the Rubik's cube consists of small blocks that rotate on a central axis. Classically, the puzzle has six faces, each with nine blocks arranged in a $3 \times 3$ square. More complicated versions of the Rubik's cube exist with $N \times N$ faces. Each block has a colored sticker in either white, red, blue, orange, green, or yellow. To solve the puzzle, the player must rotate one strip of blocks at a time until each of the six faces of the cube is populated by a single color.</p>
<p>Every year, dozens of Rubik's cube competitions are held around the world in which the objective is to solve the puzzle as fast as possible. A number of easily memorizable algorithms exists that allow players to solve any Rubik's cube configuration. However, solving these puzzles is not just of interest to players. There is also much academic interest in designing efficient algorithms to solve a Rubik's cube in as few turns as possible.</p>
<p>The goal of this case study is to present a mixed-integer program that can solve an $N \times N \times N$ Rubik's cube from any starting configuration.</p>
<h3>Methodology</h3>
<p>Given any $N \times N \times N$ Rubik's cube, a unique set of $m$ moves exists. It is important to note that moves are a sequence that involves many position-to-position mappings. We define moves to be quarter-turns of a block strip in either direction; half-turns require two moves.</p>
<div class="center-block"><figure><img src="/sites/default/files/rubiks-valid-move.png" width="65%" height="65%" /></figure></div>
<p>Consider the two-dimensional representation of a standard $3 \times 3 \times 3$ Rubik's cube in Figure (1). In this figure, a rotation of face 6 of the cube also rotates a row in the four neighboring faces. It is easy to verify that all moves can be exhausted by taking any face and considering all row- and column-wise turns, and then taking one vertically (horizontally) adjacent face and considering all row-wise (column-wise) turns. With the standard $3 \times 3 \times 3$ cube, this yields 18 unique moves. More generally, this yields $6N$ unique moves for an $N \times N \times N$ cube.</p>
<h3>Notation</h3>
<p>Notation used to define the model are introduced below.</p>
<ul><li>$N$ denotes the number of faces on the Rubik's cube (for this case study, we assume $N = 3$).
</li><li>The faces of the Rubik's cube are indexed by $f = 1, \ldots, 6$.</li>
<li>Let $r, c = 1, \ldots, N$ index the rows and columns, respectively, of each face. The tuple $(f,r,c)$ is a fixed position on the Rubik's cube.</li>
<li>The function $x(f,r,c,t)$ defines the color of the block in position $(f,r,c)$ on turn $t$. As there are six faces, $x(f,r,c,t)$ can take on values one through six, representing the six colors of the cube.</li>
<li>Let $A(f,r,c)$ denote the set of moves associated with position $(f,r,c)$; that is, the set of moves that involve the block in position $(f,r,c)$ moving, and consequently being replaced by a new block. Thus if move $m \in A(f,r,c)$ is made on turn $t$, $x(f,r,c,t) = x(f_m, r_m, c_m, t+1)$, where $(f_m,r_m,c_m)$ is the new position of the block originally occupying position $(f,r,c)$ after move $m$.</li>
</ul><h3>Computing all possible moves for Rubik's cube</h3>
<p>
Given our framework, a set of heuristics can be devised that generates all moves automatically for any $N \times N \times N$ Rubik's cube. Figure (2) is a snapshot of the code that produces the first $3$ moves on a $3 \times 3 \times 3$ cube.</p>
<div class="center-block"><figure><img src="/sites/default/files/rubiks-possible-moves.png" width="75%" height="65%" /></figure></div>
<p>Variable $p$ indexes either the rows or the columns. Let's consider the case when $p = 1$. <code>lm(m,fi,ri,ci,fj,rj,cj)</code> indicates that move $m$ is associated with transfering the block in the initial position $(f_i,r_i,c_i)$ to the terminal position $(f_j,r_j,c_j)$.</p>
<ul><li>The first condition defining the set <code>ord(m) eq ord(p)</code> assigns this mapping to the first ($p = 1)$ move.</li>
<li>The second condition <code>ord(p) eq ord(ri)</code> says that we are concerned with moving blocks in the first row of face 2.</li>
<li>The third condition <code>ord(ri) eq (cubeSize - ord(cj)+1)</code> says that the last column of face 5 is the terminal location of the blocks from face 2</li>
<li>The last condition <code>ord(rj) eq ord(ci)</code> ensures that the row index of the initial position in face 2 matches the column index in the terminal position in face 5.</li>
</ul><p>The rest of the code can be interpreted in the similar fashion. Combining all of these generates all moves displayed in Figure (1b). Counterclockwise quarter-turns move blocks from face 2 to face 5, from face 5 to face 4, from face 4 to face 1, and from face 1 to face 2. The fifth line of the code also defines the rotation of blocks within face 6 (when $p = 1$). The last line of the code describes the actions within face 3 (when $p = 3$). By turning the "middle" row of the cube, faces 3 and 6 do not change, but blocks within the other faces still rotate (when $p = 2$).
</p>
<p>
Given all possible legal moves for a Rubik's cube, the set of move associations $A(f,r,c)$ is constructed by computing within GAMS: <code>bm_assc(m,f,r,c)=YES</code>, which is equivalent to $m \in A(f,r,c)$.
</p>
<h3>The Rubik's Cube Model</h3>
<p>Assuming that all moves and move associations can be generated, we now consider the solution of a Rubik's cube. Given any $N \times N \times N$ Rubik's cube, we consider the following model:<br />
\begin{align}<br />
\min&\qquad\sum_t\sum_m y(m,t)\cdot t \\[5pt]<br />
\text{subject to}&\qquad \sum_m y(m,t)\le 1\\[5pt]<br />
&\qquad x(f,r,c,t)-M(1-y(m,t))\le x(f_{m},r_{m},c_{m},t+1)\\[5pt]<br />
&\qquad x(f,r,c,t)+M(1-y(m,t))\ge x(f_{m},r_{m},c_{m},t+1)\\[5pt]<br />
&\qquad x(f,r,c,t)-M\sum_{m\in A(f,r,c)}y(m,t)\le x(f,r,c,t+1)\\[5pt]<br />
&\qquad x(f,r,c,t)+M\sum_{m\in A(f,r,c)}y(m,t)\ge x(f,r,c,t+1)\\[5pt]<br />
&\qquad \sum_n z(f,r,c,t,n)\cdot n=x(f,r,c,t)\\[5pt]<br />
&\qquad \sum_n z(f,r,c,t,n)=1\\[5pt]<br />
&\qquad \sum_r\sum_c z(f,r,c,t,n)\ge N^2\cdot v(f,t,n)\\[5pt]<br />
&\qquad \sum_r\sum_c z(f,r,c,t,n)+1\le N^2+v(f,t,n)\\[5pt]<br />
&\qquad \sum_f\sum_n v(f,t,n)\ge 6\cdot d(t)\\[5pt]<br />
&\qquad \sum_f\sum_n v(f,t,n)\le 5+d(t)\\[5pt]<br />
&\qquad \sum_t d(t)\ge 1<br />
\end{align}<br />
The function $x(f,r,c,t)$, which indicates the color of the block in position $(f,r,c)$ on turn $t$, takes on integer values one through six; all remaining variables are binary:
</p><ul><li>$y(m,t)$ indicates whether move $m$ is made on turn $t$</li>
<li>$z(f,r,c,t,n)$ indicates whether $x(f,r,c,t) = n$</li>
<li>$v(f,t,n)$ indicates whether every block on face $f$ is color $n$ on turn $t$; and</li>
<li>$d(t)$ indicates whether the Rubik's cube is solved by turn $t$.</li>
</ul><p>The model minimizes an objective value that is increasing in the number of turns taken and increasing in the time at which a turn is made. Thus, the model aims to solve the Rubik's cube in as few steps as possible. The model constraints are described below.<br /><span class="indent"><b>Constraint 1</b>: Constraint (1) ensures that no more than one move is made per turn.</span><br /><span class="indent"><b>Constraints 2 and 3</b>: Assume $M$ is chosen such that $M \ge 5$. Constraints (2) and (3) together ensure that $x(f,r,c,t+1)$ is between $x(f,r,c,t) - M$ and $x(f,r,c,t) + M$. Consider a move $m \in A(f,r,c)$. If $y(m,t) = 0$ (move $m$ is not made on turn $t$), then the constraints leave $x(f,r,c,t+1)$ unbounded. If $y(m,t) = 1$, then the constraints ensure that $x(f,r,c,t) = x(f_m,r_m,c_m,t+1)$ so that the block in position $(f,r,c)$ on turn $t$ is moved to position $(f_m,r_m,c_m)$ on turn $t+1$.</span><br /><span class="indent"><b>Constraints 4 and 5</b>: If $y(m,t) = 0$ for all $m \in A(f,r,c)$, then the constraints force $x(f,r,c,t) = x(f,r,c,t+1)$; that is, when no move is associated with position $(f,r,c)$ is made, then the block in position $(f,r,c)$ does not move. If $y(m,t) = 1$ for some $m \in A(f,r,c)$, then the constraints leave $x(f,r,c,t)$ unbounded. When combined with constraints (2) and (3), the equations ensure that if a move $m \in A(f,r,c)$ is made on turn $t$, then $x(f,r,c,t) = x(f_m,r_m,c_m,t+1)$; otherwise, if $m \notin A(f,r,c)$ is not made on turn $t$, then $x(f,r,c,t) = x(f,r,c,t+1)$.</span><br /><span class="indent"><b>Constraints 6 and 7</b>: Constraints (6) and (7) guarantee that $z(f,r,c,t,n) = 1$ if and only if $x(f,r,c,t) = n$.</span><br /><span class="indent"><b>Constraints 8 and 9</b>: Constraints (8) and (9) define bounds on the number of blocks on face $f$ with color $n$ on turn $t$. Thus, if $v(f,t,n) = 1$, then all blocks on face $f$ are color $n$ on turn $t$.</span><br /><span class="indent"><b>Constraints 10 and 11</b>: The left-hand side of constraints (10) and (11) is equal to one if face $f$ is complete, that is, if all blocks on face $f$ have the same color, and zero, otherwise. The constraints state that the cube is solved ($d(t) = 1$) if all faces are complete.</span><br /><span class="indent"><b>Constraint 12</b>: Constraint (12) states that the cube must be solved (i.e., $d(t) = 1$ for some $t$).</span>
</p>
<p>
The GAMS model is available for download <a href="https://neos-guide.org/sites/default/files/rubiks_original.gms">here</a>.
</p>
<hr /><h3>Some Results</h3>
<p>Figure (4) displays the results for the $3 \times 3 \times 3$ cube defined in <code>rubiks3x3.dat</code>. The cube is sovled in four turns. In the first turn, Figure (4a) to (4b), the third row of the front face is quarter-turned to the left. In the second turn (4b) to (4c), the front face is rotated counterclockwise 90 degrees. In the third turn (4c) to (4d), the third row of the front face is quarter-turned to the right. Finally, in the last turn (4d) to (4e), the second row of the front face is quarter-turned to the left.</p>
<div class="center-block"><figure><img src="/sites/default/files/rubiks-fig4.png" width="45%" height="45%" /></figure></div>
<p>Figures (3) and (5) demonstrate the model on Rubik's cubes of size $2\times 2\times 2$ with 6 shuffles and $4\times 4\times 4$ with 4 shuffles.</p>
<div class="center-block"><figure><img src="/sites/default/files/rubiks-fig3.png" width="45%" height="45%" /><img src="/sites/default/files/rubiks-fig5.png" width="45%" height="45%" /></figure></div>
<h3>Limitations</h3>
<p>The number of turns allotted $T$ (length of set $t$) must be sufficiently large so that the model is solvable. For more complex cubes, larger values of $T$ are needed to maintain model feasibility. It can be verified that for an $N \times N \times N$ cube, the model can be solved for $6T(7N^2 + N + ^6) + T$ variables. For a standard cube with $N = 3$, this amounts to 433 variables per turn allotted. As a result, even for cubes with a single shuffle, larger values of $T$ increase runtime substantially. Ideally, $T$ should be the smallest value such that the model is solvable.</p>
<h3>Supporting Scripts</h3>
<p>The following Matlab scripts utilize <a href="http://www.mathworks.com/matlabcentral/fileexchange/31672-rubik-s-cube-simulator-and-solver">Joren Heit's Rubik's Cube Simulator and Solver</a> available for download from Mathworks.</p>
<p>To generate an NxNxN Rubik's cube in the appropriate format for GAMS, run <code>generateRubiks.m</code>. To create the images for a given solution to a Rubik's cube, use <code>plotRubiksCube.m</code>.</p>
<div class="center-block">
<pre>
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Purpose: Creates data for NxNxN Rubik's cubes that can be fed into GAMS.
%
% Dependencies: Joren Heit's Rubik's Cube Simulator and Solver is used
% to generate a valid, random Rubik's Cube. This work can be found here:
% http://www.mathworks.com/matlabcentral/fileexchange/31672-rubik-s-cube-simulator-and-solver
%
% Inputs:
% -sizeCube: The number of blocks to be in each row and column.
% Ex: If sizeCube = 3, a 3x3x3 Rubik's Cube will be generated.
% -shuffleSteps: The number of random steps used to shuffle the cube.
% -turns: The number of turns you want to give the mixed integer
% program to solve the Rubik's cube.
% Note: If you are choosing a lot of shuffle steps, you need
% a high value of t, or else you risk infeasability.
% -directory: The directory where you want your output file to be
% stored. It's advisable to save your output file where you
% run your GAMS files.
% -fileName: Desired name of output file. This fileName will be concaten-
% ated with an n x n suffix.
% Ex: If fileName = rubiks and sizeCube = 3, the output file
% will be titled rubiks3x3.dat.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function generateRubiksData(sizeCube,shuffleSteps,turns,directory,fileName)
addpath Digital_Rubiks_Cube/src/;
% Generate valid, random Rubik's Cube.
generatedCube = rubgen(sizeCube,shuffleSteps);
rubplot(generatedCube);
% Create file suffix.
fileNameSuffix = strcat(num2str(sizeCube),'x',num2str(sizeCube));
% Output it to a file that GAMS can read.
fid = fopen(strcat(directory,fileName,fileNameSuffix,'.dat'),'w');
fprintf(fid,'sets\n');
fprintf(fid,'\tf \"faces\" / f1 * f6 /\n');
fprintf(fid,'\tr \"rows\" / r1 * r%d /\n',sizeCube);
fprintf(fid,'\tc \"columns\" / c1 * c%d /\n',sizeCube);
fprintf(fid,'\tm \"moves\" / m1 * m%d /\n',sizeCube*6);
fprintf(fid,'\tt \"turns\" / t1 * t%d /\n',turns);
fprintf(fid,'\tn \"color\" / c1 * c6 /;\n\n');
fprintf(fid,'scalar\n');
fprintf(fid,'\tcubeSize \"size of cube\" / %d /;\n\n',sizeCube);
fprintf(fid,'parameters\n');
fprintf(fid,'\tinitial_x(f,r,c) /\n');
% The faces of the generated cube must be translated to match the way
% they are expected to be input in the GAMS code.
trans = [3 5 6 1 2 4];
for i = 1:6
for j = 1:sizeCube
for k = 1:sizeCube
if (i == 6 & j == sizeCube & k == sizeCube)
fprintf(fid,'\tf%d.r%d.c%d %d /;\n',trans(i),j,k,generatedCube(j,k,i));
else
fprintf(fid,'\tf%d.r%d.c%d %d\n',trans(i),j,k,generatedCube(j,k,i));
end
end
end
end
fclose(fid);
end
</pre></div>
<div class="center-block">
<pre>
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Purpose: Plot GAMS output and save it to specified outDirName.
%
% Dependencies: Joren Heit's Rubik's Cube Simulator and Solver is used
% to generate a valid, random Rubik's Cube. This work can be found here:
% http://www.mathworks.com/matlabcentral/fileexchange/31672-rubik-s-cube-simulator-and-solver
%
% Inputs:
% -solFile: The output file produced by GAMS.
% -sizeCube: The number of blocks to be in each row and column.
% Ex: If sizeCube = 3, a 3 x 3 Rubik's Cube will be generated.
% -outDirName: What you would like the output folder in the working
% directory to be called. For example, if outDirName =
% rubiks3x3plots, you can find your results in a directory
% called rubiks3x3plots in the working directory.
%
% Outputs: A directory called outDirName in which there will be images for
% all steps of the solution.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function plotResults(solFile,sizeCube,outDirName)
addpath Digital_Rubiks_Cube/src/;
fid = fopen(solFile);
tline = fgetl(fid);
f1 = [];
f2 = [];
f3 = [];
f4 = [];
f5 = [];
f6 = [];
% Collect the solutions into 6 matrices, one for each face.
while ischar(tline)
formatSpec = ' %f %f %f';
sizeFace = [sizeCube sizeCube];
face = fscanf(fid,formatSpec,sizeFace);
if (length(findstr(tline,'f1')) > 0)
f4 = [f4 face'];
elseif (length(findstr(tline,'f2')) > 0)
f5 = [f5 face'];
elseif (length(findstr(tline,'f3')) > 0)
f1 = [f1 face'];
elseif (length(findstr(tline,'f4')) > 0)
f6 = [f6 face'];
elseif (length(findstr(tline,'f5')) > 0)
f2 = [f2 face'];
elseif (length(findstr(tline,'f6')) > 0)
f3 = [f3 face'];
end
tline = fgetl(fid);
end
% Generate a cube as a base.
graphCube = rubgen(sizeCube,0);
% Create the name base of the output file names.
nameBase = strcat(num2str(sizeCube),'x',num2str(sizeCube),'c');
% Determine how many plots will need to be made.
plots = size(f1,2)/sizeCube;
mkdir(outDirName);
% Save each plot to the specified directory.
for i=1:plots
fileName = strcat(nameBase,num2str(i));
graphCube(:,:,1) = f1(:,1:sizeCube);
graphCube(:,:,2) = f2(:,1:sizeCube);
graphCube(:,:,3) = f3(:,1:sizeCube);
graphCube(:,:,4) = f4(:,1:sizeCube);
graphCube(:,:,5) = f5(:,1:sizeCube);
graphCube(:,:,6) = f6(:,1:sizeCube);
f1 = f1(:,sizeCube+1:size(f1,2));
f2 = f2(:,sizeCube+1:size(f2,2));
f3 = f3(:,sizeCube+1:size(f3,2));
f4 = f4(:,sizeCube+1:size(f4,2));
f5 = f5(:,sizeCube+1:size(f5,2));
f6 = f6(:,sizeCube+1:size(f6,2));
figure1 = figure;
rubplot(graphCube);
set(gca,'position',[0 0 1 1],'units','normalized');
saveas(figure1,[strcat(outDirName,'/') fileName '.jpg']);
end
fclose(fid);
end
</pre></div>
<!--
<h3><p>Solving the Rubik's Cube</h3>
<p>Copy and paste the Rubik's cube configuration into the area below. Click "Solve Rubik's Cube" to send the GAMS model to the NEOS server. This demo can take a long time depending on the type of cube submitted; therefore, an email will be sent to you upon job completion. You will then be able to download an output file named 'results.txt' from the NEOS server that will have a turn-by-turn solution to your Rubik's cube. The job number and password will also be displayed below after submission.</p>
<p style="padding: 0 2em 2em 1em;"><textarea name="rubiks_cube" id="rubiks_cube" rows=15 cols=120 placeholder="Copy Rubik's cube coordinates here"></textarea><br />
<span class="rspace"><input id="email_ad" type="text" placeholder="Email address" value="" size=20 class="input" required></span><span class="rspace"><button id="btnSolve" type="button" onclick="solveCube();">Solve Rubik's Cube</button></span><button id="btnDefault" type="reset" onclick="resetInput();">Clear</button><br />
<span class="rspace"><input type="text" id="job_num" value="" placeholder="Job number" readonly></span><input id="job_pass" type="text" value="" placeholder="Job password" readonly></p>
<p>-->
</div></div></div><section class="field field-name-field-method field-type-taxonomy-term-reference field-label-above view-mode-rss"><h2 class="field-label">Optimization Category (Linear Programing, Integer, MIP and etc.): </h2><ul class="field-items"><li class="field-item even"><a href="/taxonomy/term/11" typeof="skos:Concept" property="rdfs:label skos:prefLabel" datatype="">Discrete and Integer Optimization</a></li><li class="field-item odd"><a href="/taxonomy/term/10" typeof="skos:Concept" property="rdfs:label skos:prefLabel" datatype="">Integer Programming</a></li></ul></section><section class="field field-name-field-image field-type-image field-label-above view-mode-rss"><h2 class="field-label">Image: </h2><div class="field-items"><figure class="clearfix field-item even"><img typeof="foaf:Image" class="image-style-thumbnail" src="https://neos-guide.org/sites/default/files/styles/thumbnail/public/rubiks-valid-move.png?itok=WofhYuul" width="100" height="47" alt="" /></figure><figure class="clearfix field-item odd"><img typeof="foaf:Image" class="image-style-thumbnail" src="https://neos-guide.org/sites/default/files/styles/thumbnail/public/rubiks-possible-moves.png?itok=UIvjxGuk" width="100" height="57" alt="" /></figure><figure class="clearfix field-item even"><img typeof="foaf:Image" class="image-style-thumbnail" src="https://neos-guide.org/sites/default/files/styles/thumbnail/public/rubiks-fig3.png?itok=-sQCH1SB" width="100" height="93" alt="" /></figure><figure class="clearfix field-item odd"><img typeof="foaf:Image" class="image-style-thumbnail" src="https://neos-guide.org/sites/default/files/styles/thumbnail/public/rubiks-fig4.png?itok=s93UZWws" width="100" height="95" alt="" /></figure><figure class="clearfix field-item even"><img typeof="foaf:Image" class="image-style-thumbnail" src="https://neos-guide.org/sites/default/files/styles/thumbnail/public/rubiks-fig5.png?itok=4bzJZAV7" width="100" height="94" alt="" /></figure></div></section><section class="field field-name-field-file field-type-file field-label-above view-mode-rss"><h2 class="field-label">File: </h2><div class="field-items"><div class="field-item even"><span class="file"><img class="file-icon" alt="Binary Data" title="application/octet-stream" src="/modules/file/icons/application-octet-stream.png" /> <a href="https://neos-guide.org/sites/default/files/rubiks_original.gms" type="application/octet-stream; length=10720">rubiks_original.gms</a></span></div></div></section>Sun, 10 Dec 2017 21:41:16 +0000ewong564 at https://neos-guide.orghttps://neos-guide.org/content/rubikscube#commentsDiscrete Optimization
https://neos-guide.org/content/discrete-optimization
<div class="field field-name-body field-type-text-with-summary field-label-hidden view-mode-rss"><div class="field-items"><div class="field-item even" property="content:encoded"><p>In <b>discrete optimization</b>, some or all of the variables in a model are required to belong to a <i>discrete set</i>; this is in contrast to <a href="/content/continuous-optimization">continuous optimization</a> in which the variables are allowed to take on any value within a range of values. Here, we consider two branches of discrete optimization. In <b><a href="/content/integer-linear-programming">integer programming</a></b>, the discrete set is a subset of integers. In <b><a href="/content/combinatorial-optimization">combinatorial optimization</a></b>, the discrete set is a set of objects, or combinatorial structures, such as assignments, combinations, routes, schedules, or sequences. </p>
<!--
[mention the broad range of applications]
--><p>
Go back to the <a href="/optimization-tree">Optimization Tree</a></p>
<ul><li><a href="/content/integer-linear-programming">Integer Linear Programming</a>
<ul><li><a href="/content/integer-linear-programming#intro">Basic Concepts</a></li>
<li><a href="/content/integer-linear-programming#software">Software Resources</a></li>
<li><a href="/content/integer-linear-programming#test_probs">Test Problems</a></li>
<li><a href="/content/integer-linear-programming#case_studies">Case Studies</a></li>
<li><a href="/content/integer-linear-programming#references">References</a></li>
</ul></li>
<li><a href="/content/combinatorial-optimization">Combinatorial Optimization</a>
<ul><li><a href="/content/combinatorial-optimization#intro">Basic Concepts</a></li>
<li><a href="/content/combinatorial-optimization#examples">Examples</a></li>
<!--
<li><p>Software Resources (include solvers on the NEOS Server and the info from the Software Guide)</li>
<li>Test Problems (TSPLIB, VRP, others)</li>
<li>Case Studies</li>
<p>-->
<li><a href="/content/combinatorial-optimization#references">References</a></li>
</ul></li>
</ul></div></div></div>Thu, 16 Jan 2014 15:48:05 +0000rberger407 at https://neos-guide.orghttps://neos-guide.org/content/discrete-optimization#commentsDetermining Protein Structure
https://neos-guide.org/content/protein-structure
<div class="field field-name-body field-type-text-with-summary field-label-hidden view-mode-rss"><div class="field-items"><div class="field-item even" property="content:encoded"><!--
[[File:Gp120.jpg|frame| '''Envelope glycoprotein GP120''' [http://en.wikipedia.org/wiki/Gp120 GP120] is embedded on the surface of [http://en.wikipedia.org/wiki/HIV HIV] envelope. It attaches to the [http://en.wikipedia.org/wiki/CD4 CD4] receptors of [http://en.wikipedia.org/wiki/Helper_T_cell T helper cell], a type of [http://en.wikipedia.org/wiki/White_blood_cell white blood cells], facilitating entry of the HIV virus to the host cell. Fusion inhibitor drugs prevent GP120 from attaching itself to the T4 receptors of the T helper cells.]]
--><p><b>Summary</b>: </p>
<h3><a name="top" id="top">Case Study Contents</a></h3>
<ul><li><a href="#problem">Problem Statement</a></li>
<li><a href="#formulation">Mathematical Formulation</a></li>
<li><a href="/content/protein-demos">Interactive Demo</a></li>
<li><a href="#references">References</a></li>
</ul><h2><a name="introduction" id="introduction">Introduction</a></h2>
<p><a href="http://en.wikipedia.org/wiki/Protein">Proteins</a> are one of the major macro molecules that are present in all biological organisms. They engage into virtually every process within biological systems, such as catalyzing biochemical reactions, transporting and storing chemical compounds, signaling and translating the information from other proteins, maintaining the structures of biological components (e.g. cells, tissues), converting chemical energy into mechanical energy causing muscular movement, and generating immune responses to the harmful foreign bodies within the organism. The function that a protein assumes depends on its structure. Therefore, <a href="http://en.wikipedia.org/wiki/Biomolecular_structure#Structure_determination">protein structure determination</a> is of utmost importance for <a href="http://en.wikipedia.org/wiki/Drug_design">drug design</a> and <a href="http://en.wikipedia.org/wiki/Protein_design">protein design</a> studies. </p>
<div style="font-size:80%;"><img src="http://neos-dev-web.neos-server.org/class-archive/images/b/bd/Gp120.jpg" style="padding-bottom:0.5em;" /><br /><b>Envelope glycoprotein GP120</b> <a href="http://en.wikipedia.org/wiki/Gp120">GP120</a> is embedded on the surface of <a href="http://en.wikipedia.org/wiki/HIV">HIV</a> envelope. It attaches to the <a href="http://en.wikipedia.org/wiki/CD4">CD4</a> receptors of <a href="http://en.wikipedia.org/wiki/Helper_T_cell">T helper cell</a>, a type of <a href="http://en.wikipedia.org/wiki/White_blood_cell">white blood cells</a>, facilitating entry of the HIV virus to the host cell. Fusion inhibitor drugs prevent GP120 from attaching itself to the T4 receptors of the T helper cells.</div>
<p><a href="http://en.wikipedia.org/wiki/X-ray_crystallography">X-Ray Crystallography</a> and <a href="http://en.wikipedia.org/wiki/Protein_NMR">Nuclear Magnetic Resonance (NMR) spectroscopy</a> are the major experimental techniques for 3D protein structure determination. X-Ray Crystallography has been a more commonly used technique and obtaining protein structure information is a routine, highly automated procedure. Yet, it requires crystallization of the protein, which can take months. On the other hand, NMR Spectroscopy allows the study of a protein nearly under physiological conditions. However, it is hard to automate the NMR Spectroscopy experiments. An important bottleneck in NMR protein structure determination is the assignment of NMR spectrum peaks to the underlying atoms. This bottleneck can be represented as an assignment problem with the help of a homologous protein (protein with a similar structure as the protein under experimentation), which is called <a href="http://en.wikipedia.org/wiki/Structure-based_assignment">Structure Based Assignment (SBA)</a> problem.</p>
<div style="font-size:80%;"><img src="http://neos-dev-web.neos-server.org/class-archive/images/e/e3/1dNMRv3.gif" style="padding-bottom:0.5em;" /><br /><b>1D NMR Spectrum</b> The peaks in the spectrum are easily observable for the 1D NMR spectrum.</div>
<p>In this case study, we present two formulations from [1] and [2] for this problem and an <a href="/content/protein-demos">interactive demo</a> that solves the NMR SBA problem with the preferred formulation solver. The interactive demo uses the GAMS model representations for the formulations presented in the following sections.</p>
<h2><a name="problem" id="problem">Problem Statement</a></h2>
<p>The NMR SBA problem in [1], [2] and [3] is constructed by the Nuclear Vector Replacement (NVR) framework. The goal is to find a mapping between the set of peaks and the set of amino acids that minimizes the total mapping cost. Each peak-amino matching has an assignment probability, which is then converted into an assignment cost.</p>
<p>The available assignments are restricted by the <a href="http://en.wikipedia.org/wiki/Nuclear_Overhauser_effect">Nuclear Overhauser Effect</a> constraints that make the problem considerably harder to solve. In the NMR SBA problem, each peak pair has a binary relation called a NOE relation, i.e. for any given two peaks, they either have an NOE relation or not. The amino acids also have a similar binary relation, i.e. for any given two amino acids, the distance between the (amide) protons of the amino acids is either less than a threshold value (NTH) or not. The NOE constraints imply that for any given pair of peak - amino acid assignments (e.g. \(p_i \rightarrow a_i\) and \(p_j \rightarrow a_j\), if \(p_i \) and \(p_j \) have an NOE relation, then the distance of the protons of the amino acids that are assigned to those peaks, \(a_i\) and \(a_j\), must be less than the threshold value. </p>
<p>In the NOE constraints illustration figure, peaks 1 and 2 have an edge in between implying they have an NOE relation, and they are mapped to amino acids 1 and 2, respectively. Amino acids 1 and 2 also have an edge in between implying their distance from each other is under the threshold value. Hence, assigning peaks 1 and 2 to amino acids 1 and 2, respectively, is feasible. On the other hand, peaks 1 and 3 also have an NOE relation. However, the amino acids that are assigned to them, amino acids 1 and 4 do not have an edge in between, which means the distance between their amide protons is more than the threshold value. Thus, the assignments of peak 1 to amino acid 1 and peak 3 to amino acid 4 cause infeasibility.</p>
<div style="font-size:80%;"><img src="http://neos-dev-web.neos-server.org/class-archive/images/3/34/FeasibleAssignment.jpg" style="padding-bottom:0.5em;" /><br /><b>NOE constraints illustration</b> If there is an edge between two peaks, the amino acids that are assigned to them should have an edge between them.</div>
<h2><a name="formulation" id="formulation">Mathematical Formulation</a></h2>
<h3>Binary Integer Programming Formulation</h3>
<p>The NMR SBA problem can be formulated as a Binary Integer Program (BIP) as follows:</p>
<p><b>Parameters</b><br />
\(P\) = set of peaks<br />
\(A\) = set of amino acids<br />
\(NOE(i)\) = set of peaks that have an NOE relation with peak \(i\), \(\forall i \in P\)<br />
\(N\) = number of peaks to be assigned<br />
\(NTH\) = distance threshold for an NOE relation<br />
\(c_{ij}\) = cost of assigning peak \(i\) to amino acid \(j\), \(\forall i \in P\), \(\forall j \in A\)<br />
\(d_{kl}\) = distance between amide proteins of amino acids \(k\) and \(l\), \(\forall k, l \in A\)<br />
\(b_{kl} = \left\{ \begin{array}{ll}<br />
1 & \mbox{if \(d_{kl}\) < \(NTH\), \(\forall k, l \in A\)} \\<br />
0 & \mbox{otherwise}<br />
\end{array} \right. \)</p>
<p><b>Decision Variables</b><br />
\(x_{ij} = \left\{ \begin{array}{ll}<br />
1 & \mbox{if peak \(i\) is assigned to amino acid \(j\), \(\forall i \in P\), \(\forall j \in A\)} \\<br />
0 & \mbox{otherwise}<br />
\end{array} \right. \)</p>
<p><b>Model</b><br />
Minimize \( \sum_{i \in P} \sum_{j \in A} c_{ij} x_{ij} \)</p>
<p>subject to:<br />
\( \sum_{i \in P} x_{ij} \leq 1, \quad \forall j \in A\) </p>
<p>subject to:<br />
\( \sum_{i \in A}x_{ij} \leq 1, \quad \forall j \in P\)</p>
<p>subject to:<br />
\( \sum_{i \in P} \sum_{j \in A} x_{ij} = N\)</p>
<p>subject to:<br />
\( x_{ij}+x_{kl} \leq b_{jl}+1, \quad \forall j, l \in A, \forall i, k \in P, \forall k \in NOE(i)\)</p>
<p>subject to:<br />
\( x_{ij} \in \mathcal{B}, \forall i \in P, \forall j \in A\)</p>
<p>The first two constraints ensure that each NMR peak is assigned to at most one amino acid and, similarly, each amino acid is assigned to at most one peak. The third constraint determines the number of peak-amino acid assignments. Although \(N\) is usually equal to the number of peaks, in rare cases, mapping all of the peaks could be infeasible. In such cases, \(N\) allows us to obtain a partial solution. The next set of constraints are the NOE constraints. Finally, the last constraints restrict the variable only to take binary values.</p>
<h3>Mixed Integer Nonlinear Programming Formulation</h3>
<p>We can also model this problem as Mixed Integer Nonlinear Program (MINLP). In this formulation, instead of having a large number of constraints for NOE violations, we add a penalty term to the objective function for each violation. We choose the penalty term as the maximum non infinity assignment cost so that any solution with an NOE violation will be less favorable.</p>
<p><b>Parameters</b><br />
\(BD(j)=\{l \in A \ | \ d_{jl}\) < \(NTH \} \)</p>
<p><b>Decision Variables</b><br />
\(x_{ij} = \left\{ \begin{array}{ll}<br />
1 & \mbox{if peak \(i\) is assigned to amino acid \(j\), \(\forall i \in P\), \(\forall j \in A\)} \\<br />
0 & \mbox{otherwise}<br />
\end{array} \right. \)</p>
<p><b>Model</b><br />
Minimize \( \sum_{i \in P} \sum_{j \in A} c_{ij} x_{ij}+ \sum_{i \in P} \sum_{j \in A} \sum_{k \in NOE(i)} \sum_{l \in BD(j)} px_{ij}x_{kl} \) </p>
<p>subject to:<br />
\( \sum_{i \in P}x_{ij} \leq 1, \quad \forall j \in A \)</p>
<p>subject to:<br />
\( \sum_{i \in A} x_{ij} \leq 1, \quad \forall j \in P \)</p>
<p>subject to:<br />
\( \sum_{i \in P}\sum_{j \in A} x_{ij} = N \)</p>
<p>subject to:<br />
\( x_{ij} \in \mathcal{B}, \quad \forall i \in P, \forall j \in A\)</p>
<p>In the model above, the objective function minimizes the total score associated with the assignment of NMR peaks to amino acids and the additional score (penalty) resulting from NOE relation violations. The first and second sets of constraints guarantee that each amino acid is assigned to at most one NMR peak and each NMR peak is assigned to at most one amino acid. Similarly, we determine the number of peak-amino acid assignments by the third constraint, and finally, the last constraints make sure that all the variables are binary.</p>
<!--
<h2><p><a name="applet">Try the Applets!</a></h2>
<h3>Small Example Protein</h3>
<p>To explain the effect of NOE constraints on the assignments, we present here a toy example and an applet that allows a user to make her own assignments while blocking the infeasible assignment options through each step based on the data provided by the user.</p>
<p><b>Applet Instructions</b><br />
<i>Note that, unfortunately, the color changes are not observable on Mac OS based systems. Therefore, to get the full performance out of this applet, please run it on a Linux or Windows machines.</i></p>
<ul>
<li>"Select the data": The applet starts with default NOE and binary distance relations that comes from the NOE constraint illustration above. The user is allowed to change the input data.</li>
<li>"Hit the start button": In order to start making assignments, the user should click the "Start" button. This will change the color of boxes in the assignment panel from red to grey.</li>
<li>"Start assigning peaks to amino acids": The user can assign peak \(i\) to amino acid \(j\) by clicking the corresponding box in the assignment panel. As soon as an assignment is made, the infeasible assignments will turn into red and be blocked. The user will be able to choose her next assignment among the remaining feasible assignments. Also, the total cost of the assignments at each step is reported right next to the assignment panel. The goal is to assign each peak to an amino acid with the minimum cost possible. When the user reaches a feasible set of assignments (each peak is assigned to one of the amino acids), she can compare her result with the optimal solution by clicking the "Optimal" button.</li>
<li>"Optimal Button": The user can check the optimal solution by clicking the "Optimal" button. The boxes of the optimal assignments in the assignment panel will turn into green.</li>
<li>"Reset Button": By clicking this button, the applet returns to its initial state with the default data from NOE constraint illustration figure.</li>
</ul>
<p><applet code="org.neos.user_interfaces.ToyApplet" WIDTH="800" HEIGHT="400" ARCHIVE="http://neos-dev-web.neos-server.org/class-archive/images/b/b4/Signedneosv22.jar,http://neos-dev-1.neos-server.org/class-archive/commons-logging-1.1.jar,ws-commons-util-1.0.2.jar,xmlrpc-client-3.1.3.jar,xmlrpc-common-3.1.3.jar,jfreechart-1.0.13.jar,jcommon-1.0.16.jar"></applet></p>
<h3>Solver Applet</h3>
<p>This applet enables user to solve real NMR SBA problems with her preference of the problem formulation. The applet contains several default proteins from [2].</p>
<p><b>Applet Instructions</b></p>
<ul>
<li>"Choose the model": The user can choose to solve her problem with the BIP formulation or MINLP formulation by choosing the corresponding model from the first drop down list.</li>
<li>"Enter protein data": There are three panels to enter protein data for binary distances, NOE relations, and cost matrices. The values for each matrix should be comma separated for each row. The binary distance matrix and the NOE matrix are square matrices with the size of \(|P|\)> and \(|A|\), respectively. The cost matrix has \(|P|\) rows and \(|A|\) columns. The user can select default proteins from the second drop down list.</li>
<li>"Click on Solve": After entering the inputs correctly, the user should click on the "Solve" button. The results will appear in the last panel of the applet.</li>
<li>"Reset Button": Clicking the ''Reset'' button returns the applet to its initial state. In order to solve a new protein, user should click on this button.</li>
<li>"Default Proteins": The number of peaks and the number of amino acids of default proteins are as follows: Polyn with 31 and 31; 1GB1, 1PGB, 2BG1 with 55 and 55; FF2 with 55 and 80; 1UBI with 70 and 72. Depending on the size of the protein, it may take a couple of minutes for the solver to return the results.</li>
</ul>
<p><applet code="org.neos.user_interfaces.MainApplet" WIDTH="800" HEIGHT="800" ARCHIVE="http://neos-dev-web.neos-server.org/class-archive/images/c/ca/Signedneosv21.jar,commons-logging-1.1.jar,ws-commons-util-1.0.2.jar,xmlrpc-client-3.1.3.jar,xmlrpc-common-3.1.3.jar,jfreechart-1.0.13.jar,jcommon-1.0.16.jar"></applet></p>
<p>-->
<h2><a name="references" id="references">References</a></h2>
<p>[1] Apaydın et. al. 2010. Nvr-bip: Nuclear vector replacement using binary integer programming for NMR structure-based assignments. <i>The Computer Journal</i>.</p>
<p>[2] Cavuslar, G., Catay B., Apaydin M. S. 2011. A Tabu Search Approach for the NMR Protein Structure-Based Assignment Problem. Working Paper/Technical Report. Sabanci University. ID:SU_FENS_2011/0001</p>
<p>[3] Apaydin, M.S., Conitzer V., Donald B.R. 2008. Structure-based protein NMR assignments using native structural ensembles. <i>Journal of Biomolecular NMR</i>, 40(4):263–276.</p>
</div></div></div><section class="field field-name-field-method field-type-taxonomy-term-reference field-label-above view-mode-rss"><h2 class="field-label">Optimization Category (Linear Programing, Integer, MIP and etc.): </h2><ul class="field-items"><li class="field-item even"><a href="/taxonomy/term/10" typeof="skos:Concept" property="rdfs:label skos:prefLabel" datatype="">Integer Programming</a></li></ul></section>Wed, 25 Sep 2013 19:10:46 +0000rberger384 at https://neos-guide.orghttps://neos-guide.org/content/protein-structure#comments15 Puzzle
https://neos-guide.org/content/15puzzle
<div class="field field-name-body field-type-text-with-summary field-label-hidden view-mode-rss"><div class="field-items"><div class="field-item even" property="content:encoded"><p><b>Summary</b>: The 15 Puzzle consists of 15 squares numbered from 1 to 15 that are placed in a 4 by 4 box with one empty position. The objective of the puzzle is to reposition the squares by sliding them one at a time into a configuration with the numbers in order.</p>
<h3><a name="top" id="top">Case Study Contents</a></h3>
<ul><li><a href="#problem">Problem Statement</a></li>
<li><a href="/content/15puzzle-demo">Solve the Puzzle</a></li>
<li><a href="#formulation">Mathematical Formulation</a></li>
<li><a href="#gams">GAMS Model</a></li>
<li><a href="#references">Acknowledgments and References</a></li>
</ul><h2><a name="problem" id="problem">Problem Statement</a></h2>
<p>The 15 Puzzle is a sliding puzzle that consists of a 4 by 4 frame of numbered square tiles in an arbitrary ordering with one space. The objective of the puzzle is to place the tiles in order, as shown in the figure below, by making sliding moves that use the empty space.<br /><img src="http://www.neos-guide.org/sites/default/files/Fifteen_puzzle.png" height="100" width="100" /></p>
<!--
[[Image:fifteen_puzzle_unsolvable.png|thumb|right|An unsolvable state of the 15-puzzle]]
[add information on history, difficulty, algorithms, and connection to artificial intelligence]
--><!--
When we human beings attempt to solve this puzzle, we usually can only focus on getting one piece to its spot at a time, solving row by row to arrive at the final state. Naturally, computers are capable of looking at the puzzle from a higher level, considering the positions of every tile, and picking the best strategy to arrive at the final state with the least amount of steps. Nevertheless, it is still a daunting task as there are 16!/2 = 1.04613949 x 10<sup><p>13</sup> states for a 4x4 puzzle. There is a factor of 2 because half of permutations would result in an unsolvable state. In fact, if you were to swap any two numbered tiles from a solvable puzzle, the resulting state will be unsolvable [1]. This puzzle is typically solved using various heuristics including Manhattan distance, Walking distance, and Pattern databases. While efficient solvers using these heuristics exist, here, we formulate the 15-puzzle as an Integer Programming problem.<br />
-->
<h2>Solve the Puzzle</h2>
<p>Solve the <a href="/content/15puzzle-demo">15 Puzzle</a> yourself using the interactive demo.</p>
<h2><a name="formulation" id="formulation">Mathematical Formulation</a></h2>
<p>Here we investigate an optimization approach to solving the 15 Puzzle. In particular, we formulate an integer programming model in which the objective is to minimize the number of moves that the empty space makes in the process of positioning the numbered tiles in their respective positions. The constraints in the model define the allowable moves and track the positions of the empty space and the numbered tiles. The empty space (or blank tile) is allowed to move in four directions -- up, down, left, and right unless it is along an edge. When the blank tile is along an edge, one or two of the directions will be prohibited.</p>
<p><b>Sets</b><br />
\(I = \{i0, i1, i2, \cdots, i15\}\) is the set of tiles in which the blank tile is \(i0\)<br />
\(T\) is the time horizon (set of moves)</p>
<p><b>Parameters</b><br />
initial(i) = the starting position of tile \(i\), for all tiles \(i \in I\)<br />
final(i) = the final (target) position of tile \(i\), for all tiles \(i \in I\)</p>
<p><b>Variables</b><br />
\(p(i,t)\) = position of tile \(i\) at time \(t\), integer<br />
\(x(t)\) = \(x\)-coordinate of the blank tile at time \(t\), integer<br />
\(y(t)\) = \(y\)-coordinate of the blank tile at time \(t\), integer</p>
<p>\(z(i,t) = \left\{ \begin{array}{ll}<br />
1 & \mbox{if tile \(i\) moves at time \(t\), \(\forall i \in I\), \(\forall t \in T\)} \\<br />
0 & \mbox{otherwise}<br />
\end{array} \right. \)<br />
\(u(t) = \left\{ \begin{array}{ll}<br />
1 & \mbox{if the blank tile moves up at time \(t\), \(\forall t \in T\)} \\<br />
0 & \mbox{otherwise}<br />
\end{array} \right. \)<br />
\(d(t) = \left\{ \begin{array}{ll}<br />
1 & \mbox{if the blank tile moves down at time \(t\), \(\forall t \in T\)} \\<br />
0 & \mbox{otherwise}<br />
\end{array} \right. \)<br />
\(l(t) = \left\{ \begin{array}{ll}<br />
1 & \mbox{if the blank tile moves left at time \(t\), \(\forall t \in T\)} \\<br />
0 & \mbox{otherwise}<br />
\end{array} \right. \)<br />
\(r(t) = \left\{ \begin{array}{ll}<br />
1 & \mbox{if the blank tile moves right at time \(t\), \(\forall t \in T\)} \\<br />
0 & \mbox{otherwise}<br />
\end{array} \right. \)</p>
<p><b>15 Puzzle Integer Programming Formulation</b><br />
Minimize \( \sum_{t \in T} z(i0,t) \)</p>
<p>subject to: blank tile can make only one move at a time<br />
\( u(t) + d(t) + l(t) + r(t) = z(i0,t) \quad \forall t \in T\)</p>
<p>subject to: update the position of the blank tile after each move<br />
\( p(i0,t+1) = p(i0,t) - 4u(t) + 4d(t) - l(t) + r(t) \quad \forall t \in T\)</p>
<p>subject to: update the position of the numbered tile if it moved<br />
\( p(i,t+1) - p(i0,t) + 16 z(i,t) \leq 16, \quad \forall i \in I, \forall t \in T\)<br />
\( p(i,t+1) - p(i0,t) - 16 z(i,t) \geq -16, \quad \forall i \in I, \forall t \in T\)</p>
<p>subject to: define the x and y coordinates of the blank tile<br />
\( p(i0,t) = x(t) + 4y(t), \quad \forall t \in T\)</p>
<p>subject to: restrict the movement of the blank tile at the top edge<br />
\( 5u(t) \le p(i0,t), \quad \forall t \in T\)</p>
<p>subject to: restrict the movement of the blank tile at the bottom edge<br />
\( 4d(t) \le 16 - p(i0,t), \quad \forall t \in T\)</p>
<p>subject to: restrict the movement of the blank tile at the left edge<br />
\( l(t) \le x(t) - 1, \quad \forall t \in T \)</p>
<p>subject to: restrict the movement of the blank tile at the right edge<br />
\( r(t) \le 4 - x(t), \quad \forall t \) </p>
<p>subject to: ensure that every tile is assigned a position at every time<br />
\( \sum_{i \in I} p(i,t) = 1 + 2 + ... + 16, \quad \forall t \in T \)</p>
<p>subject to: ensure that one of the numbered tiles moves if the blank tile moves<br />
\( z(i0,t) = \sum_{i \ne i0 } z(i,t), \quad \forall t \in T\)</p>
<p>subject to: maintain the position of the numbered tiles if the blank tile does not move<br />
\( p(i,t) - p(i,t+1) + 4 z(i,t) \geq 0, \quad \forall i \in I, t \in T\)<br />
\( p(i,t) - p(i,t+1) - 4 z(i,t) \leq 0, \quad \forall i \in I, t \in T\)</p>
<p>subject to: bound restrictions on the variables<br />
\( 1 \le p(i,t) \le 16, \quad \forall i \in I, \forall t \in T\)<br />
\( 1 \le x(t) \le 4, \quad \forall t \in T\)<br />
\( 0 \le y(t) \le 3, \quad \forall t \in T\)</p>
<p>subject to: initial positions<br />
\( p(i,1) = initial(i), \quad \forall i \in I\)</p>
<p>subject to: final positions<br />
\( p(i,|T|) = final(i), \quad \forall i \in I\)</p>
<p>Different instances of the model can be created by specifying different values in the vector <i>initial(i)</i>. To solve an instance, we can use one of the NEOS Solvers in the <a href="http://www.neos-server.org/neos/solvers/index.html#milp">Mixed Integer Linear Programming</a> category.</p>
<p>In order to solve an instance of the model, we need to specify an upper bound on \(T\), the number of steps required to solve the puzzle. Clearly, we want the upper bound to be as small as possible. Brüngger et al. (1999) proved computationally that the hardest initial configurations required 80 steps to solve. Therefore, in the general case, we can define \(T = \{1, \cdots, 80\}\), but the computation time required to solve those hardest initial configurations is extensive. For the Java applet here, we make two simplifications in order to provide a user-friendly experience . First, we limit the set of available starting positions to those that can be solved within 60 seconds. Second, we have the solver return the <i>first</i> integer solution that it finds. This solution may not be optimal in the sense that there may be a shorter sequence of steps, however, this approach eliminates the (potentially lengthy) time spent by the solver proving the optimality of the solution.</p>
<h2><a name="gams" id="gams">GAMS Model</a></h2>
<p>Here is a GAMS model for an instance in which the initial configuration is the following:<br />
(i5, i1, i2, i3, i9, i6, i7, i4, i13, i10, i11, i8, i14, i15, i0, i12).</p>
<p> sets<br />
i tile number /i0*i15/<br />
t move number /0*80/</p>
<p> parameter<br />
*Optimal solution is 11 moves<br />
initial(i) /i1 2, i2 3, i3 4, i4 8, i5 1, i6 6, i7 7, i8 12, i9 5, i10 10, i11 11, i12 16, i13 9, i14 13, i15 14, i0 15/<br />
final(i) /i1 1, i2 2, i3 3, i4 4, i5 5, i6 6, i7 7, i8 8, i9 9, i10 10, i11 11, i12 12, i13 13, i14 14, i15 15, i0 16/;</p>
<p> integer variables<br />
p(i,t), x(t), y(t);</p>
<p> binary variables<br />
z(i,t), u(t), d(t), l(t), r(t);</p>
<p> variable<br />
obj;</p>
<p> equations<br />
c_blank(t)<br />
c_move(t)<br />
c_move2_1(i,t)<br />
c_move2_2(i,t)<br />
c_pos(t)<br />
c_up(t)<br />
c_down(t)<br />
c_left(t)<br />
c_right(t)<br />
c_no_repeat(t)<br />
c1(t)<br />
c2_1(i,t)<br />
c2_2(i,t)<br />
calc_obj<br />
;</p>
<p> c_blank(t).. u(t) + d(t) + l(t) + r(t) =E= z('i0',t);<br />
c_move(t)\$(not sameas(t,'80')).. p('i0',t+1) =E= p('i0',t) - 4*u(t) + 4*d(t) - l(t) + r(t);<br />
c_move2_1(i,t)\$(not sameas(i,'i0')).. p(i,t+1) - p('i0',t) + 16*z(i,t) =L= 16 + 0;<br />
c_move2_2(i,t)\$(not sameas(i,'i0')).. p(i,t+1) - p('i0',t) - 16*z(i,t) =G= -16 + 0;<br />
c_up(t).. 5*u(t) =L= p('i0',t);<br />
c_down(t).. 4*d(t) =L= 16 - p('i0',t);<br />
c_left(t).. l(t) =L= x(t) - 1;<br />
c_right(t).. r(t) =L= 4 - x(t);<br />
c_pos(t).. p('i0',t) =E= 4*y(t) + x(t);<br />
c_no_repeat(t).. sum(i, p(i,t)) =E= sum(i, ord(i));<br />
c1(t).. z('i0',t) =E= sum(i\$(not sameas(i,'i0')), z(i,t));<br />
c2_1(i,t)\$(not sameas(t,'80')).. -4*z(i,t) =L= p(i,t) - p(i,t+1);<br />
c2_2(i,t)\$(not sameas(t,'80')).. p(i,t) - p(i,t+1) =L= 4*z(i,t);<br />
calc_obj.. obj =E= sum(t, z('i0',t));</p>
<p> p.lo(i,t) = 1; p.up(i,t) = 16;<br />
x.lo(t) = 1; x.up(t) = 4;<br />
y.lo(t) = 0; y.up(t) = 3;</p>
<p> p.fx(i,'1') = initial(i);<br />
p.fx(i,'80') = final(i);</p>
<p> model puzzle4 /all/;</p>
<p> solve puzzle4 using mip minimizing obj</p>
<h2><a name="references" id="references">Acknowledgments and References</a></h2>
<p>Wai Kit Ong and Yachao Dong contributed the original version of this case study, which was completed as part of the CS/ISyE 635 taught course by Professor Jeff Linderoth at UW-Madison in Spring 2012. </p>
<ol><li>Brüngger, A., Marzetta, A., Fukuda, K., and Nievergelt, J. 1999. The Parallel Search Bench ZRAM and Its Applications. <i>Annals of Operations Research</i> <b>90</b>, 45-63, 1999.</li>
<li>Johnson, W., and Story, W. 1879. Notes on the "15" Puzzle. <i>American Journal of Mathematics</i>, 397-404.</li>
<li>Korf, R., and Schultze, P. 2005. Large-scale parallel breadth-first search. In <i>Proceedings of the 20th National Conference of Artificial Intelligence (AAAI-05)</i>, 1380-1385.</li>
</ol></div></div></div><section class="field field-name-field-method field-type-taxonomy-term-reference field-label-above view-mode-rss"><h2 class="field-label">Optimization Category (Linear Programing, Integer, MIP and etc.): </h2><ul class="field-items"><li class="field-item even"><a href="/taxonomy/term/10" typeof="skos:Concept" property="rdfs:label skos:prefLabel" datatype="">Integer Programming</a></li></ul></section>Wed, 18 Sep 2013 18:14:29 +0000rberger383 at https://neos-guide.orghttps://neos-guide.org/content/15puzzle#commentsTraveling Salesman Problem
https://neos-guide.org/content/traveling-salesman-problem
<div class="field field-name-body field-type-text-with-summary field-label-hidden view-mode-rss"><div class="field-items"><div class="field-item even" property="content:encoded"><p>Back to <a href="/content/combinatorial-optimization">Combinatorial Optimization</a></p>
<ul><li><a href="#intro">Introduction</a></li>
<li><a href="#software">Software Resources</a></li>
<li><a href="#resources">Online Resources</a></li>
<li><a href="#references">References</a></li>
</ul><h2><a name="intro" id="intro">Introduction</a></h2>
<p>Perhaps the most famous combinatorial optimization problem is the <b>Traveling Salesman Problem</b> (TSP). Given a complete graph on \(n\) vertices and a weight function defined on the edges, the objective of the TSP is to construct a <i>tour</i> (a circuit that passes through each vertex exactly once) of minimum total weight. The TSP is an example of a <i>hard</i> combinatorial optimization problem; the decision version of the problem is \(\mathcal{NP}\)-complete.</p>
<p><b>Integer Programming Formulation</b><br />
The TSP can be formulated as an integer linear programming problem. Let \(N\) be the set of vertices (cities) and let \(c_{ij}\) be the weight of the edge connecting vertex \(i\) and vertex \(j\). Let decision variable \(x_{ij}\) take the value 1 if the tour includes the edge connecting \(i\) and \(j\) and the value 0 otherwise.</p>
<p>Minimize \( \sum_{i \in N} \sum_{j \in N} c_{ij} x_{ij}\)</p>
<p>subject to: must enter each vertex exactly once<br />
\(\sum_{i \in N} x_{ij} = 1, \quad \forall j \in N\)</p>
<p>subject to: must exit each vertex exactly once<br />
\(\sum_{j \in N} x_{ij} = 1, \quad \forall i\in N\)</p>
<p>subject to: subtour elimination constraints<br />
\(\sum_{i, j \in S} x_{ij} \leq |S| - 1, \quad \forall S \subset N\)</p>
<p>subject to: integrality constraints<br />
\(x_{ij}\) integer</p>
<h2><a name="software" id="software">Software Resources</a></h2>
<ul><li>A <a href="http://www.neos-server.org/neos/solvers/co:concorde/TSP.html">NEOS version</a> of the <a href="http://www.math.uwaterloo.ca/tsp/concorde/index.html">Concorde solver</a> is available for users to solve TSP instances online.</li>
<li>Stephan Mertens's <a href="http://www-e.uni-magdeburg.de/mertens/TSP/" rel="nofollow">TSP Algorithms in Action</a> uses Java applets to illustrate some simple heuristics and compare them to optimal solutions on 10-25 node problems.</li>
<li>Onno Waalewijn has constructed Java TSP applets exhibiting the behavior of different methods for <a href="http://www.waalewijn.com/tspfast.html" rel="nofollow">heuristic</a> and <a href="http://www.waalewijn.com/tspx.html" rel="nofollow">exhaustive</a> search on various test problems.</li>
<li>The <a href="http://tsp.r-forge.r-project.org">TSP Package for R</a> provides infrastructure for specifying instances of a TSP and its (possibly optimal) solution as well as several heuristics to find good solutions. It also provides an interface to the <a href="http://www.math.uwaterloo.ca/tsp/concorde/index.html">Concorde solver</a>.</li>
<li><a href="http://code.google.com/p/google-maps-tsp-solver">TSP Solver for Google Maps API</a> is a component for Google Maps API developers to compute the fastest route that visits a given set of locations.</li>
</ul><p>For practical purposes, the traveling salesman problem is only the simplest case of what are generally known as vehicle-routing problems. Commercial software packages for <i>vehicle routing</i>, or more generally for <i>supply chain management</i>, may have TSP routines. <i>OR/MS Today</i> periodically publishes a <a href="http://www.orms-today.org/surveys/Vehicle_Routing/vrss.html" rel="nofollow">vehicle routing software survey</a>. The most recent survey appeared in the February 2014 issue.</p>
<h2><a name="resources" id="resources">Online Resources</a></h2>
<ul><li><a href="http://www.math.uwaterloo.ca/tsp/index.html">The Traveling Salesman Problem</a> website provides information on the history, applications, and current research on the TSP as well as information about the <a href="http://www.math.uwaterloo.ca/tsp/concorde/index.html">Concorde</a> solver.</li>
<li><a href="http://en.wikipedia.org/wiki/Travelling_salesman_problem">Travelling Salesman Problem</a> on Wikipedia provides some information on the history, solution approaches, and related problems.</li>
<li><a href="http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/">TSPLIB</a> provides a library of sample instances for the TSP and related problems.</li>
</ul><h2><a name="references" id="references">References</a></h2>
<ul><li>Applegate, D. L., Bixby, R. E., Chvátal, V., and Cook, W. J. 2006. <i>The Traveling Salesman Problem: A Computational Study.</i> Princeton University Press, Princeton, NJ.</li>
<li>Cook, W. J. 2011. <i>In Pursuit of the Travelling Salesman: Mathematics at the Limits of Computation</i>. Princeton University Press, Princeton, NJ.</li>
<li>Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G., and Shmoys, D. B. 1985. <i>The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization.</i> John Wiley and Sons, New York.</li>
<li>Reinelt, G. 1994. <i>The Traveling Salesman: Computational Solutions for TSP Applications.</i> Springer-Verlag, Heidelberg.</li>
</ul></div></div></div>Mon, 18 Jun 2012 16:16:26 +0000cmelan265 at https://neos-guide.orghttps://neos-guide.org/content/traveling-salesman-problem#comments