New answers tagged mixed-integer-programming
5
votes
Accepted
Linearization the product of three variables (two binary & one continuous)
More compactly, you want to enforce
$$-x|y| \le p \le x|y|$$
Assume $L \le y \le U$ for some constants $L\le 0$ and $U\ge 0$, and let $M=\max(-L,U)$. Introduce continuous decision variable $w$ (to ...
- 27.3k
0
votes
Linearization the product of three variables (two binary & one continuous)
Basically you are trying the following:
$ p \le xp_{max}$: ensures $p=0$ if $x=0$, else $p$ is free,
$ p_{max}$ is upper bound of $p$
And
$ y(2z-1) \le p \le y(1-2z) $
For $ y, z$ switching I think ...
- 2,560
1
vote
Linearization the product of three variables (two binary & one continuous)
By updating the question, the mentioned conditional inequalities can be linearized by introducing new indicator variables, $z_i$, for each part and coupling those to make linearization. For example ...
- 7,281
0
votes
Accepted
how to minimize the distance to the final points with incomplete information?
Define binary $e_{i}^r,s_{i}^r$ as drop-off & pickup nodes for rider $r$.
Then assuming a rider $r$ is picked/dropped by same driver
$\sum_d(\sum_j x_{j,i}^{d,r} -\sum_jx_{i,j}^{d,r}) = e_{i}^r - ...
- 2,560
3
votes
Automatic detection of SOS variables and constraints
There has been some research on algorithmically detecting SOS structure in optimization models. One approach is to use a graph-based algorithm to identify the structure of the model and detect the ...
- 186
2
votes
How to restrict the amount of consecutive assignments
To model the constraint that limits the number of working shifts before a rest shift, you can introduce an additional binary variable to represent whether a person is on rest or not, and then use this ...
- 186
6
votes
Accepted
Linearize conditional constraint
It might help to consider the contrapositives:
\begin{align}
x=0 &\implies c\le 0 \\
x=1 &\implies c\ge 1
\end{align}
Both of these are indicator constraints, which you can linearize via big-M:...
- 27.3k
1
vote
Is there any "not bad" algorithm that can solve the minimax problem in 0/1 integer programming?
Let $I$ and $K$ be the index sets and for $i\in I$ let $K_i = \lbrace k\in K : a_{i,k}=1\rbrace.$ Hopefully $K_i \neq \emptyset\, \forall i\in I,$ else the problem is infeasible.
Since $a$ is binary, ...
- 35.5k
3
votes
Is there any "not bad" algorithm that can solve the minimax problem in 0/1 integer programming?
A greedy construction heuristic might not perform horribly here. For each $i\in I$, select the $b_{ik}$ (with $a_{ik}=1$) that increases the minimax value the least. You could process $I$ in ...
- 27.3k
0
votes
Is there any "not bad" algorithm that can solve the minimax problem in 0/1 integer programming?
If I understand your question, something like this should work:
...
- 133
1
vote
How to tackle online scheduling problems?
Take a look into Real-time planning and Non-disruptive replanning. See my video.
- 4,645
1
vote
Accepted
How to tackle online scheduling problems?
Disclaimer: I'm not a practitioner, so I don't know if any of the relevant academic literature is actually, well, relevant. That said, I think you might want to look at work on "rolling horizon&...
- 35.5k
1
vote
Fixing binary variables in an Binary Integer Program
Actually, it effectively depends on the problem you have at hand. Modern solvers have often been armed with dozen of (SOTA) heuristics, cutting plane approaches, powerful pre-solving phases, etc. Also,...
- 7,281
0
votes
Fixing binary variables in an Binary Integer Program
There are approaches like this, kind of heuristic you may say, where you can fix values of some variables like a warm start and allow the solver to start search from the given feasible candidate ...
- 2,560
1
vote
Accepted
Solver for Flexible Job Shop Scheduling Problem
There are constraint programming solvers that support global constraints specific to job scheduling (setup times, resource sharing etc.). CPOptimizer is the one with which I am most familiar, but I am ...
- 35.5k
1
vote
Any Idea why PuLP is ignoring binary variables?
Changing 'binary' to 'Binary' in the lines_selection definition gave me this in the LP file
...
- 2,560
3
votes
Any Idea why PuLP is ignoring binary variables?
Some points should be considered.
First, you defined the variable $FlowInternal_{j}$ as the slack variables on the constraints $C_2$ and $C_3$ but, forgot to limit it on the objective function. (For ...
- 7,281
4
votes
Any Idea why PuLP is ignoring binary variables?
You need to capitalize the first letter in the cat option:
...
- 1,187
3
votes
Reformulate bilinear binary constraint
If the cost $w_{p,n}$ is nonnegative, you should be able to get by with no additional variables and the following linear constraints:
$$
c_{p,n} \ge x_{p,s,i-1} + x_{n,s,i} - 1
$$
These arise from the ...
- 27.3k
0
votes
Reformulate bilinear binary constraint
If sum $\sum_{s\in S}\sum_{i \in \{1,2,3\} } x_{p,s,i-1} x_{n,s,i}$ is $\le 1$ then you can modify as
$ y_{s}\le \sum_i x_{p,s,i-1} $.
$ y_s\le \sum_i x_{n,s,i}$
$\sum_i x_{p,s,i-1}+\sum_s x_{n,s,i}\...
- 2,560
0
votes
How to restrict the amount of consecutive assignments
If aim is to restrict non consecutive shifts then
$ \sum_{j\lt k}x_{ij} \le 3+y_{i,k} \\\forall k\in S_i$
where $S_i$ is set of designated shift time for worker $i$ and shift indicator is the binary $...
- 2,560
0
votes
Reformulate this constraint optimization problem such that I do not have to divide 2 variables?
You can define a parameter $\tau_t= 1$ if tasks $t$ is from set A, -1 otherwise. In that case your $ m_{t,d}=1$ if task $t$ is assigned on day $d$, becomes a binary. you can use $ \sum_t \tau_t m_{t,d}...
- 2,560
0
votes
Reformulate this constraint optimization problem such that I do not have to divide 2 variables?
You could try implementing the condition $x * y = z$ by expanding $x$, $y$, and $z$ as binary vectors $x^b$, $y^b$,$z^b$. I.e. $\Sigma x^b = \Sigma y^b = \Sigma z^b = 1$, $z^b_{i \cdot j} >= x^b_i +...
- 133
1
vote
Converting a piecewise function to a linear equation as a constraint
For the if statements try this
$x_1-(x_2+x_3) \le w_1$
$x_2-x_3 \le w_2 $
$x_3 \le w_3 $
$ w_1 +w_2+w_3 =1$
where $w$ are binary.
$\alpha = 100w_1 +200w_2 + 300w_3 $
As question now stands I d modify ...
- 2,560
0
votes
Modelling with Gurobi-Python a Supply Chain Problem
Sample variable declaration and use in expressions or constraints\
...
- 2,560
1
vote
Modelling with Gurobi-Python a Supply Chain Problem
One possible way is by defining each part of the objective function separately and finally collecting them in an objective method. For example, suppose there are two different terms in the object as $\...
- 7,281
0
votes
Linearizing a disjunctive expression into MILP
From the modeling language point of view, the above disjunctive form can be written by CPLEX in the following form:
...
- 7,281
1
vote
Maximization problem with preferences on variables
How is this following constraint
Either
$b_z + y \le b_x+z +b_y\le x + b_z +yb_y$
Or let's break it
$b_x+z \le x + b_z$
$b_z + y \le z +b_y $
- 2,560
0
votes
Solver for quadratically constrained mixed-integer linear programs
Gurobi can solve mixed integer quadratically constrained problems provided that your known values in the quadratic constraint form positive semidefinite matrix. You'd need to use Quadratic Constraint ...
- 2,560
0
votes
Meaning difference between SUMMATION and not in the MIP model
Constr(7) is saying from every slot $s$ if any container (that's why you have summation, whenever you want to work on conditions like any/atleast) is picked up, the seaside crane's position $ x_{2t}$ ...
- 2,560
Top 50 recent answers are included
Related Tags
mixed-integer-programming × 776optimization × 173
linear-programming × 172
modeling × 160
integer-programming × 105
linearization × 91
cplex × 68
python × 59
gurobi × 59
combinatorial-optimization × 51
constraint × 47
logical-constraints × 47
scheduling × 45
binary-variable × 44
solver × 42
vehicle-routing × 32
big-m × 31
nonlinear-programming × 30
reference-request × 27
constraint-programming × 27
quadratic-programming × 23
indicator-constraints × 23
pyomo × 22
heuristics × 19
docplex × 18