Questions tagged [mixed-integer-programming]
A mixed-integer programming (MIP) problem is a linear program where some of the decision variables are constrained to take integer values.
234
questions
-1
votes
1answer
9 views
How to solve mixed integer programming problems with multiple varibles in one inequality?
Below I need to find the optimal results of $y_i$ and $x_{ij}$, where $a_i$,$b_{ij}$ and $c_i$ are constant numbers. $x_{ij}$ and $y_i$ are binary variables, while $v_i$ and $z_i$ are allowed to be ...
0
votes
0answers
18 views
Solve Constrained zero-one Integer Linear Program Using Simulated Annealing
Recently, I was reading about several techniques that solves Unconstrained Mixed Integer Linear Programs (UM-ILP) using a meta-heuristic algorithm called simulated annealing. I was thinking about the ...
0
votes
1answer
20 views
Integer programming : linearize product of constants given conditions
I have some constant values $c_i$ in $(0.5, 2)$.
I also have binary variables $x_i$. For my integer program, for a particular constraint, I need to multiply only those $c_i$ when $x_i$ takes the value ...
0
votes
1answer
22 views
Boundary point in MIP using inclusive inequality?
I want to write if-else condition in linear programming and the only method I can think of is using MIP.
I have to write a binary variable called b so that
...
0
votes
0answers
23 views
Does this fall into a typical optimization problem? (Knapsack??)
MOVED TO OR STACK
I am struggling to find a representative problem formulation for this optimization challenge. I have implemented a MILP in Matlab, but the run time is taking more then a day. My ...
1
vote
0answers
12 views
Need help formulating an event scheduling problem involving multiple clients and class types
I run training classes. A "B" class, a "C" class and an "Adv" advanced class.
B classes run every saturday, take 3 hours, and have a maximum 4 clients.
C classes follow B classes and take 2 hours. ...
0
votes
1answer
33 views
Explanation of branch-and-cut method in solving MIP.
I'm reading about the branch and cut algorithm to solve a mixed-integer programming problem. The interface and the steps of the algorithm are as follow:
The extreme ray $e^*$, if exists, is from the ...
0
votes
2answers
33 views
Division in linear program
In my linear program, I have an inequality constraint as follows.
$$ x + \frac{y}{g(z)} \leq c $$ where $x \in \mathbf{R}^+, y \in \{0, 1\}$, and $g(z)$ is a function of $z \in \mathbf{Z}_{\geq 0}$ ...
1
vote
1answer
29 views
Linear program decomposition and Column Generation
I needed to decompose a large LP of equality constraints.
$\\Dx=B^1,$
$\\Ax=B^2,$
$\\D \in R^{m^{(1)} \times n} $
$\\A\in R^{m^{(2)} \times n}, m<<n$
$A$ has a block diagonal structure and $D$ ...
1
vote
1answer
35 views
Choosing Variable to generate a Node in a MILP
I'm trying to find or understand rigorous a criterion about choosing the variable to generate a new Node in the Branch and Bound method.
Usually the methods I've seen just choose the variable nearly ...
0
votes
1answer
22 views
The existence of an optimal solution in a MILP guarantees existence of the optimal solution in the relaxation problem?
I'm following a description of the Branch and Bound Method.
But I don't understand at all, that if you assume a MILP problem has an optimal solution it implies that the relaxation problem has also ...
0
votes
1answer
19 views
Integer program for minimizing maximum Lateness with precedence constraints
In studying for an upcoming exam the following problem came up:
Write an integer program to: minimize the maximum Lateness for the one machine scheduling problem with precedence constraints and ...
0
votes
1answer
35 views
Reformulation of min constraints with binary decision variable inside the min()?
I am trying to reformulate a mix integer problem with a binary decision variable lies within the min constraint.
That is ${x_1} = \min \left( {c,\frac{d}{\alpha }} \right)$ where $c$ and $d$ are two ...
0
votes
1answer
23 views
How to model grouping constraint in Knapsack problem?
I would like to add a new constraint to a standard Knapsack problem by introducing groups.
My variables are $x_c \in \mathbb{Z}^+, c\in \mathbb{C}$. Where $\mathbb{C}$ is the set of all items. Each ...
1
vote
2answers
36 views
How to linearize $\min\{\max\{0,x\},y\}$ as constraint in MILP?
I am formulating a MILP and one of the constraints is
$\min\{\max\{0,y-x+a\},b\} \leq c$.
with decision variables $x, y \geq 0$ and $a,b,c$ as constants.
How would I ideally introduce auxiliary ...
1
vote
1answer
28 views
Optimizing cost function dependant on sum of decision variables
I am trying to model $M$ sellers offering $N$ items at different prices. Each seller charges a different amount of shipping depending on how many items are purchased from them. For example, seller $...
0
votes
0answers
42 views
While solving a MILP via subsequent Linear Relaxations are relaxed Indicator variables and constraints still useful to guide the objective function?
I have a multi objective Mixed Quadratic binary non-linear problem.
Following a scalarization approach, the objective function includes the sum of some binary variables (say Z_j) minus lambda times ...
1
vote
0answers
9 views
How to define the fog-based vehicular network?
I'm trying to create a fog-based graph which describes as follows:
The fog-based vehicular network consisting of sets of RSUs, fog nodes, and vehicles, as depicted in the below. The vehicular network ...
1
vote
1answer
28 views
Problem with big-M logical constraints
Consider a linear optimization problem with two variables $u_1, u_2$:
$$\begin{array}{rl}
\max_{u_1, u_2} & k_1 u_1 + k_2 u_2\\
\text{s.t.}\\
& 0 \leq u_1 \leq a_1\\
& 0 \leq u_2 \leq a_2
...
0
votes
1answer
86 views
MIP with conditional constraints
Sorry in advance, for the length of my question and if something seems vague, but this is my first question ever.
Here I got a MIP I tried to solve and is formulated as:
A set of binary decision ...
-1
votes
1answer
180 views
How to write if else statement in Mixed Integer Programming? [closed]
I posted a similar question earlier here
How to write the following if-else condition in Linear/MI Programming?
If $a = b$ then
$c = d$
else
$c = e$
$a,b,c,d,e$ all are variables. How can we ...
1
vote
1answer
47 views
How to write a Mixed Integer program for a streak?
I have a list x(variable in MIP) of outcomes.
x = [1,-1,-1,-1,1,1,-1,1,1,1,1,-1,1,-1,-1,1]
1 represent a win and -1 represent a loss. In this case the max winning streak is 4 and max losing streak ...
0
votes
1answer
16 views
How to include safety distance in only one direction, when solving a facility layout problem using a mixed-integer programming approach?
I'm trying to design an office using a mixed-integer programming approach, but I'm having some trouble.
Task: Place a fixed number of rectangular shaped tables in a rectangular shaped room. If we ...
1
vote
1answer
22 views
Total Unimodularity of set of equality and inequality constraints by partitioning of rows
Consider binary decision variables $x_{ij}$ and $y_j$ where $ i \in \{1,2,\ldots,I\}$ and $ j \in \{1,2,\ldots,J\}$ for fixed integers $I$ and $J$. Consider the following feasibility prolem:
\begin{...
1
vote
1answer
77 views
Taylor approximation to multiplication of two 0-1 variables
Let $Z$ and $Y$ be two 0-1 decision variables.
Is there any way to approximate the following term using Taylor approximation or any other approximations?
$$\sum_w \sum_s \sum_b \left(Z_{wbr}^s \...
1
vote
0answers
39 views
Mixed integer linear programs determined by their continuous variables
What is known about mixed integer linear programs of the form
$$
\begin{array}{rll}
\max & c^T \mathbf{x} + d^T \mathbf{y} & \\
\text{subject to:} & a_i^T \mathbf{x} + b_i^T \mathbf{y} \...
1
vote
1answer
35 views
Minimize the number of non-zero rows
I am trying to formulate a shipping problem as a mathematical optimization one, and I'm having some trouble determining my optimization objective (cost function). Without getting too far into the ...
1
vote
1answer
36 views
How to use binary variables to satisfy if/then linear constraints
I am trying to solve the constraint $c$ where:
$$c=\begin{cases}
50\sigma & \text{if $\sigma < 0$},\\
150\sigma & \text{if $\sigma \geq 0$}.
\end{cases}
$$
I know I need ...
-1
votes
1answer
21 views
MILP exclude previous combinations of solutions
I'm trying to formulate a MILP with a variant of the standard integer cuts constraint (which excludes previously found integer solutions) by avoiding previously found combination of solutions.
For ...
1
vote
1answer
24 views
Algorithms to optimize over an interval union a singleton.
Sorry for the simple question, but my Google skills were not enough. I have a large optimization problem and I would like to add constraints of the following kind:
$$ x \in \{ 0 \} \cup [c, \infty) $$...
0
votes
2answers
40 views
Integer programming - non-linear objective function with min operator?
The goal is to maximize the objective function, where the decision variable is the vector x = [x,y,z]. It is a binary integer problem (i.e: x,y,z can only take values of 0 or 1). See image for full ...
0
votes
0answers
42 views
How to linearize the product of binary variables?
I have the following equation that I need to linearize for an integer programming problem,
$s_i$ = $x_{i-1}$*$y_i$
where $s,x,y$ are binary
and $i ā ${1,2,3,4,5,6}
I've noticed that there is a ...
1
vote
1answer
30 views
Formulating linear (or perhaps non-linear) program to fix variables across one dimension
I have been working with linear programs for a few years now but have no formal mathematics training, so hoping for some help with formulating a problem. I think its non-linear but want to be sure.
I ...
0
votes
0answers
28 views
Closest Vector Problem in the 1-Norm. Mixed-Integer Linear Programming Formulation
So I understand the closest vector problem in the infinity-norm and getting to the final step of the program where I have:
Minimize z
Subject to z >= xj - tj for j = 1,2,...,n
z >= tj - ...
0
votes
0answers
55 views
How can I write this in proper mathematical equation?
I'm working on an optimization problem, but I'm not sure how to write this constraint correctly.
I have several servers (e.g., S1, S2, S3, S4...) and some Virtual Network Functions (e.g., V1, V2, V3....
1
vote
1answer
37 views
MIP/LP - Modelling āif distance(i,j)<=e then x=1ā constraint
I want to add a constraint to my model that works like this:
if distance(i,j)<=e then x=1
The distance(i,j) is calculated based on euclidean distance between a determined point and an ...
2
votes
1answer
72 views
Doing a Charnes-Cooper transformation with matrices and an zero-one constraint
I need to solve an assignment problem with the following objective function:
$${\max} \frac{\displaystyle\sum_{i=1}^m\sum_{j=1}^n h_{ij}\cdot x_{ij}}{\displaystyle\sum_{i=1}^m\sum_{j=1}^n c_{ij}\cdot ...
1
vote
1answer
122 views
Find pairs of linearly associated linear combinations
I am trying to figure out if the following problem can be formulated using linear or quadratic programming:
consider a set of $n$ normalized vectors $V = \{V_1,..,V_n\}$ with $V_i \in \mathbb{R}^d$. ...
0
votes
1answer
26 views
Solving a particular Integer Programming Problem
Integer Programming formulation described as follows:
Assume a set of variable $V$ = ${v_1,...,v_m}$.
The set of total $S$ constraints is of the form:
$$v_1 + \overline{v_2} + v_3 \leq 1 \\
....
2
votes
1answer
99 views
Convert a Non-Linear Constraint of Integer and continuous variables to a Linear Constraint for programming
I have nonlinear constraints:
\begin{equation}
\sum_{i} \dfrac{X_{ij}^{t}}{r_{ij}} \le T_{disp1} * w_{t} * NN_{j}^{t} * \overline{\mu}_{j} \quad \forall j \ ,\ t
\end{equation}
\begin{equation}
O_{...
1
vote
1answer
29 views
Is this a valid mathematical model (MILP)?
Is it ok to calculate values in one set of constraint and than using it for another in MILP model. Here Z and Y are binary variable.
1
vote
1answer
36 views
Mixed Integer Implementation
I have a problem where I want to optimize a path while performing obstacle avoidance in a known map like the following:
Representing the hiperplanes as $h_i x\leq k_i$ but I need to put into the ...
0
votes
0answers
15 views
Speedup or Caching for a Multi-Iteration Boolean MIP problem
I'm solving a MIP:
\begin{align}
\mathrm{arg\,min}&\quad\sum\limits_{i}{x_i}\\
\text{s.t.}&\quad A\,x\geq1,\\
&\quad A_{ij}\in\{0,1\}, \\
&\quad x_{i}\in\{0,1\}, \; i,j \in \{1..N\}
\...
1
vote
0answers
39 views
Local branching in Benders Decomposition
I am trying to understand how local branching is used in Benders Decomposition. I was wondering if someone could kindly explain me how exactly local branching works.
If my understanding is correct, ...
0
votes
0answers
30 views
Solution of Lagrange relaxation of problem does not converge to optimal
I am trying to solve the MILP problem using Lagrange relaxation with subgradient method. I am following the approach described in here: http://www.cs.uleth.ca/~benkoczi/OR/read/lagrange-relax-...
0
votes
1answer
24 views
MILP solve for A and b
I have a nurse scheduling problem that I'm trying to solve and it works as advertised right now. The objective function currently is trying to maximize the reward for scheduling individuals and the ...
0
votes
0answers
31 views
Re-weighted regularized linear least squares for integer programming?
Say I have a vector of integers ${\bf a} = [a_1,\cdots,a_N]^T$ and an optimizations problem I would like to find a solution (or approximation) in this set.
Assume for every number, a probability ...
0
votes
1answer
37 views
Maximisation of the absolute value of a linear function subject to bound constraints: Am I wrong?
I have the following optimisation problem:
$\max |a_0 + a_1x_1 + \dots + a_nx_n |$
subject to bound constraints
$\mathbf{b}_l \leq \mathbf{x} \leq \mathbf{b}_u.$
According to this previous post ...
0
votes
0answers
22 views
Mixed Integer non convex optimization problem
I have a question regarding mixed integer non convex optimization problem. The solution of the problem through brute force exhaustive search method is impractical as it has very high complexity. Can ...
0
votes
0answers
94 views
How do I formulate this integer programming question on excel?
Triangle Utilities provides electricity for three cities. The company has four electric generators that are used to provide electricity. The main generator operates 24 hours per day, with an ...
