Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
0answers
10 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
0answers
46 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
16 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
29 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
10 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
35 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
35 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
28 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
35 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++? ...
0
votes
0answers
27 views

Mathematical set notation translation to AMPL/MILP code?

I am trying to run a model from an existing paper with the following mathematical model: and the following decision variables: I am unfamiliar with set notation and have tried to understand it, but ...
1
vote
0answers
46 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
21 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
23 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
26 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
39 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
26 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
36 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
21 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
33 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
67 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 ...
0
votes
1answer
27 views

How do you set up this constraint in integer programming using binary variables?

Mike wants to invest in $X_1$ if and only if he invests into $X_2$ or $X_3$ or both. Please help i can't get my head around this Thanks
0
votes
1answer
46 views

Rewrite $[p_1(x)\geq 0 \text{ and } p_2(x)\geq 0] \Rightarrow q(x)\geq 0$, $[-p_1(x)\geq 0 \text{ and } -p_2(x)\geq 0] \Rightarrow q(x)\geq 0$

I am trying to reformulate an optimisation problem with unknown $x$ into a mixed-integer program. In this respect, I would like your help to rewrite the following constraints $$ \begin{cases} p_1(x)\...
1
vote
1answer
74 views

Rewrite the constraint $ p(x)=0 \Rightarrow q(x)=0 $ in an optimization problem

I am trying to reformulate an optimisation problem with unknown $x$ into a mixed-integer program. In this respect, I would like your help to rewrite the following constraint $$ p(x)=0 \Rightarrow q(x)=...
0
votes
0answers
16 views

How can i make refrigerator operations should be sequential?.

I am working on the appliance scheduling problem, tried to create the constraint that imposes the refrigerator tasks should be run sequentially. I have a binary variable $x_{t, u, i, j}$ is 1 if task ...
0
votes
0answers
10 views

How to model and formulate this optimization problem on clustering?

I have a system with 72 nodes. I have a binary adjacency matrix $S$ of size $72\times 72$. If $S_{i,j}=1$, then node $I$ is adjacent to node $j$. So, we also have $S_{i,j}=S{j,i}$. So, $S$ is a ...
4
votes
2answers
94 views

How to prove that 1/3 is the optimal solution for the muffin problem with 5 students and 7 muffins?

The Muffin Problem Definition Let there be $m$ muffins and $s$ students. The problem is to divide the muffins into pieces where every student gets exactly $\frac m s$ muffin, such that the size of ...
0
votes
2answers
84 views

MILP: Minimizing $|Ax-b|$ with at most 5 x variables being non-zero

I have a $m \times n$ matrix $A$, where $n$ is very large and $ n>m$ (underdetermined), and $b$ is $m \times 1$ matrix. I want to minimize $|Ax-b|$, but at most $5$ $x_i$ can be non-zero. Other ...
0
votes
1answer
27 views

Forcing a series of OR statements in ILP Problem

I am attempting to solve an ILP program in relation to maximizing the return on investments. There are 10 decision variables, $x_1, x_2, ...,x_{10}$, with the following goals: Max $0.067x_1 + ...+0....
3
votes
1answer
38 views

Transportation problem with the least number of transportations.

I have a non trivial case of transportational problem. Let me get you familiar with it. We have $n$ suppliers $a_1, ..., a_n$ and $m$ consumers $b_1, ..., b_m$. The suppliers volume of goods to ...
1
vote
1answer
37 views

Solving an integer (boolean) constraint satisfaction problem

I have a 0-1 integer constraint satisfaction problem of the following form: find binary vectors $x = (x_1,\dots,x_m) \in \{0,1\}^m$ and $y = (y_1, \dots,y_n) \in \{0,1\}^n$ that satisfy the ...
0
votes
1answer
33 views

binary quadratic mixed integer nonlinear programming to inequalities

I have this unconstrained z=x.y where x,y are 0-1 integers. How to reformulate that into set of mixed integer linear inequalities with exactly the same feasible region?
0
votes
1answer
67 views

How to count occurrences in linear programming

This is an integer linear programming question. Let $L$, $T$, and $R$ be positive integer values and define the sets $\mathscr{L} = \{1,2,\ldots,L\}$, $\mathscr{T} = \{1,2,\ldots,T\}$ and $\mathscr{R}...
1
vote
1answer
45 views

Why adding a few rows of constraints can dramatically slow down the running time of MIP optimization?

