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.

Filter by
Sorted by
Tagged with
0 votes
2 answers
41 views

Conditional modelling of a binary variable based on the values of two continous variables

I want to model a binary variable $(b)$ from two continous variables $(x_{in},\:x_{out})$. These variables are $ 0\leq x_{in} \leq x_{max},\: 0\leq x_{out} \leq x_{max})$. I want the following three ...
user avatar
  • 1
0 votes
1 answer
22 views

Excel Solver Linear Optimization : Formula Debugging

I am trying to get a optimization model to work correctly. The background is to use the solver to find a circuit (AC or DC) that would minimize cost. I am trying to use binary variables so the ...
user avatar
  • 1
0 votes
1 answer
22 views

How can I convert non-linear constraint to linear one?

Problem: Suppose I have $n$ finished products and each product has its own completion time, such as C$_i$ (C$_i$=completion time of product $i$, where $i=\{1,2,...,n\}$). These products will be ...
user avatar
  • 15
1 vote
1 answer
42 views

MIP- If then with either or

I need something like this It may sound silly but I couldn't find a way to express this. x,te,ts decision variables, x bool, te,ts >=0; if $x[m,i]+x[m,j]-1 > 0$ then either $te[i]+d-ts[j]<=0$ ...
user avatar
1 vote
1 answer
15 views

Relationship between number of explored nodes and solution space for a MILP problem

I'm using CPLEX through AMPL to solve a problem using two equivalent formulations. The problem is being solved to global optimality. However, one of the formulations is faster than the other. I have ...
user avatar
1 vote
1 answer
23 views

assymetric graph coloring formulation

I'm reading this articel which is about formulating VCP to eleminate symmetric solution, they say: And then In order to eliminate some of the symmetrical solutions, they say these two constraint is ...
user avatar
0 votes
0 answers
9 views

Suboptimality of QR decomposition based integer least squares

Given a real n-by-m matrix $A$ and a real vector $y$, the integer least squares problem is to find an integer-valued vector $x$ that minimizes $\left|Ax-y\right|_2^2$. A typical solution when $A$ is ...
user avatar
  • 51
0 votes
1 answer
43 views

Formulate constraints to an Integer programming: How to algebraically formulate a geometric constraint that the colored grids must form a rectangle?

I am stuck in a constraint formulation of a discrete optimization problem. Consider a board of Cartesian grids (M rows by N columns). We are going to color some grids among them. There is a geometric ...
user avatar
4 votes
1 answer
48 views

Linearize optimization problem with absolute value

Is there any method to linearize the following optimization problem? \begin{align} \min_{x,y} &~~ c~[x; y] \\ \text{s.t.} &~~ \sum x\leq \alpha_1 \\ &~~ \sum |y|\leq \alpha_2 \\ &~~ \...
user avatar
  • 316
1 vote
0 answers
26 views

How much running time does solving a Mixed Integer Linear Program need?

Given a mixed integer linear program with $m$ constraints and $n$ variables how much time do we need to solve this? I know that MIPs like IPs are in general NP-hard. Nevertheless for IPs one can show ...
user avatar
  • 578
0 votes
1 answer
38 views

Alternate approach to formulate this MIP

This is in concern to reformulating a previously formulated set of linear equations in my previous question: This is the link \begin{align} y_i &= 1 &&\text{for $i\in\{0,n+1\}$} \tag1 \\ \...
user avatar
  • 65
0 votes
2 answers
55 views

Reformulate IF-statement in mathematical optimization

I have an optimization problem that chooses which location must be opened based on a set of possible locations. And per location we have a certain amount of available spots from which we must buy a ...
user avatar
  • 3
0 votes
1 answer
56 views

How to convert non-linear equation to linear equation [closed]

I have a problem with X machines, each one with a specific production. All the production needs to be sent to an specific place via different routes which may or may be not cheaper. I need to minimize ...
user avatar
  • 111
2 votes
1 answer
29 views

Mixed Integer Programming - variable that equals the sign of an expression

I want to define the following: y = 1 if x<=th = 0 otherwise Currently I'm doing the following: Let's say we know the lower ...
user avatar
0 votes
0 answers
31 views

Converting constraint with absolute value equation into linear programming constraint

I have following constraints, w1 = | XR1 - 20 | where w1 is a binary variable and XR1 is a nonnegative variable. How can I convert this into a linear programming ...
user avatar
3 votes
1 answer
71 views

Modeling contiguity of machine processing in a flow shop environment via a MIP

I'm working on a Mixed-Integer-Programing (MIP) formulation for a flow shop scheduling problem. One of the requirements/wishes is that for each machine $i$, processing should be contiguous, or at ...
user avatar
  • 101
2 votes
0 answers
51 views

Benders Decomposition Convergence

I have found James Murphy's "Benders, Nested Benders and Stochastic Programming: An Intuitive Introduction" (http://www.optimization-online.org/DB_FILE/2013/12/4157.pdf) to be quite helpful ...
user avatar
0 votes
0 answers
31 views

How to write elseif into linear programming

