1
$\begingroup$

I am trying to find the algorithm for the 0-1 goal programming problem. Actually I don't have any recent references for explicit algorithms, all the recent articles are about the modelling and not about the solution and algorithms (the solution is found using the commercial software like LINGO or CPLEX).

Now I am thinking that linear goal programme can be reduced to the multidimensional 0-1 knapsack problem where the the simple linear combination of goal program auxiliary variables n1(+)+n2(+)+... can be considered as the objective function the initial goal expressions can be considered as the constraints of the multidimensional knapsack problem together with the remaining constraints of the goal program.

Am I right? To which classical integer (0-1) programming problems the 0-1 goal programm can be reduced?

There is simple procedure how to convert nonpreemptive simple integer goal program to linear program and that procedure is described in article "Linear Goal Programming and Its Solution Procedures" (can be Googled). The problem in my case is that my initial variables xi are 0-1 variables but auxiliary variables y(+)j, y(-)j can take any value and so the resulting problem is general mixed-integer problem or at least general integer problem. Is this the best possible conversion in this case? It could be better to stay end with 0-1 problem and use all the efficiency of the solution of such problems.

$\endgroup$
  • $\begingroup$ Welcome to CS.SE! Can you remind us what the 0-1 goal programming problem is? When you say "the algorithm", note that there's probably not just one algorithm; often there are multiple possible algorithms. Also, can you tell us what research you've done? Did you search on Google Scholar? Note that you can use MathJax (Latex) to format your math expressions more cleanly. Finally, can you provide a full citation for that "Linear Goal Programming" article, and preferable a link to a non-paywalled copy of the paper? I encourage you to edit the question based on these comments. $\endgroup$ – D.W. Aug 5 '15 at 19:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.