I am working on a linear mixed-integer programming (MIP) optimization problem. Let's say the constraint can be denoted as $Ax\leq b$, where A is the constraint matrix. Previously, A has a dimension ...
1
vote
1answer
46 views

Modeling an optimization problem as linear programming problem

Attempt: First, I call $x$ be the number of shafts produced per year and $y$ the number of frames produced per year. We have that each machine works at most $4500$ hours. we can place all of our data ...
-1
votes
1answer
37 views

Reducing data sparsity in linear integer programming

I have following decision variables and constrains in my ILP model. Resolution time of CPLEX solver grows exponentially with respect to problem space getting larger. Is that solely because 4D matrix ...
1
vote
1answer
34 views

How to create constraints for Mixed integer linear problem?

i am a beginner to Discrete optimization domain. I am working on the real world problem, i.e., Scheduling of hybrid appliances. I have hybrid appliances which can ...
0
votes
1answer
124 views

Linearization of product of three variables

Let $h=xyz$, where $x,y \in \{0,1\}$ and $z \in [0,T]$ with $T>0$ being a constant. Is there any method that can linearize $h=xyz$? For example, if $h=xy$ the method in here can be used to ...
0
votes
0answers
40 views

Graph Clustering - Capacitated VRP on a MultiDiGraph

I'm working on the problem of the CVRP on a Multi Directed non-complete graph that has been extracted from OpenStreetMaps using OSMnx. In the extracted graph I have also 'flagged' several delivery ...
0
votes
0answers
38 views

Convert the following model to quadratic integer programming

Really having a hard time with this.....Convert the following model to a quadratic integer program: Maximize $Ay$ subject to $Bx \leq d$ and $y\in$ argmax $x^TMy.$ Does anyone have any idea? Or ...
0
votes
1answer
54 views

Convert fractional to quadratic integer programming

Maximize $\frac{\sum_i\sum_ja_{ij}x_iy_j}{(\sum_ix_i)(\sum_jy_j)}+ \frac{\sum_i\sum_jb_{ij}x_iz_j}{(\sum_ix_i)(\sum_jz_j)}$, subject to $Ax+By+Cz \leq d, \quad x,y,z\in \{0,1\}$. Can we convert the ...
0
votes
0answers
44 views

Adding to the objective the absolute differences of numbers that are multiples of decision variables in mixed integer programming

I am trying for formulate a mixed integer program that optimizes the cost of transferring water through three piping systems. I have three tanks $S_i$, $i= 1,2,3$. Each tank $S_i$ has $5$ pipes ($j=...
0
votes
1answer
50 views

Convex constraint in a Mixed-Integer Program

I have an optimization with the following convex constraint: \begin{equation*} x_1^2+x_2^2\leq \textrm{C}_1\cdot x_3 + \textrm{C}_2\\ \end{equation*} My problem also contains some integer variables (...
1
vote
1answer
46 views

Is the LP-relaxation value on a subset of variables a bound for that subsets value in the MIP solution?

Say we're given the following integer problem: $\min c^Tx$ s.t $Ax \leq b$ $x \in \{0,1\}^n$ and its corresponding LP-relaxation: $\min c^Tx$ s.t $Ax \leq b$ $x \in [0,1]^n$ Then we can ...
0
votes
2answers
129 views

How to add integer cut to MILP constraints to find alternative optimal solutions?

I am solving an MILP optimization with binary variables in MATLAB in which I want to find more than one optimal solution by excluding previous solutions. Therefore, I know I must include the following ...
0
votes
1answer
37 views

Coping with $y = \text{max}\{b-x,0\}$ in constraint for MILP

Problem Description: I have a mixed integer linear optimization problem (MILP) with objective function $$\min_{x_{jt}} \sum_\omega \sum_j \sum_t y_{jt}(\omega)$$ I know $L_{jt}\le x_{jt}\le U_{jt}$ ...
3
votes
1answer
42 views

dual of sub problem is infeasible, What should we do?

i have this problem \begin{equation} \begin{split} \min &\; c^Tx + b^Ty\\ s.t. & \; Ax \ge d\\ & \; Bx +Dy \ge h\\ & \; y\ge0, x\in\mathbb{X} \end{split} \label{OP} \end{equation} i ...
2
votes
0answers
104 views

Benders Decomposition Type of Optimality Cut

In Bender's decomposition we use optimality cuts. An optimality cut is $\pi^T (h-Bx)\leq\phi$ or $b^Ty'+\pi^T (x-\hat x)\leq\phi$, depending on the subproblem. I read in the book that both cuts ...