Hot answers tagged

18

For context: most (if not all) major LP solvers are built on 2 algorithms: the simplex method, and the interior-point method. The simplex method is intrinsically sequential: you're doing a lot of (cheap) operations called pivots, and the matrices involved are usually sparse. At each pivot, you essentially perform a rank-one update of a sparse LU ...


13

The Graph Coloring example shipped with CP optimizer (file: color.cpp in the examples directory): #include <ilcp/cp.h> const char* Names[] = {"blue", "white", "yellow", "green"}; int main(int , const char * []){ IloEnv env; try { IloModel model(env); IloIntVar Belgium(env, 0, 3, "B"), Denmark(env, 0, 3, "DK"), ...


12

It could be that you faced the issue described in this bug report. RS03137: CPLEX MAY IGNORE TIME LIMITS ON HIGHLY SYMMETRIC MODELS ON WHICH A NEW INCUMBENT IS FOUND CLOSE TO THE TIME LIMIT. http://www-01.ibm.com/support/docview.wss?uid=swg1RS03137 The bug was fixed in version 12.9, which was released earlier in the year.


10

You have it almost all right, with a few caveats. Let's say I want to implement a Foo Lazy Constraint: #include <ilocplex/ilocplex.h> #include <ilocplex/ilocplexi.h> struct Foo : IloCplex::LazyConstraintCallbackI { // Your code goes here... }; There are three main things you need to put inside your class; two of these are documented (more or ...


9

in order to increase the throughput you could Not only rely on add and remove in "modifying problems" options but on smaller changes. Try to run the instances in parallel Instead of adding a constraint on the objective use the setting IloCplex::Param::MIP::Tolerances::UpperCutoff or IloCplex::Param::MIP::Tolerances::LowerCutoff


8

What you want is: AddLessOrEqual(LinearExpr(starts[j]).AddConstant(durations[j]), starts[succ[j][s]]) You might also want to take a look at the examples (ending with _sat.cc) to be more familiar with the c++ methods. https://github.com/google/or-tools/tree/master/examples/cpp


8

That may be related to the "presolve" phase of the optimization procedure. In large instances, the time for "presolve" may be too large, that makes the total time larger than the specified time-limit. If that is the case, you can set the presolve parameter to zero, so that CPLEX does not perform a presolve on your instances. The following link is useful to ...


7

Can you elaborate a bit on what you mean when you say you are getting "Strange values"? One possible explanation is that if you call getDuals() on a model that includes some variables bounds other than $[0, +\infty)$, then your dual unbounded ray requires that you look at the reduced costs as well as the the dual variables returned by getDuals(). However, ...


7

If you look at OR-Tools: CumulativeConstraint, AddCumulative takes a variable as argument, so if it is constant, create a variable with a fixed domain. It returns a CumulativeConstraint with a method to add (IntervalVar, DemandVar) pairs to the constraint. See OR-Tools 7.4: C++ Reference (CumulativeConstraint). Note that the rcpcp solver is implemented in ...


7

For specifying constraint direction, look to the various IloRange constructors. You can specify both a lower and upper bound (for constraints of the form $b_0 \le a'x \le b_1$, or use a constructor that either defaults the lower bound to $-\infty$ or defaults the upper bound to $+\infty$. For adding objective terms, you have at least a couple of options I ...


6

You don't actually need to use the MIP start approach. Fix the upper and lower bounds for all your discrete variables to their values in the heuristic solution, then try to solve the model. Assuming CPLEX asserts that the modified model is infeasible, invoke the conflict refiner to see which constraints (in addition to at least some of your modified bounds) ...


5

You can use addTerms() to construct a linear expression in one call. According to the documentation this is the most efficient way: You should avoid using expr = expr + x in a loop. It will lead to runtimes that are quadratic in the number of terms in the expression. Using expr += x (or expr -= x) is much more efficient than expr = expr + x. Building ...


5

To create an intermediate boolean that is true iff s[j] == t you just have to create 2 constraints: cp_model.AddEquality(s[j], t).OnlyEnforceIf(b); cp_model.AddNotEqual(s[j], t).OnlyEnforceIf(Not(b)); The problem with this line: cp_model.AddEquality(b, starts[j]==actual_t); is that starts[j]==actual_t "always" evaluates to false. To learn more about ...


5

Another paradigm to parallelize search heuristics is the Backbone strategy. See for example this paper. The main idea is to run multiple instances of an arbitrary heuristic in parallel, and then compare the resulting solutions of each instance. "structures" (e.g. subtours in TSP) common in all/most solutions (called Backbones) are used to reduce the ...


4

I don't have any C++ code using a lazy constraint callback, although I could show you a Java example if you can't find anything better. The basic approach, IIRC, is to create an instance of class IloCplex::LazyConstraintCallbackI. In it, you implement the main() method, which is what CPLEX will call to invoke the callback. Inside the main method, you call ...


4

CpModelProto is a protobuf representation of your model in ortools. You create it by using the CpModelBuilder class (your cp_model), and calling its Build() method, the SolveCpModel function that you are using actually also takes a CpModelProto as its first argument.


4

Out of the multiple options, the open-source option is Coin-OR's BCP (Branch-Cut-Price) [github]. SCIP also offers branch-and-price via its GCG (generic branch-cut-and-price) solver [link].


4

In the Python API there is a pretty good docstring of what an OptionalIntervalVar is: An optional interval variable is a constraint, that is itself used in other constraints like NoOverlap. This constraint is protected by an is_present literal that indicates if it is active or not. Internally, it ensures that is_present implies start + size == ...


3

The answer is basically no. You will find interesting information here related to node evaluation and here related to node selection in the CPLEX B&B. In particular, by setting the parameter Cplex.NodeSelect to the value BestEst, you will activate the so-called Best-Estimate Search. As a competitor of CPLEX, we know CPLEX quite well :-) Now, the best ...


