Most Popular
1500 questions
9
votes
1 answer
Equivalence of formulations
I have a simple model such as:
\begin{align}\max&\quad z=X_1+X_2+X_3+X_4\\\text{s.t.}&\quad y_1+y_2+y_3+y_4=2\\&\quad X_1 \leq y_1\\&\quad X_2 \leq y_1+y_2\\&\quad X_3 \leq y_2+y_3\\&\quad X_4 \leq y_1+y_4\\&\quad x,y \in \{0,1\}.\end{align}
The…
Evren Guney
- 912
- 5
- 14
9
votes
1 answer
Integrating genetic algorithm (or other heuristic methods) with CPLEX
[Topic to discuss GA and CPLEX]
I've seen some papers trying to integrate genetic algorithm with CPLEX, such as here and here. Although they integrated both, it is done in 2 different steps; that means, they use CPLEX in one step and the results…
campioni
- 1,133
- 5
- 13
9
votes
2 answers
How can I transform this MILP into an LP problem?
I have a MILP problem with one of the constraints is given below. Sometimes, even for a small-sized problem, the solver takes a very long time to find a solution. What could be an efficient transformation into an LP or heuristic…
KGM
- 2,265
- 7
- 23
9
votes
3 answers
Interval variables in MIP
In Constraint Programming it is possible to use interval variables to represent intervals of time during which something happens (see here), usable in scheduling problems, for example.
Is there something similar in MIP? I am aware of some modeling…
Libra
- 937
- 5
- 14
9
votes
1 answer
Introducing a big M variable in given equations
While I do understand the general workings of the Big-M-method I am struggling with the following sample exercise, in which the Big-M-method has to be used to find a first feasible solution:
\begin{alignat}2\max&\quad 10x_1+4x_2\\\text{s.t.}&\quad…
John Eren
- 93
- 4
9
votes
2 answers
Implementing solvers with Object Oriented Programming
I would like to know what are some best practices in designing a solver implementation with Object Oriented Programming. We have implemented a solver with procedural programming paradigm, using python, and therefore we have data structures and…
naveen divakaran
- 113
- 7
9
votes
2 answers
Intuition behind more-for-less transportation paradox?
In this post, it was asked to describe counter intuitive results in the field of operations research.
Among the answers came up the more-for-less transportation paradox. In essence, this paradox in transportation problems occurs when it is possible…
Kuifje
- 13,324
- 1
- 23
- 56
9
votes
2 answers
Complexity of LP and MILP Problems?
My original problem is an MILP. I make it an LP by relaxing the integer variables.
Can someone please comment on the complexity, solvability and optimality of MILP and LP problems, in general?
Is there a guarantee that a given MILP can be solved…
KGM
- 2,265
- 7
- 23
9
votes
3 answers
Equipment replacement problem
I have a question on the Equipment Replacement Problem, where the following is taken (with some syntactic modifications) from IB2070 Mathematical Programming II (MP2), Warwick Business School.
Equipment Replacement Problem…
Slim Shady
- 107
- 14
9
votes
1 answer
TSP problem: traveller does not visit all nodes - Google OR-tools
Context:
I am dealing with a kind of scheduling problem, in which I have a set of tasks and machines. All tasks must be assigned to machines (not necessary all of them). In addition to that, I must calculate the cost of transferring the product…
campioni
- 1,133
- 5
- 13
9
votes
1 answer
Finding Dual Objective
I have the following simplified optimization problem:
\begin{align}\max &\quad ax+by\\\text{s.t.}&\quad0 \le x \le \overline X\\&\quad0 \le y \le\overline Y\\&\quad z = E-x+\beta\cdot y\end{align}
where $E$, $\beta$, $a$, $b$, $\overline X$ and…
S_Scouse
- 803
- 3
- 11
9
votes
2 answers
Partial derivative of LP solution $(x_1 , \ldots, x_n)$ w.r.t. $x_i$ or $a_i$
Suppose I have an optimal solution and I want to know how the solution would (likely) change if one of the coefficients in the objective function changes, or if I add a constraint that forces $x_i$ away from its optimal value.
Is there a way to…
Henry
- 542
- 2
- 7
9
votes
1 answer
Doubt on finding simplex's initial canonical tableau (II Phase)
Good day.
Given the following notation for an initial canonical tableau for a linear program in standard form:
$$
T_1 =
\begin{bmatrix}
I & B^{-1}N & \bar{x}_{B} \\
0^\intercal & \hat{x}_{N}^\intercal & -\bar{z}
\end{bmatrix}
$$
with:
$B$…
Johnny Bueti
- 253
- 2
- 5
9
votes
2 answers
How to formulate a MIP that can minimize the costs with a combination of subsets given a set?
I am trying to solve the following problem. I have a set $\{1,2,3\}$, which gives the following subsets with its costs:
$\{1\}=8$, $\{2\}=9$, $\{3\}=7$, $\{1,2\}=9$, $\{1,3\}=18$, $\{2,3\}=15$ and $\{1,2,3\}=24$.
Which combinations of subsets give…
Harry van t Kamp
- 367
- 1
- 7
9
votes
1 answer
How to tackle large nurse scheduling problem?
I have a nurse-scheduling type of problem with a time span of a year and many employees.
Formulation
My main variables are:
\begin{align}x_{e,t} &= \begin{cases}1 \text{ if employee } e \text{ is assigned to task } t \\ 0 \text{ otherwise}…
Stradivari
- 1,414
- 6
- 14