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.
1
vote
2answers
42 views
How to model iff and union statements in MILP?
I am trying to model $\{Ax\leq b\}\iff\{Bx\leq c\}$. How different is this from $\{Ax\leq b\}\wedge\{Bx\leq c\}$?
How to model with binary variables when $b$ and $c$ are $0$ vectors.
I am also trying ...
1
vote
1answer
38 views
is optimal solution of the original problem always the same as the relaxed problem Or is this just an accident?
I want to solve the following problem with GAMS software:
$ \min y+\frac{1}{0.05} \sum_s p^s u^s $
$s.t$
$\sum_{j \in V}\delta_j=b$
$\sum_{j\in W^s} x_j^s +q^s=1 \ \ \forall s\in S$
$ x_j^s \...
2
votes
1answer
49 views
mixed integer programming formulation for n jobs on m machines with preceding constraints
Suppose $n$ jobs are required to be done, $m$ equally capable machines are available, each job takes $t_i$, $i\in{1\ldots n}$ time on chosen machine (this time cannot be split into parts). Some jobs ...
2
votes
1answer
65 views
Mixed integer nonlinear programming without relaxation of integer constraints
I have a multi-objective mixed integer nonlinear problem to solve. For this particular problem the objective functions are not defined for fractional values of the integer constrained variables.
...
1
vote
0answers
32 views
MIP programming for fairness
I have a MIP model that allocates 24 rides between 6 drivers (with many constraints irrelevant here), and an important part of my objective is splitting the rides fairly.
The easiest implementation ...
1
vote
1answer
41 views
Technique to improve MIP solve time
Was on a webinar and the presenter mentioned that modelers should "slice" in certain contexts to reduce MIP solve time. The context was in sending a Minimum Cost Network Flow Problem. I believe he was ...
0
votes
1answer
27 views
complex problem turning logical conditions into linear expressions
I'm trying to add a logical condition constraint into a linear expression on puLP in python. I have translated them by myself and coded them, but the solution is infeasible, which should not be the ...
0
votes
1answer
22 views
Optimization of an objective where cost parameter takes step value
I have the following simplified optimization problem:
min $C*x$
s.t, some constraints
I want the following to be enforced as additional constraints:
$C=1$, when $0<x<=40$
$C=2$, when $40&...
0
votes
2answers
73 views
IF a == b, then c = 1, else 0. How to turn this to a linear expression? [closed]
I want to turn the following condition into a linear expression:
If a == b, then c = 1, else 0.
How should I transform this into a linear expression?
Thanks!
2
votes
2answers
35 views
Strict inequality logical implication in optimization problems
I have $ x \in \{0,1\}$ and $y \geq 0$ and I want to model that $x=1$ iff $y>0$, is this possible while keeping the constraint linear? Thanks.
One part of the implication is easy $ y \leq Mx$. The ...
1
vote
2answers
61 views
If then convex condition in mixed integer linear programming with binary variables
I have a convex polynomial $f(x_1,\dots,x_t)$ where $x_1,\dots,x_t\in\mathbb R$ and constant $a$.
If condition $$f(x_1,\dots,x_t)\leq a$$ holds I have to make variables $y_1,\dots,y_n\in\mathbb R$ ($...
0
votes
0answers
32 views
Linearise product of two integer variables for MILP
First up I'm new to this sort of task so please bare with me. I'm trying to linearise (for use in a MILP written in GAMS) the following constraint:
$$ f_{h,n} \le \beta_{n} x_{h,n} \sum_{n} C_n x_{h,...
1
vote
1answer
16 views
For a Bi-level Mixed Integer Linear Program with integer variables in the lower, can I use KKT conditions to reduce the problem to a single level?
For example, my optimization formulation looks something like this:
max $-10y-x$
s.t. $y=$ arg {min $20y-25x\leq 30;2y+x\leq 10;-y+2x\leq 15;10y+2x\geq15$}
$y$ integer
In order to convert this to ...
3
votes
1answer
48 views
How to linearize these constraints in scheduling optimization problem?
I have a mixed integer programming problem as below
$$\underset{{\bf w}_k }{\max}\sum_{k=1}^K x_k\alpha_k \log_2(1+\gamma_k)$$
subject to
$$\sum_{k=1}^K x_k||{\bf w}_k||^2_2\le P$$
$$x_k\in\{0,1\}$$
...
0
votes
0answers
31 views
Minimum number of binary integer variables to handle $AND$ and $OR$ implications in Mixed Integer Linear Programming?
Suppose I want to have an integer program for handling the cases
$(x_1>1)\wedge(x_2>1)\wedge(x_3>1)\wedge\dots\wedge(x_n>1)\implies\delta=1$
$(x_1>1)\vee(x_2>1)\vee(x_3>1)\vee\...
0
votes
1answer
57 views
What is the answer linear programming?
I am solving the following model in R and Lingo. However, I am getting an incorrect result. Do you know where my error is?
Model
minimize $10,773 * gt_1 + 30,094.7 * gt_2 + 684 * def$
subject to:
$...
0
votes
1answer
99 views
How to linearize the product of a non-binary discrete variable and a continuous variable?
Given a set $J$, I have the following constraint:
$w_j = y_j u \quad \forall j \in J$
where $y_j \in \mathbb{N}$ and $u \in \mathbb{R}⁺_0$. I would like to make this constraint linear.
Note: I am ...
1
vote
2answers
21 views
mixed integer programming - turning conditional statements into inequalities
I have if statements in my constraints and I'm having trouble turning it into an inequality problem. The statement is as following:
IF a>=x1, THEN f(x1,x2) = a+x2, Else f(x1,x2) = a.
x1 and x2 are ...
1
vote
1answer
47 views
Correctness of integer reformulation in the FICO MIP quick reference
I have stumbled upon an industry quick reference for MIP formulation by FICO:
However, after checking their writing on section 2.3 Maximum value. It seem that there are problems with their ...
1
vote
1answer
51 views
Reformulation of a Mix Integer Programming problem with both if else and min max logical constraints
I am quite new to the field of discrete optimization and currently having problem formulating the system below. This system contain both if-elseif statement and a difficult to linearize min-max ...
0
votes
0answers
37 views
How to linearize the following constraint of product of binary and continuous variable
How can I linearize a constraint that contains the product of a continuous variable and a binary variable? Is it possible to linearize it?
Thank you very much.
0
votes
0answers
21 views
mixed integer linear programming problem
Consider following mixed integer linear programming problem:
finding a parking plan for set of cars K={1,...,k} with various lengths.
parking is organized in lines P={1,...,p}, legth of a parking ...
0
votes
0answers
31 views
Mathematical Decomposition-stage-based and scenario-based
What is the difference between the two decomposition techniques? Also, how that relates to complicating variables and constraints? As far as I understand, algorithms like Bender's decomposition are ...
0
votes
1answer
44 views
MILP if then check statements?
Suppose I want to check $\forall i\in\{1,\dots,n\}\quad x_i\in\mathbb R$ if $-b\leq x_i\leq b$ then $Ax\leq c$ holds (where $x=(x_1,\dots,x_n)'$ with $'$ being transpose) is there a way to do this in ...
1
vote
1answer
48 views
Correct terminology for optimization problem
An optimization problem aims to minimize the sum of a variable u over a time-series. It is made of three variables that are in a linear relationship. Two binary variables
$$x_1, x_2, \dots x_n$$
and ...
1
vote
1answer
55 views
Conditional constraint activated by binary variables
I have the following situation in a Mixed Integer Program: $x_1, \dots, x_n$ are binary variables, and $y, z$ are continuous. If $k$ or less variables $x_i$ are set to $1$, then I need to have $y \leq ...
0
votes
1answer
27 views
What type of optimization problem is this? Ride sharing?
I am given source containers $s_1,s_2, \dots, s_n$, products $p_1, p_2, \dots, p_m$ and an assignment of which container needs to be used to make a certain product, which I represent as follows
\...
0
votes
0answers
19 views
A mixed integer programming problem
What is the integer programming complexity of this sentence?
$\exists x\in\mathcal P\quad\forall y\in\mathcal P\quad\phi(x)\leq\phi(y)$ where $\mathcal P$ is a bounded convex polytope in $\mathbb Z^{...
0
votes
1answer
12 views
Variable selection in mixed linear integer programming or mixed integer programming with convex constraints and objective
I have a binary variable $b\in\{0,1\}$ and three real variables $x,y,z$.
If $b=0$ then I want $x=y$ and if $b=1$ then I want $x=z$.
Is this possible with mixed linear integer programming?
Is this ...
0
votes
0answers
52 views
Using non-negative continuous variable to constrain binary variable
I have a problem. I am programming a mixed integer linear model. $S_{ij}$ $\in$ {$0$,$1$}. And $o_{ij}$ is a non-negative continuous variable. $o_{ij}$ lower bound is zero. where $i$ and $j$ $=1,2,3,.....
0
votes
1answer
27 views
how to model if else statement in mixed integer program
I am trying to model a if-then condition for a MIP. The MIP looks like
Maximize $\sum\limits_i H_i - C$
s.t. $\sum\limits_j x_{ij} \le D_i$ and $\sum\limits_i x_{ij} \le S_i$,
where $H_i = 1$ if $\...
0
votes
0answers
48 views
Big M Equality Constraints Question
I am a newcomer to mixed integer linear programming, and I am having some trouble using the Big M method to linearize some constraints, and was wondering if I implementing it incorrectly.
Here is ...
0
votes
0answers
12 views
A rational solution to a MILP of polynomial size
I have a question regarding the size of a rational solution to MILP. Suppose that I am given an MILP problem where all coefficients are rational numbers. I know that if the problem is feasible, then ...
0
votes
1answer
39 views
Two Mixed Integer Linear Programs (MILP) with different objectives and same constraints
There are two Mixed Integer Linear Programs. They have the same set of linear constraints constraints, but different objectives with variables $\mathbf{z}$ and $\mathbf{x}$.
The first objective is:
$...
0
votes
1answer
20 views
Number of lattices inside mixed-integer polyhedron
Given a mixed-integer polyhedron
$P = \{(x;z) \in \mathbb{R}^n \times \mathbb{Z}^d \mid A x + B z \leq c \}$
with $A \in \mathbb{Q}^{m \times n}$, $B \in \mathbb{Q}^{m \times d}$ and $c \in \mathbb{...
0
votes
2answers
52 views
Project allocation optimisation Code
I've been formulating an integer optimisation model for allocating students to projects where students give their preferences and rank them 1,2,or 3 with one being their best project preference.
...
0
votes
1answer
41 views
How to use non-binary variable in a conditional statement MILP?
I have a conditional statement I want to implement in a MILP.
$A$ is a non-binary variable that has known upper and lower bounds. $B$ is a known parameter. And $C$ is a binary variable.
How do I ...
0
votes
0answers
38 views
Assuming X = A + B * C, where A & B are integers, C is irrational; Find A & B given X & C
I'm looking for an efficient algorithm which can solve this problem. Can I do better than with the following brute force algoritm in C++?
...
1
vote
0answers
60 views
Employee Scheduling Problem MIP
I am trying to create a mathematical model for employee scheduling.
I have already got an idea on how I should model it but I do not know whether it is the best way to do it so.
Take for example a ...
0
votes
1answer
15 views
Enforce constraints in nth visited node
I have a problem similar to the tsp problem where :
$x_{i,j} \in \left\{0,1\right\}$, is 1 if I visit node $j$ immediately after node $i$.
Now suppose that I need to enforce constraints for the n-th ...
1
vote
0answers
31 views
Resource Allocation Problem
Let $I, J, n \in \mathbb N$. Furthermore, let $\mathbf M \in \mathbb N^{I \times J}$. Finally, for $i \in \{1, \dots, I\}$ and $j \in \{1, \dots, J\}$, let $M(i,j)$ denote the element in the $i$th ...
0
votes
1answer
30 views
Count the number of unique elements in a vector by linear constraints (ILP)
Let $\mathbf{x}\in \{0,1\}^n$, be the objective variables of an ILP.
Further, let $\mathbf{a} \in \mathbb{N}_{\geq 0}^n$ be a given random vector and $\mathbf{w} = \mathbf{x} \odot \mathbf{a}$ where ...
0
votes
0answers
31 views
integer programming linearization
I have two variables. $g$ is a binary variable and $s$ is a continuous variable. Goal is to linearize this $gs \geq0$ a.k.a if $s \geq 0, g = 1\:\: \text{or}\:\: s\leq0, g = 0$. How can I linearize ...
0
votes
0answers
42 views
SOS1 for linearizing complementarity condition
I am trying to linearize the complementarity condition
$0<a \perp b>0$ with SOS1 method by the following formulation:
$p_1+p_2 = 1e5 \label{1}\tag{1}$
$a < p_1\label{2}\tag{2}$
$b < ...
1
vote
1answer
31 views
Question to the solution of “Indicator Variable if x is in specific range”
This question is to query the solution provided by Erwin Kalvelagen to the post
Indicator Variable if x is in specific range
and
conditional constraint: if $x \in [a,b]=> z=1$
(Sorry for ...
0
votes
0answers
12 views
Bus fleet requirement for transporting passengers/baggage between airport terminals
I am trying to determine the optimum number of buses required for loading and unloading of passengers/baggage. The buses perform following tasks:
Transport terminating passengers and their carry on ...
1
vote
1answer
50 views
Do redundant constraints help in big-M reformulation?
I am trying to reformulate an optimisation problem with unknown $x$ of dimension $K\times 1$ into a mixed-integer program using big-M transformation.
In this respect, among my constraints, I have ...
0
votes
0answers
36 views
(Generalized) Benders Decomposition of MINLP Leads to Linear Master and Sub Problem
I have a mixed-integer nonlinear program (MINLP) which I want to apply (Generalized) Benders Decomposition (GBD) to.
The nonlinearities exclusively originate from products of first-stage decision ...
0
votes
0answers
35 views
which combination(partiotioning ) has the smallest value?
A positive integer can be partitioned, for example, the number 7 can be partitioned into the following:
$7=7$
$ 7=6+1$ , $ \ \ 7=5+2$,$ \ \ 7=4+3$
$ \ \ 7=4+2+1$,$ \ \ 7=3+3+1$,$ \ \ 7=3+2+2$,
$ \ ...
2
votes
1answer
81 views
MIQP problem slow to solve: how to rewrite it?
I am looking for suggestions on how to rewrite a MIQP problem.
Let me firstly introduce the problem
Notation:
The unknown vector is $x$ with size $(4*2+225*2)\times 1$.
We can think of the ...