3

Assuming that your solution is indeed feasible and that your lazy constraints are correctly coded, the most likely explanation is that the order of your variables is inconsistent between your heuristic and CPLEX's input.


3

After hours of internet research and coding debugging, I could finally solve the problem. The problem was on the way that I passed the solution to the Cplex MIP Start. Below follows an example of how I was passing the solution to the Cplex MIP Start, where x_var is a matrix of variables, x_start_val is a matrix of values, and cplex is an object of class ...


3

In order to query the GRB_DoubleAttr_UnbdRay attribute, you need to optimize the problem with the InfUnbdInfo parameter set to 1.


3

If I recall correctly, adding a constraint on the primal objective function causes degeneracy in the dual LPs, which could account for at least part of the speed decrease you noted. In addition to Alex's suggestion about using the upper and lower cutoff parameters, you could add a new variable (call it $z$), constraint it to equal the original objective ...


3

The link that @EhsanK posted already covers the question pretty well. In such a case, Gurobi should choose the best suited algorithm on its own. Check out this little example, where I read and optimize a linear model, add a new constraint, and optimize again: In [20]: m = gp.read('C:/gurobi900/win64/examples/data/afiro.mps') Read MPS format model from file ...


3

Have not used CPLEX, but I've done that in Gurobi. In the latter, you just retrieve the equivalent of dualFarkas() when the primal version of the Benders subproblem you are solving is infeasible.


3

I agree that the e_z == 1 constraint belongs in the model. Your constraints y_bounds(k)*z[k] <= y_hat[k] && y_hat[k] <= y_bounds(k+1)*z[k] do not appear in the Valenzuela dissertation, though, and I suspect they are the source of your troubles. Note, for example, that if $M=10$ and $z[3] = 1$, you are forcing $x\in [0.3, 0.4]$ and $y\in [0.3,0....


2

I've implemented reproducible parallelization on a number of Local Search variants with incremental score calculation (= delta constraint and fitness evaluation). Some of our requirements you might be able to forgo (most notably OO/FP support), but others (such as not sacrificing incremental calculation) are crucial to get better results. For more ...


2

I don't know whether this is the reason, but the documentation says that InfUnbdInfo is for LP only. So we might have to work with the LP. Two thoughts: x = 0, u = 0 is a feasible solution for the MIP. As x is bounded, x will not be part of the ray. Thus, any ray for the LP should also be a ray for the MIP. So if Gurobi decides your problem is unbounded, ...


2

Have you tried to disable all the presolve? I don't remember which version it stoped, but in some early 12. versions of cplex there was a bug that did not disable some presolve function that allowed the solver to remove some constraints/variables it found unnecessary. Sometimes this could lead to infeasibility, or suboptimal solutions.


2

First, I don't understand why you extract the master model, set parameters and add the callback repeatedly inside a loop. When using a callback, the plan is to solve the master problem once, adding cuts via the callback along the way, so extracting the model etc. would be done once. Second, and more directly related to your issue, while I'm not a C/C++ user ...


Only top voted, non community-wiki answers of a minimum length are eligible