Given: If a < 0 and c < 0: d = 1 else: d = 0 I was wondering how to write it into statement of linear statement?
user avatar
  • 75
0 votes
0 answers
20 views

How to linearize the following if-then constraint with Or constraint involved?

I have the following constraint set that contain an if-then condition and or condition at the same time: $$ \eta_i = 1 \...
user avatar
  • 367
1 vote
1 answer
117 views

Linear constraint considering binary bit position

Right now, I have some binary variables for a linear programming problem: $x_1\;x_2\;x_3\;x_4\;x_5\;x_6\;x_7\;x_8$ Say these are groups of 4 bits each in this example. So: Group 1 ={$x_1\;x_2\;x_3\;...
user avatar
  • 75
0 votes
0 answers
49 views

Is there a way to minimize the standard deviation in linear programming

Here is the scenario: There are n boxes with $C_{a}$ of capacity at the beginning of each box before assigning. I want to fit x parcels into the boxes, letting the capacity left for each boxes are as ...
user avatar
0 votes
1 answer
28 views

Find a minimum threshold value for a constraint [closed]

I want to find a minimum threshold value for a constraint, such that if this constraint is satisfied, the next one must be satisfied. For example, given two inequations $f_1(X)\geq a$ and $f_2(X) \geq ...
user avatar
  • 11
2 votes
1 answer
26 views

Resources to learn about modeling within the scope of Linear/Integer programming?

I'm currently taking a course in OR, and I'm facing some major difficulties trying to formulate my LP/IP problems. I understand most of the topics just fine, but I just get lost trying to formulate ...
user avatar
  • 153
0 votes
1 answer
40 views

Clustering data using mixed integer linear programming

I am trying to understand if it is possible to use mixed integer linear programming (MILP) in order to perform a basic clustering operation to a dataset $D$. I know there exists standard algorithms ...
user avatar
  • 2,109
0 votes
0 answers
11 views

How to figure out integer variables in the relaxation set?

Suppose, there is mixed-integer programming as follows: $(1)$ $$\begin{aligned} \min&\quad c^{\top} x\\ \text{s.t.}& \quad A x \geq b \\ &\quad B x \geq d \\ &\quad x \geq 0 \\ &...
user avatar
  • 113
0 votes
1 answer
48 views

why the code assigns multiple jobs on same position on machines

scheduling n jobs on m machines, each job has a different processing time on each machine. all schedule has n positions indexed by l as l =0,1,...,n as position 0 for dummy job Used this mathematical ...
user avatar
1 vote
1 answer
44 views

Linear Programming - Job Scheduling Domain Mapping To Binary Decisions

I am trying to maximise machine profit subject to a repair plan (job schedule), but cannot seem to map between the integer domain from the job schedule to the binary domain for the revenue model in ...
user avatar
  • 11
1 vote
1 answer
57 views

The difference between subtour-elimination constraints in the symmetric and asymmetric TSP

We know that there are lots of formulations for traveling salesman problem. Some of them are based on the directed graph (asymmetric) and others are based on the undirected graph (symmetric). Also, ...
user avatar
  • 113
1 vote
0 answers
31 views

Which Python package is suitable for solving the following mixed integer optimization problem?

Assume I have given a matrix $A=\mathbb R^{d \times n}$. I want to minimize the following: $$\min \left \| \begin{bmatrix} a_{11} & \dots & a_{1n} \\ \vdots & \ddots & \vdots ...
user avatar
2 votes
1 answer
27 views

Modeling the quotient of continuous decision variable in a MIP

For a continuous decision variable $S_{i,j}\geq 0$, I would like to know the quotient of its division by some number $x$, because I need to use it in another constraint. My initial thoughts to do this ...
user avatar
  • 101
1 vote
2 answers
39 views

Mixed Integer Linear Programming problem maximizing projects but they can share resources

I need help with this optimization problem. I'm sharing a simplified version for easier discussion. For example, I have projects $x_i$ where $i=1,2,...5$. Each project has factors $a_i, b_i, c_i$ with ...
user avatar
1 vote
1 answer
40 views

How to write the following if-then condition in Mixed Integer Programming? If a<b then c=1, 0 otherwise

I am new to mixed-integer programming and I am confused about how to approach this if-then condition. How do I the following constraint in mixed-integer programming: if Dm +t < Dn + then Zmn=1, 0 ...
user avatar
2 votes
1 answer
44 views

Modeling sequence dependent setup times via a MIP for flow shop scheduling

As part of a Non-Permutation Flowshop Scheduling (NPFS) problem, I would like my MIP model to be able to deal with sequence dependent setup times. That is, for each pair of consecutive jobs, a setup ...
user avatar
  • 101
1 vote
2 answers
158 views

MIP binary variable value based on value of continuous variable

I would like to model the following constraint: $$ b = \begin{cases} 1 \quad \text{if } c=0 \\ 0 \quad \text{if } c>0 \\ \end{cases}, $$ where $b\in\{0,1\}$ and $c\in\mathbb{R}_{\...
user avatar
  • 101
0 votes
0 answers
32 views

Construct linear floorplanning constraints

This question is an extension of a previous question. Right now, what I have are these "cheap" equations. The goal is to have the floorplan allow a circle with diameter, $D$ outside the red ...
user avatar
1 vote
1 answer
41 views

Maximizing a quadratic function subject to linear constraints

Consider the problem: $$maximize: Z = x_1+2x_2$$ subject to: $$x_1+x_2 \leq 8$$ $$-x_1+2x_2 \leq 2 $$ $$x_1-x_2 \leq 4$$ I know that this problem can be solved by using Branch-and-Bound ...
user avatar
  • 77
1 vote
1 answer
32 views

Modeling some constraints

We have two decision variables $x \in \mathbb{Z}^{0+}$ that is the main decision variable and $0 \leqslant y \leqslant 1$ that is an auxiliary decision variable. Now based on the nature of the problem ...
user avatar
0 votes
0 answers
22 views

Show that incidence vectors of s-t paths are the extreme points

Given a directed graph $G=(V,A)$, let $(U, \bar{U})$ be any partition of the vertices such that $s \in U$ and and $t \in \bar{U}$. Such set of $s-t$ arcs where $s$ and $t$ are tail and head, ...
user avatar
  • 180
2 votes
1 answer
41 views

Fixing a minimal number of variables in linear programming problem to worsen objective

Consider a fairly standard linear program with $A\in \mathbb{R}^{m\times n}$ and cost vector $c\in \mathbb{R}^n_{\geq 0}$ such that $\begin{align*}\text{maximize}&& c^Tx\\\text{such that} &...
user avatar
2 votes
3 answers
180 views

Linearization of product of a continuous and a discrete variable

From my previous questions, I have a variable : $Q$, which is function of a discrete known vector, $P$ and a binary variable $x$ : $Q=f(P,x)$. I know, we can linearize the products of (a) two / ...
user avatar
  • 65
0 votes
0 answers
73 views

Want to form the linear equations for conditions given below: [duplicate]

I want to formulate the set of linear equations for the following conditions: $Q(i) = 0$ if $y(i)=1$ for $i = 1,2,...,n$ $Q(i) = P(i)$, if $\sum_{j=1}^{n}{y(j)}=0$ for $j \le i$. $Q(i) = P(i-r)$, if $...
user avatar
  • 65
1 vote
1 answer
204 views

I want help in formulating a mixed integer linear problem formulation

I want the following help in linear fashion (In my previous question, I asked the same but the solution was not generic. Please check it : Prev.Question). I have an arbitrary vector: $P(n) = [1, 2, 3,...
user avatar
  • 65
1 vote
1 answer
113 views

How to translate minimization problem containing a min function into a Mixed Integer Problem (MIP)?

I have the following optimization problem: $\min J = \sum_{i=0}^{N} k_i = k_0 + k_1 +\dots+ k_N$ s.t: $k_i = f_i(z_i)$ where $f_i(x) = \begin{cases} x,& \text{if } x\leq P_i\\ P_i, ...
user avatar
1 vote
1 answer
31 views

Choosing optimal intervals

I have two list of numbers of size N. For example, say N=6, x=[1, 3, 5, 10, 15, 20] and y=[1.5, 3.5, 4.7, 9, 12, 18]. I would ...
user avatar
  • 13
0 votes
1 answer
40 views

Optimization problem using MIP

I am trying to solve the following mixed integer programming problem. However, I have any problems with the approach of the model. Problem: A company that sells athletic shoes aims to make the ...
user avatar
0 votes
0 answers
41 views

How would I represent the following constraint in the linear form?

Given the optimization variables $\mathbf{a}, \mathbf{b} \in \mathbb{C}^{n}$ and $\mathbf{y} \in \mathbb{R}^{n}$, I would like to represent the following constraint to the linear form $\mathrm{diag}(\...
user avatar
3 votes
2 answers
143 views

Select five vectors that upon undergoing elementwise multiplication are most similar to another vector

I have a sparse $60000\times10000$ matrix where each element is either a $1$ or $0$ as follows. $$M=\begin{bmatrix}1 & 0 & 1 & \cdots & 1 \\1 & 1 & 0 & \cdots & 1 \\0 &...
user avatar
0 votes
1 answer
126 views

What are Bounds in Branch Bound

I am looking at a video to understand branch and bound more. Specifically, the one found at this link: (21) Ch06-03 Branch and Bound Method (B&B) - YouTube. I have two questions: Around 9:44, I'm ...
user avatar
0 votes
1 answer
107 views

Converting a basic MILP into LP

I have a MILP looks like following: $$ min \sum_i capacity[i] * weight[i] $$ where i=[Mid_North_1, Mid_North_2, North_Mid_1, North_Mid_2] Basically I got 2 sites ...
user avatar
  • 125
0 votes
1 answer
91 views

one way conditional statement in binary variable linearization

I am trying to write a one-way conditional statemen with binary variables. my condition is (x and y are both binary variables) (if x=1 then y=0) and it is the only ...
user avatar

1
2 3 4 5
7