# source:projects/ApplicationTemplates/osDip/osDip.tex@276

Last change on this file since 276 was 276, checked in by kmartin, 3 years ago

update makefile.in

File size: 16.8 KB
Line
1\documentclass[11pt]{article}
2\usepackage{graphics,graphicx}
3%\usepackage[dvips]{graphics,graphicx}
4\DeclareGraphicsExtensions{.ps,.jpg,.eps,.pdf,.png}
5\usepackage{boxedminipage,amsmath,amsfonts}
6\usepackage{url}
7\usepackage{./own}
8%\usepackage{secdot}
9%\usepackage{natbib}
10\usepackage{verbatim}
11%\usepackage{moreverb}
12\usepackage{enumerate}
13\usepackage{makeidx}
14\bibliographystyle{plain}
15\makeindex
16
17
18%%%%%
19% some other macros
20\newcommand{\figurepath}{./figures}
21\newcommand{\bibpath}{/Users/kmartin/Documents/files/misc}
22\newcommand{\figfiletype}{pdf}
23
25
26% Latex macros defined for all the CppAD documentation:
27\newcommand{\T}{ {\rm T} }
28\newcommand{\R}{ {\bf R} }
29\newcommand{\C}{ {\bf C} }
30\newcommand{\D}[2]{ \frac{\partial #1}{\partial #2} }
31\newcommand{\DD}[3]{ \frac{\partial^2 #1}{\partial #2 \partial #3} }
32\newcommand{\Dpow}[2]{ \frac{\partial^{#1}}{\partial  {#2}^{#1}} }
33\newcommand{\dpow}[2]{ \frac{ {\rm d}^{#1}}{{\rm d}\, {#2}^{#1}} }
34
35% Define the hangref environment used for the References list:
36\newenvironment{hangref}
37  {\begin{list}{}{\setlength{\itemsep}{4pt}
38  \setlength{\parsep}{0pt}\setlength{\leftmargin}{+\parindent}
39  \setlength{\itemindent}{-\parindent}}}{\end{list}}
40
41% Set the page margins to 1 inch all around:
44\textwidth 6.5in \topmargin 0pt\textheight 9.0in
45\newtheorem{theorem}{Theorem}
46
47
49\newcounter{Fig}
50\renewcommand{\theFig}{\arabic{Fig}}
51\newcommand{\Fig}[2]{\refstepcounter{Fig} \label{#1}
52                     {\small\bf Figure \theFig.} {\small\sl #2 \par}}
53
54\setcounter{topnumber}{3}
55\renewcommand{\topfraction}{.9}
56\setcounter{bottomnumber}{3}
57\renewcommand{\bottomfraction}{.9}
58\setcounter{totalnumber}{4}
59\renewcommand{\textfraction}{.1}
60\setlength{\floatsep}{.25in}
61\setlength{\intextsep}{.25in}
62
63\setlength{\fboxrule}{2\fboxrule} \setlength{\fboxsep}{3\fboxsep}
64
65\newcommand{\Sa}{8pt}
66\newcommand{\Sb}{0pt}
67
68\renewcommand{\_}{{\char"5F}}
69\renewcommand{\{}{{\char"7B}}
70\renewcommand{\}}{{\char"7D}}
71\renewcommand{\^}{{\char"0D}}
72
73\let\accute= \'
74\renewcommand{\'}{{\char"0D}}
75
76\newcommand{\bfit}{\bfseries\itshape}
77
78\newlength{\extopskip} \newlength{\exbottomskip}
79\setlength{\exbottomskip}{1\baselineskip}
81\setlength{\extopskip}{1\exbottomskip}
83
84\newenvironment{Example}{\vspace{1\extopskip}\noindent\hspace*{2em}
85                         \frenchspacing\small
86                         \tt\begin{tabular}{@{}l@{}}}{
268
269
270\begin{eqnarray*}
271\begin{array}{lll}
272x_{11}\leq y_{1}\leq 1 & &  \\
273x_{12}\leq y_{1}\leq 1 & & \\
274x_{13}\leq y_{1}\leq 1 & & \\
275x_{21}\leq y_{2}\leq 1 & & \\
276x_{22}\leq y_{2}\leq 1 & &   \\
277x_{23}\leq y_{2}\leq 1 & & \\
278x_{31}\leq y_{3}\leq 1 & & \\
279x_{32}\leq y_{3}\leq 1 & &\\
280x_{33}\leq y_{3}\leq 1 & &\\
281\end{array}
282 Bx \ge b \,\, {\rm constraints} \\
283x_{ij},y_{i}\ge 0 , \,\, i = 1, \ldots, n, \, \, j = 1, \ldots, m.
284\end{eqnarray*}
285
286
287
288
289
290
291\section{Generalized Assignment Problem Example}
292
293A problem that plays a prominent role in
294vehicle routing is the {\it generalized assignment problem.}    The problem is to assign each of $n$
295tasks to $m$ servers without exceeding the resource capacity of the servers.
296
297\noindent{\bf Parameters:}
298\begin{itemize}
299\item[]  $n -$ number of required tasks
300\item[]  $m -$   number of servers
301\item[]  $f_{ij} -$ cost of assigning task $i$ to server $j$
302\item[]  $b_{j} -$  units of resource available to server $j$
303\item[]  $a_{ij} -$ units of server $j$ resource required to perform task $i$
304\end{itemize}
305
306\noindent{\bf Variables:}
307\begin{itemize}
308\item[]  $x_{ij} -$ a binary variable which is equal to 1 if task $i$ is assigned to server $j$
309and 0 if not
310\end{itemize}
311The integer linear program for the generalized assignment problem  is
312$$313\eqnarrayx{ 314\min &\sum_{i = 1}^{n} \sum_{j = 1}^{m} f_{ij} x_{ij} &&&&&&& \eq{eq:gapobj} \cr 315(GAP) &{\rm s.t.}& \sum_{j = 1}^{m} x_{ij} &=& 1, & i = 1, \ldots, n &&&& \eq{eq:gapassign} \cr 316&& \sum_{i = 1}^{n} a_{ij} x_{ij} &\le& b_{j}, &j = 1, \ldots, m &&&&\eq{eq:gapcapacity} \cr 317&& x_{ij} &\in& \{ 0, 1 \}, & i = 1, \ldots, n, & j = 1, \ldots, m. &&& 318\eq{eq:gapbinary} \cr 319} 320$$
321
322The objective function (\ref{eq:gapobj}) is to minimize the total assignment cost.  Constraint
323(\ref{eq:gapassign}) requires that each task is assigned a server.  The requirement that the
324server capacity not be exceeded is given in (\ref{eq:gapcapacity}).
325
326The test problem
327
328
329\begin{verbatim}
330 min     2 X11 + 11 X12 + 7 X21 + 7 X22 + 20 X31 +
3312 X32 + 5 X41 + 5 X42
332s.t.
333X11 + X12 =    1
334X21 + X22 =    1
335X31 + X32 =    1
336X41 + X42 =    1
337
3383 X11 + 6 X21 + 5 X31 + 7 X41 <=   13
3392 X12 + 4 X22 + 10 X32 + 4 X42 <=   10
340\end{verbatim}
341
342\section{Implementing A Block Solver}
343
344Describe the Factory Code
345
346\section{Issues to Fix}
347
348\begin{itemize}
349  \item Enhance solveRelaxed to allow parallel processing of blocks. See ticket
350  30.
351  \item Does not work when there are 0 integer variables. See ticket 31.
352  \item Be able to set options in C++ code. See ticket 41.
353  \item Problem with Alps  bounds at node 0. See ticket 43
354  \item Figure out how to use BranchEnforceInMaster or BranchEnforceInSubProb so
355  I don't get the large bonds on the variables. See ticket 47.
356\end{itemize}
357
358\end{document}
359
360configure - using command line or configure file
361
362for example on lehigh machines that have cplex, my config file is:
363
364
365
366# COIN config.site file for common autotools settings
367#enable_debug=yes
368
369#use CPLEX
370with_lp_solver=cplex
371with_ip_solver=cplex
372
373#location of CPLEX
374with_cplex_incdir="/usr/local/cplex/include/ilcplex"
376
377
378
379%%%%%%%%%%%%%%%%%%%%%
380
381Matt sept 7
382
383
384CC'ing DIP list.
385
386
387I ran the GAP example for  VERSION1. Got it to run with no problem. Very useful. I was hoping you could clarify the folloiwng.
388
3891) It looks like the only place where the blocks get defined are in 235-238:
390
391for(i = 0; i < nMachines; i++){
392modelName = "KP" + UtilIntToStr(i);
393setModelRelax(NULL, modelName, i);
394}
395
396It looks like you are NOT creating a DecompConstraintSet for each block and you
397are NOT specifying the variables that go into the blocks. Is this correct? You
398simply tell the master how many blocks there are with setModelRelax().
399
400
401That is correct. There is no "explicit" polyhedron in this example. It is
402implicitly defined by the oracle (solveRelaxed).
403
404
405
406
407
408
4092) In the solveRelaxed() method, I assume that the redCostX array contains a
410reduced cost FOR EVERY variable. Is this true? I guess it must be since I have
411not told the master which variables are in which block.  Of course I see the line
412
413const double   * redCostXB   = redCostX + getOffsetI(whichBlock);
414
415which implies maybe redCostX is only the variables for whichBlock? But then I
416have not specified the variables in whichBlock. I am confused here and this seems
417like a key point.
418
419
420redCostX is, in fact, for every variable. You will also notice in the arguments
421the "whichBlock" that tells you which block you are suppose to solve in that
422call. The redCostXB defines the starting point for the reduced costs for block
423whichBlock. It uses the user-defined 'getOffsetI' function. Since this is a
424user-defined oracle, they are responsible for keeping track of which variables
425correspond to which blocks. The framework doesn't really need to know that -
426since the polyhedron is defined implicitly.
427
428
429
430
4313) This question is related to 2). What if I define "master only" variables.  Do
432the "master only" variables reduced cost get included in redCostX in
433solveRelaxed()? If you are not telling the master which variables go into which
434block, then I guess the concept of "master only" variables is not really needed
435or is moot. Correct? Just pass all variable to solveRelaxed(). In my case I do
436have variables that appear only in the master. Should I declare these?
437
438
439Yes, master-only would be included in redCostX and as a user you would want to
440ignore them. Each master-only is considered its own block and is dealt with
441internally. I guess I should add an example that shows implicit polyhdreon and
442master-only variables? Is that the case you have? If so, I can work on that soon.
443Yes, you should delcare them and explicitly state them as master-only.
444
445
446
447
448
449
4504) This is related to 3). If indeed, redCostX is the vector of all variables then
451I suppose I could easily do what I wrote you about earlier this  summer, namely
452solve the blocks in parallel. That is I could take redCostX and in my own code,
453in parallel solve a problem for each block and then when each solveRelaxed() is
454called in turn, give it the solution from my parallel solve. Does this make
455sense?
456
457
458Not yet. Two issues there. (1) the logic by default is to loop over all blocks
459and call the solveRelaxed for each value of whichBlock. So, if you solved all in
460parallel, you'd get too many. You, could, of course, just solve the "first one"
461for all and then skip the rest. But, that is an ugly hack. (2) The argument
462convexDual is the dual associated with the convexity constraint for whichBlock.
463To do what you want, you really need all the duals for the convexity constraint.
464Again, you could "get this" by grabbing the full dual vector from the master LP
465and parsing it yourself - but that gets tricky when you add in cut and branch
466constraints to the master -- the accounting is tricky.
467
468The better approach is for me to provide you an API for doing what you want. I
469have not got around to that yet: https://projects.coin-or.org/Dip/ticket/30
470
471
472
473
474% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
475
476
477
478Master-only variables need to be dealt with special. Because of the design of
479DIP, it relies on a mapping between the compact and extended space. If there are
480no master-only vars, this is clearly just x=sum{b} sum{s} lambda^b_s s, where s
481is a vector in projected space of x (for each block).
482
483With master-only vars, this only works if you "put these vars" in another block
484(or blocks). Experience shows that putting them all in one block and treating it
485like another subproblem performs poorly. Since they are unconstrained in the
486subproblems, they are all independent and the most efficient thing to do is to
487treat each as its own block -- with really only 2 choices - set it at its UB or
488LB. All of this can be done efficiently if I know which ones are master-only
489vars.
490
491Yes, the user defines all the vars in the core. But, without knowing which are in
492the blocks, I don't know which are "master-only".
493
494
495%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
496
497
498But for each block, convexDual affects the value of the reduced cost, but it has
499no effect on which column I choose. The convexDual does not affect the subproblem
500solution, only the solution value. Therefore, in the first call to solveRelaxed
501(whichBlock = 1) I can use redCostX for all the variables and simultaneously find
502the best column for each subproblem. Then when the other subproblems are called
503(whichBlock >1) I simply take the column from the first call (do not solve again)
504and return it. The convexDual did not affect that solution. Hope I  am making
505sense here.
506
507
508
509Yep. You are correct, convexDual does not effect the pricing. It only effects the
510"check" for negative RC (if you choose to do that as a user - you don't need to
511actually) and, the constructor for a DecompVar. The latter could be redesigned so
512the user doesn't need to provide it and the internal adjusts it for you. Either
513one, a change (or addition) in the API would make this cleaner. I will think