Stack Exchange Network

Stack Exchange network consists of 175 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.

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 ...