Get multiply feasible solutions from solution pool for mip

正式なコメント

Gurobi Staff

2026年11月13日 01:48

This post is more than two years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support.

Marika Karbstein

Gurobi Staff

2023年03月03日 07:24

Hi,
All solutions in the solution pool should be feasible solutions.
Could you share a minimal reproducible example?
Best, Marika

0

Dong Han

2023年03月03日 14:22

Hi Marika, Thank you very much for you reply. I just found I could get optimal solution which is definitely feasible when I set PoolSearchMode by default and only get one solution. But, when I want to get more feasible solution with default PoolSearchMode, I found some solution is infeasible, it seems failed to add lazy constraints(by callback). I just don't know why sometimes adding lazy constraints works, sometimes not.(I set GRB_IntParam_LazyConstraints to 1). Since I revised some part of code, I will try to provide an example.

if (len < n) {

// cout << "XXXX len = " << len << endl;

// for (int i = 0; i < len; i++)

// cout << tour[i] << " ";

// cout << endl;

// for (int i = 0; i < n; i++){

// for (int j = i+1; j < n; j++) {

// if (x[i][j] > 0.5)

// cout << "x:" << i << " " << j << endl;

// if (x_bar[i][j] > 0.5)

// cout << "x_bar:" << i << " " << j << endl;

// }

// Add subtour elimination constraint

GRBLinExpr expr = 0;

//cout << "starting building constraints.." << endl;

for(int i =0; i < len-1; i++){

for(int j = i+1; j < len; j++){

expr += vars[tour[i]][tour[j]];

expr += vars_bar[tour[i]][tour[j]];

}

//cout << "finishing building constraints.." << endl;

addLazy(expr <= len-1);

//cout << "finishing add lazy constraints.." << endl;

}

0

Marika Karbstein

Gurobi Staff

2023年03月03日 15:30

This is not a reproducible example.

If I understand you correctly you started with the Gurobi example tsp_c++.cpp. But why do you change something in the code if you want to get more feasible solutions with default PoolSearchMode?

If I run the example tsp_c++.cpp with value 12, Gurobi finds 2 solutions:

Solution count 2: 3.41529 6.06623

Both solutions are feasible. If you want Gurobi to find more solutions, you need to change the parameter PoolSearchMode to 1 or 2 (and maybe also adapt PoolSolutions).
I do not see where you get infeasible solutions.

0

Dong Han

2023年03月03日 15:58

Yes. I could also get the results you shown here. But if I want to print these two solutions with GRB_IntParam_SolutionNumber, sometimes the sub-optimal solution is infeasible, which means it has subtour, like "0-1-3-2" and "4-6-7-5" if we have 8 nodes. Do you mean I have to set PoolSearchMode to 1 or 2 to get feasible sub-optimal solution?

0

Dong Han

2023年03月03日 16:20 編集済み

Since I need to revised tsp_c++ for my own project, I just show you the part of code and infeasible result I got. For example, I have 22 node, but I got a tour with only 5 nodes.

int SolCount = model.get(GRB_IntAttr_SolCount);

if(SolCount >0){

double poolobj =0.0;

for(int i =0; i < SolCount; i++){

model.set(GRB_IntParam_SolutionNumber, i);

poolobj = model.get(GRB_DoubleAttr_PoolObjVal);

double**sol =newdouble*[n];

double**sol_bar =newdouble*[n];

for(int i =0; i < n; i++)

{

sol[i]=model.get(GRB_DoubleAttr_Xn,vars[i], n);

sol_bar[i]=model.get(GRB_DoubleAttr_Xn,vars_bar[i], n);

}

int* tour =newint[n];

int len;

findsubtour(n, sol, sol_bar,&len, tour);

if(len < n){

cout << "len = " << len << endl;

cout << "tour : " << " ";

for(int i =0; i < len; i++){

cout << tour[i] << " ";

}

cout << endl;

The result is as following.

len = 5

tour :  3 4 11 16 19

sol:0 14

sol:0 17

sol:1 2

sol:1 6

sol:2 5

sol:3 4

sol_bar:3 19

sol:4 11

sol:5 7

sol:6 10

sol:7 9

sol:8 10

sol_bar:8 13

sol_bar:9 17

sol_bar:11 16

sol_bar:12 13

sol:12 15

sol:14 21

sol:15 18

sol:16 19

sol:18 20

sol:20 21

0

Marika Karbstein

Gurobi Staff

2023年03月03日 17:52 編集済み

This is still not enough information to help you. Your problem is probably not defined properly.
Could you explain a bit more about what you exactly want to solve?
Why do you have variables vars and vars_bar? What does vars_bar represent?
What does the callback to add the sub-tour elimination constraints look like?
What does the output "sol: 0 14" or "sol_bar: 3 19" mean?

0

Dong Han

2023年03月03日 18:08 編集済み

Thank you very much for your reply! Since I revised tsp_c++ to fit my model, vars and vars_bar are both decision variables. For example, as for 0 14, vars[0][14] + vars_bar[0][14] = 1, which means if we travel from 0 to 14, we could make vars[0][14] = 1 or vars_bar[0][14] = 1. As for the solution part, sol: 0 14 means the optimal solution told us that we travel from 0 to 14 by vars[0][14] = 1 and we travel from 3 to 19 by vars_bar[3][19] = 1. From above result, when I get this suboptimal solution, this suboptimal solution has a subtour 3 4 11 16 19, which is infeasible because subtour solution should be eliminated by lazy constraints. So I think the callback function didn't work for this suboptimal, but I have no idea how to fix it. Here is the callback part. Thank you.

void callback() {

try{

if(where == GRB_CB_MIPSOL){

// Found an integer feasible solution - does it visit every node?

double**x =newdouble*[n];

double**x_bar =newdouble*[n];

int*tour =newint[n];

int len;

for(int i =0; i < n; i++){

x[i]=getSolution(vars[i], n);

x_bar[i]=getSolution(vars_bar[i],n);

}

findsubtour(n, x, x_bar,&len, tour);

if(len < n){

// Add subtour elimination constraint

GRBLinExpr expr = 0;

for(int i =0; i < len-1; i++){

for(int j = i+1; j < len; j++){

expr += vars[tour[i]][tour[j]];

expr += vars_bar[tour[i]][tour[j]];

}

}

addLazy(expr <= len-1);

}

for(int i =0; i < n; i++)

{

delete[]x[i];

delete[]x_bar[i];

}

delete[] x;

delete[] x_bar;

delete[] tour;




}

}catch(GRBException e){

cout << "Error number: " << e.getErrorCode() << endl;

cout << e.getMessage() << endl;

}catch(...){

cout << "Error during callback" << endl;

}

}

0

Marika Karbstein

Gurobi Staff

2023年03月03日 20:58

I cannot reproduce the issue.

You probably need to share the complete reproducible example.

0

Dong Han

2023年03月10日 16:15

Hi, Here is my code. The main function of this project is to find several routes that start from 0 and visited several nodes and finally go back to 0. For example, if I have 0 1 2 3 4 5 6 7 8, and I would like to get the results that looks like 0-1-2-4-5-0 and 0-3-8-7-6-0. And I do not want to get subtour like 3-8-7-3. When I retrieved the suboptimal solution. I did found certain suboptimal solution including subtour like 3-8-7-3. Please see the code and set node number 33.

#include "gurobi_c++.h"

#include <cassert>

#include <cstdlib>

#include <cmath>

#include <sstream>

#include <vector>

#include <algorithm>

using namespace std;

string itos(int i) {stringstream s; s << i; return s.str(); }

double distance(double* x, double* y, int i, int j);

void findsubtour(int n, double** sol, vector<vector<int>> &sub_tour, int* tourlenP);

// Subtour elimination callback. Whenever a feasible solution is found,

// find the smallest subtour, and add a subtour elimination constraint

// if the tour doesn't visit every node.

class subtourelim: public GRBCallback

{

public:

GRBVar** vars;

intn;

subtourelim(GRBVar**xvars,intxn){

vars=xvars;

n=xn;

}

protected:

voidcallback(){

try{

if(where == GRB_CB_MIPSOL){

// Found an integer feasible solution - does it visit every node?

double**x=newdouble*[n];

for(inti=0;i<n;i++)

x[i]=getSolution(vars[i],n);

inttour_len;

vector<vector<int>>sub_tour;

findsubtour(n,x,sub_tour,&tour_len);

for(size_ti=0;i<sub_tour.size();i++){

if(find(sub_tour[i].begin(),sub_tour[i].end(),0)==sub_tour[i].end()){

intlen=sub_tour[i].size();

GRBLinExpr expr = 0;

for(size_tk=0;k<sub_tour[i].size();k++)

for(size_tj=k+1;j<sub_tour[i].size();j++)

expr+=vars[sub_tour[i][k]][sub_tour[i][j]];

addLazy(expr<=len-1);

cout << "Adding lazy constraint" << endl;

}

}

for(inti=0;i<n;i++)

delete[]x[i];

delete[]x;

}

}catch(GRBException e){

cout << "Error number: " << e.getErrorCode() << endl;

cout << e.getMessage() << endl;

}catch(...){

cout << "Error during callback" << endl;

}

}

};

// Given an integer-feasible solution 'sol', find the smallest

// sub-tour. Result is returned in 'tour', and length is

// returned in 'tourlenP'.

void

findsubtour(int n,

double**sol,

vector<vector<int>>&sub_tour,

int*tourlenP)

{

bool*seen=newbool[n];

for(inti=0;i<n;i++)

seen[i]=false;




intvisited=0;

boolflag;

vector<int>temp_tour;

do{

flag=false;

intnode=0;

seen[node]=true;

for(intlen=0;len<n;len++){

inti;

for(i=0;i<n;i++){

if(sol[node][i]>0.5&&!seen[i]){

if(!node){

temp_tour.emplace_back(node);

}

node=i;

temp_tour.emplace_back(node);

seen[node]=true;

++visited;

break;

}

}

if(i==n){

sub_tour.emplace_back(temp_tour);

temp_tour.clear();

break;

}

}

for(intj=1;j<n;j++){

if(sol[0][j]>0.5&&!seen[j]){

flag=true;

break;

}

}

}while(flag);

cout << "visited = " << visited << endl;

*tourlenP=visited;




while(visited<n-1){

for(inti=1;i<n;i++){

while(!seen[i]){

intstart=i;

for(intlen=0;len<n;len++){

temp_tour.emplace_back(start);

++visited;

seen[start]=true;

intj;

for(j=1;j<n;j++){

if(sol[start][j]>0.5&&!seen[j]){

start=j;

break;

}

}

if(j==n){

sub_tour.emplace_back(temp_tour);

temp_tour.clear();

break;

}

}

}

}

}

// cout << "findsubtour : sub_tour_list" << endl;

// for (size_t i = 0; i < sub_tour.size(); i++){

// for (size_t j = 0; j < sub_tour[i].size(); j++){

// cout << sub_tour[i][j] << " ";

// }

// cout << endl;

// }

delete[]seen;

}

// Euclidean distance between points 'i' and 'j'.

double

distance(double* x,

double*y,

inti,

intj)

{

doubledx=x[i]-x[j];

doubledy=y[i]-y[j];

returnsqrt(dx*dx+dy*dy);

}

int

main(int argc,

char*argv[])

{

if(argc<2){

cout << "Usage: tsp_c++ size" << endl;

return1;

}

intn=atoi(argv[1]);

double*x=newdouble[n];

double*y=newdouble[n];

inti;

for(i=0;i<n;i++){

x[i]=((double)rand())/RAND_MAX;

y[i]=((double)rand())/RAND_MAX;

}

GRBEnv *env = NULL;

GRBVar **vars = NULL;

vars = new GRBVar*[n];

for(i=0;i<n;i++)

vars[i]=newGRBVar[n];

try{

intj;

env = new GRBEnv();

GRBModel model = GRBModel(*env);

// Must set LazyConstraints parameter when using lazy constraints

model.set(GRB_IntParam_LazyConstraints,1);

//model.set(GRB_IntParam_PoolSearchMode,1);

// Create binary decision variables

for(i=0;i<n;i++){

for(j=0;j<=i;j++){

vars[i][j]=model.addVar(0.0,1.0,distance(x,y,i,j),

GRB_BINARY, "x_"+itos(i)+"_"+itos(j));

vars[j][i]=vars[i][j];

}

}

// Degree-2 constraints

GRBLinExpr expr1 = 0;

for(j=0;j<n;j++){

expr1+=vars[0][j];

}

model.addConstr(expr1>=4,"vehicle_");

for(i=1;i<n;i++){

GRBLinExpr expr = 0;

for(j=0;j<n;j++)

expr+=vars[i][j];

model.addConstr(expr==2,"deg2_"+itos(i));

}

// Forbid edge from node back to itself

for(i=0;i<n;i++)

vars[i][i].set(GRB_DoubleAttr_UB,0);

// Set callback function

subtourelimcb=subtourelim(vars,n);

model.setCallback(&cb);

// Optimize model

model.optimize();

// model.write("tsp_model.lp");

cout << "########Print the results#########" << endl;

// Extract solution

intSolCount=model.get(GRB_IntAttr_SolCount);

if(SolCount>0){

for(inti=0;i<SolCount;i++){

model.set(GRB_IntParam_SolutionNumber,i);

doublepoolobj=model.get(GRB_DoubleAttr_PoolObjVal);

cout << "Obj value " << i << ": " << poolobj << " ";

double**sol=newdouble*[n];

for(inti=0;i<n;i++)

sol[i]=model.get(GRB_DoubleAttr_Xn,vars[i],n);

// for (int i = 0; i < n; i++){

// for (int j = i+1; j < n; j++) {

// if (sol[i][j] > 0.5)

// cout << i << " " << j << " ";

// }

// }

// cout << endl;

intvisited_len;

vector<vector<int>>sol_tour;

findsubtour(n,sol,sol_tour,&visited_len);

cout << "visited_len = " << visited_len << endl;

//assert(len == n);

cout << "sub_tour_list" << endl;

for(size_ti=0;i<sol_tour.size();i++){

for(size_tj=0;j<sol_tour[i].size();j++){

cout << sol_tour[i][j] << " ";

}

cout << endl;

}

for(inti=0;i<n;i++)

delete[]sol[i];

delete[]sol;

}

}

}catch(GRBException e){

cout << "Error number: " << e.getErrorCode() << endl;

cout << e.getMessage() << endl;

}catch(...){

cout << "Error during optimization" << endl;

}

for(i=0;i<n;i++)

delete[]vars[i];

delete[] vars;

delete[]x;

delete[]y;

delete env;

return0;

}

And this is one of suboptimal solution I got from solution pool that has sub tour.

sub_tour_list

0 17 8 5 6 22 

0 20 15 18 21 3 19 30 24 11 26 9 4 32 12 10 28 13 29 25 

0 23 1 7 31 

2 14 27 16

0

Marika Karbstein

Gurobi Staff

2023年03月13日 07:07

Which Gurobi Version do you use?

Could you please also add the log file?

0

Dong Han

2023年03月14日 21:10

The Gurobi version I use is 952. When you run this code, you are able to get the log file.

0

Marika Karbstein

Gurobi Staff

2023年03月15日 12:39

There were some fixes for Version 10.0.0, see Recent Bug Fixes by Version - Gurobi Optimization:

Fixed issue with not calling the callback for solutions found in MIP cleanup at the end of the solve
Fixed a bug that the MIPSOL callback is not called for one of the solutions found

I think the latter corresponds to what you observed.

I recommend updating to the newest version.

0

Dong Han

2023年03月16日 03:14

Thank you very much! Problem solved!

0

Get multiply feasible solutions from solution pool for mip

コメント

お探しのものを見つけられませんでしたか？