New answers tagged

1

If the $y$ function is continuous (meaning $a\cdot 25 + b = a^\prime \cdot 25 + b^\prime$ and similarly at other breakpoints), you can use an SOS2 constraint to model this. Let $p_0, \dots, p_n$ be the breakpoints ($n=4,\,p_0 = 15,\,p_4 =55$ in your example) and $\gamma_0 \dots, \gamma_n$ be the values of the $y$ function at $p_0, \dots, p_n$. Add continuous ...


3

Let $y_i$ be a binary variable that equals $1$ if and only if $x$ is in the interval $i \in \{[15,25],[25,35],[35,45],[45,55]\}$. You can express $x$ as a convex combination of the extreme points of these intervals by introducing variables $\lambda_0, \lambda_1,\lambda_2,\lambda_3, \lambda_4 \in \mathbb{R}^+$. If $f$ denotes your piecewise linear function, ...


2

My overall experience is that feeding constraints of the form $\rm objval \geq lb$ is detrimental to MIP solver performance. The main reason is the following: MIP solvers rely on branch-and-bound algorithms... ... whose performance depends heavily on branching decisions... ... which are themselves based on how the dual (lower if you're minimizing) bound ...


1

I'm not aware of any solver that can exploit a lower bound to a minimization problem. (An upper bound can be used to prune the search tree, assuming you are using branch-and-bound/branch-and-cut.) CPLEX, for instance, will let you supply the lower bound via the LowerCutoff parameter, but it only uses that information in a maximization problem.


2

There are different approaches to solve MILP problems since you didn't mention what kind of solver you are using i assume you mean in context of branch and bound solver. Feasible solutions are found using a feasibility pump which tries to guess a low feasible solution.The feasibility pump could be positively affected by those additional constraints as a part ...


4

In Making optimization simple (Python) I gave 2 options: progress listener / MIP info callback get solutions one by one The models: from docplex.mp.model import Model from docplex.mp.progress import * mdl = Model(name='buses') nbbus40 = mdl.integer_var(name='nbBus40') nbbus30 = mdl.integer_var(name='nbBus30') mdl.add_constraint(nbbus40*40 + nbbus30*30 >...


3

One solution is to add an Incumbent callback (not sure whether DOCPLEX support this yet, but certainly Java/C++), and log the solution + time stamp within the the callback. Another solution which, if my memory service me well, is the following: Set the MIP integer solution limit to 1 (IntSolLim parameter in Cplex <=12.6). Invoke solve(). Cplex will ...


5

If the variable is declared integer (and assuming the solver leaves it that way in the presolve stage), there is at least a chance that the solver will branch on it. In some cases this might be a good thing (getting the solver to a feasible solution faster, improving the bound faster) and in some cases this might be a bad thing (distracting the solver from ...


2

It is not the best option to regard it as a non-convex QP. A product of a binary variable and a continuous variable is not really bilinear (or non-linear). For example, the nonlinear constraint $$ z_{ij} \geq x_{ij}y_{ij} $$ could be replaced with $$ z_{ij} \geq y_{ij} - y_{\max}(1-x_{ij})\\ z_{ij} \geq y_{\min}x_{ij} $$ (the RHS of the second line could be $...


4

Well, you did not define and detail well the problem, hence, I will first write formally the problem definition based on my understanding of what you have written, and then I will propose an Integer Programming formulation. Problem definition Let's first define formally the problem. Let: $t$ be the number of tasks to be serviced; $T = \mathbb{N}_{\leqslant ...


4

It looks like your first constraint should instead be $$0b_1 + a_1 b_2 + a_2 b_3 - d \le 0$$ With this change, the logical implications are \begin{align} b_1 = 1 &\implies 0 \le d \le a_1 \\ b_2 = 1 &\implies a_1 \le d \le a_2 \\ b_3 = 1 &\implies a_2 \le d \le a_3 \end{align} To avoid ambiguous borders, introduce a small tolerance $\epsilon>...


3

In Breadth First Search, nodes are processed by non-decreasing value of their depth, i.e. the next node processed in the unprocessed node with the smallest depth. In Best First Search, a value is assigned to each unprocessed node. The next node processed is the unprocessed node with the smallest value. Therefore, Breadth First Search is equivalent to a Best ...


2

There are multiple ways to express a finite interval of integers using boolean variables. A different encoding would be the logarithmic one $$\sum_{i=0}^{\left \lceil{\log_2(10)}\right \rceil } 2^i\tilde{x}_i \text{ subject to } \sum_{i=0}^{\left \lceil{\log_2(10)}\right \rceil } 2^i\tilde{x}_i \leq 10$$ You can come up with many such encodings and in ...


5

Constraints 1 and 2 ensure that there is an edge going in and out of every node. Constraint 3 works as a subtour elimination and along with the above constraints ensures that there is no subtour and as a result, you must enter and leave the depot. A simple illustration is to assume there are only 3 nodes. So: $ V = \{0, 1, 2\}$ and $ N = \{1,2\}$. Let's ...


5

Unless you turn off the presolve step, CPLEX will eliminate the variables that are locked at zero during presolve. So the answer to your second question is that presolve may take slightly longer (but the difference will be too small to notice) and the actual branch-and-cut phase will not take any longer than if you had omitted the variables yourself. The ...


2

Your question isn't entirely clear and isn't really an OR question, but I think what you are trying to do is the following: for j in n: for k in r: o += xsum(w[k] *y[k][jj] for jj in n if jj <= j) >= xsum (a[i][k]* x[i][j] for i in p)


5

Forum users are invited to post their suggestions for tighter/better formulations of mixed integer linear programming models here. The emphasis is on getting solutions (and closing the gap) efficiently, as opposed to model expressiveness (ease of users to see what is going on in the model). General Logical constraints For "big M" models, smaller ...


2

I am not familiar with this specific subject but, do you try googling about that? There are many related papers such as: Developing a model for multi-objective optimization of open channels and labyrinth weirs: Theory and application in Isfahan Irrigation Networks Optimization of Irrigation Scheduling Linear Optimization Model for Efficient Use of ...


5

If the time for any project fails to be a convex function of the number of employees assigned to the project, I think your best bet is indeed to use a binary variable for each combination of project and employee count. Note that, in your example, completion time is a linear function of head count for the third project and a convex function for the second ...


4

Can anyone think about a better formulation? Another option is to use binary variables $x_{it}$ that take value $1$ if task $i$ starts at time $t$. You then need two sets of constraints: one start time per task: $$ \sum_{t}x_{it} = 1 \quad \forall i $$ don't overlap tasks: $$ \sum_{i}\sum_{k, t+1 - d_i \le k \le t}x_{ik} \le 1 \quad \forall t $$ This ...


2

In computer science, "integer" data types are generally a fixed-length array of bits. In earlier languages, those lengths were generally 16 or 32 bits, but later languages tend towards 64. This type of implementation does have drawbacks. For instance, they aren't really integers, in the mathematical sense, as they are members of a finite set. The ...


Top 50 recent answers are included