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.
294
questions
0
votes
1answer
24 views
Relaxation of the binary optimization problem doesn't make sense in terms of the original problem - how do I repose the model to make sense?
Suppose I have a set of binary variables $x\in \{0,1\}^N$,
where in the context of my optimization problem these binary parameters mean to include the parameter in a model or not include it, where ...
2
votes
1answer
27 views
Minmax combinatorial optimization with target set size constraint
I have a combinatorial optimization problem whose objective is in the "min-max" form.
Suppose that there is a row stochastic matrix $P=[p_1^T,\cdots,p_n^T]^T\in\mathbb{R}^{n\times n}$ whose ...
1
vote
1answer
26 views
Reformulate indicator function using mixed integer program
Consider the following constraint: $$ \sum_i I(a_i x \leq b) \leq m. $$
Can we reformulate this constraint using big-M constraint?
A similar question can be found in Involving indicator function as a ...
3
votes
2answers
109 views
Changing a model in to a mixed integer linear programing model
Trying to learn about integer programming in quarantine and I've come across a problem that stumped me. I searched the net but couldn't see anything similar and would appreciate another set of eyes on ...
0
votes
2answers
48 views
What objective function I should consider?
Given an undirected graph $G=(V,E), the Vertex Coloring Problem (VCP) requires to assign a color to each vertex in such a way that colors on adjacent vertices are different and the number of colors ...
0
votes
0answers
38 views
Where can I find good practices on building models for optimization?
I am sort of new to mathematical optimization and have to build some fairly complicated models for my thesis. I was wondering where I could find literature to help me develop more efficient versions ...
0
votes
0answers
22 views
Formal robustness verification of neural networks: MILP vs SMT
I'm not sure if this is the right place to ask this questions.
I'm working my way into the field of formal verification of neural networks. The goal is to analytically evaluate the robustness of ...
0
votes
0answers
28 views
How to write the KKT condition?
$Min f=\sum\limits_{t\in T\text{}}{\left[ \lambda _{grid,t}^{WM,P}p_{grid,t}^{WM}+k\left( 1-{{v}_{it}} \right) \right.}$
${{v}_{i,t}}-{{v}_{j,t}}\le {{\tilde{z}}_{ij}}s_{ij,t}^{*}+\tilde{z}_{ij}^{*}{{...
0
votes
1answer
46 views
How to enforce graph continuity constraint?
I am working on a single source multiple destinations problem formulation using MILP. The network I have designed is as shown in the figure below Graph Network. The objective function is to minimize ...
1
vote
0answers
19 views
Assignment problem with batching costs
I am studying an assignment problem with batching costs, and I would like to know if there is a standard name or algorithm for this problem. I know this problem can be formulated as mixed-integer ...
0
votes
1answer
53 views
What will be an efficient joint clustering solution to this problem?
There is a system with $S$ transmitters/service points, $U$ subscribers/users.
The link quality/gain between any transmitter indexed by $s$ and a user indexed with $u$ is denoted by $h_{u,s}$.
Any ...
0
votes
0answers
27 views
Proving that an inequality is a split inequality (in cutting plane, Integer Programming)
As I know, to prove if a given inequality is a split inequality or not, we need to find $\pi$ and $\pi_0$ such that $πx ≤ π_0$ and $πx ≥ π_0 +1$ and the given inequality must be valid for both $Π_1$ ...
1
vote
1answer
65 views
Making a variable in a linear program be equal to a ramp function
In a linear program, I have a variable $y$ that must obey $y=\max(x-a,0)$ where $x$ is a linear combination of the other variables and $a$ is a constant. $x$ and $y$ and $a$ are always non-negative.
...
2
votes
1answer
37 views
Conditional constraint activated by binary variable [closed]
For each time step $t$, $T_1(t),...,T_n(t)$ are continuous variables, $z(t)$ are binary variables. $T_c(t)$ is known. I am trying to express the following constraint in a Linear Programm.
$$
T_i(t+1) =...
1
vote
1answer
24 views
Using strict inequalities for constraints in linear programming
I started to work a bit with linear programming methods and would like to know why we can't use strict inequalities in our constraints, i.e., why is the equivalence in constraints excluded?
What can I ...
1
vote
1answer
45 views
Why does the simplex algorithm not accept negative decision variables?
I would like to know why the Simplex algorithm does not accept negative decision variables? I read this article on Wikipedia but couldn't find a satisfying answer.
0
votes
0answers
39 views
Mixed Integer Programming - Model Formulation for A Resource Allocation Problem
Crossposted at Stack Overflow and Operations Research SE
There are a number of orders, which needs to be shipped. For each order, there may be 1 to 3 route options. The problem here is to find out ...
0
votes
1answer
17 views
linear program formulation discontinuous function
I have the following discontinuous function:
$f(x) = 10 $ if $x = 0$ or $f(x) = 5 + 8x $ if $x > 0$ where $ x \in [0,30]$
I'd like to formulate as a bilinear program using binary variables but I am ...
0
votes
0answers
25 views
How can I compute the number of solutions to an under-constrained equation over some integers?
I have system of under-constrained equations over a fixed set of integers, defined as follows, how can I find the number of solutions to this problem? A computational reference will do (in-fact ...
0
votes
0answers
6 views
Modeling that there is no feasible solution to a linear system in mixed integer programming
My question is about how to construct a mixed integer programming to model that there is no feasible solution to a given linear system. Specifically, given $x\in \mathbb{R}^{n}$ and $z\in \{0,1\}^{d}$,...
0
votes
1answer
10 views
MIP modelling of piecewise linear function
Suppose we have the following piecewise linear function $f(x)$:
$3x + 8, x\in [0,5]$
$33 - 2x, x\in [5,10]$
$3 + x, x\in [10,20]$
How to model the relations between $f(x)$ and $x$ using ...
0
votes
1answer
23 views
Integer programming formulation for the entire region of a triangle except the region of a rectangle inside it
Suppose we have a triangle-shaped region such as:
$x-y\ge0$
$x+y\le8$
$x,y\ge0$ and integers
How to write an IP formulation to describe all real points inside this triangle except the points inside ...
0
votes
1answer
25 views
How to write a constraint for time bound binary integers?
In these constraints $u_{g,t}^G$ is on at t=1, then $u_{g,t}^{G,start}$ should become 1 after $t_g^{G,start}$ time-steps then after it stays 1 for $t_g^{G,cr}$ time-steps then $u_{g,t}^{G,on}$ ...
0
votes
0answers
38 views
How to solve the mixed integer continuous programming problem?
We have a mixed integer continuous programming problem that described in the follow,
$$\max\limits_{\left\{\kappa_{k},\mathbf{w}_{k}\right\}} \left\|\mathbf{\kappa}\right\|_{0}$$
$$\mathrm{s.t.}~\...
1
vote
1answer
28 views
MILP formulation of constraint
I'm very new to MILP, and I'm testing python-mip.
I'm trying to model a simple power distribution system with some constraints, but I'm stuck....
I want to find a valid power balance between a device, ...
0
votes
1answer
26 views
'Weird' Indexing In The MILP Literature
Fairly new to MILP. I posted this question as an issue on the Gurobi examples repo too, but it might be more appropriate to ask it here.
NOTE: Since I "need at least 10 reputation to post images&...
2
votes
1answer
62 views
Solving a system of piecewise linear equations with multiple variables in minimum function
General problem
I am facing a problem from the transportation field. For a given network, the maximum flow $q$ on a link is either the sum of the flows from upstream links, entering at the upstream ...
1
vote
0answers
86 views
Column Generation?
I implemented a method to solve a large integer program but am not sure how its called.
The idea is the same as column generation, just less explicit.
Take the following problem as a simple example (...
-1
votes
1answer
20 views
Valid inequality with chvatal gomory for problem with binary variables
I am not able to find a valid inequality with chvatal gomory for my problem that increases the value of the relaxed problem.
My problem:
Determine the optimal allocation of n workers to m machines in ...
2
votes
0answers
33 views
Integer solutions to a large sparse equation
How might one find integer solutions to:
$$
\textrm{diag}(x)Ax = Bx
$$
$A$ and $B$ are integer-valued, square, non-invertible, sparse, and large. The values of $x$ should be $0$ or $1$ (ideally; ...
1
vote
1answer
60 views
Mathematical formulation of an optimization problem
I have the following optimization problem at hand.
There are N integer numbers, $a_{i},a_{i+1},\dots,a_{n}$ where $a_{i} > 0$.
We need to partition these numbers ...
3
votes
1answer
58 views
Any nice/good way to allow an “or” option in a linear program?
I am looking for a way to express an "or" option in a system of linear inequalities for a linear program I am working on.
I will explain what I mean precisely: Lets say I have a set of ...
0
votes
1answer
25 views
If Else Statement in Linear Program, making it Mixed Integer Program [closed]
How to write the following if-else condition in Linear Programming or in Mixed Integer Program?
If a <= b then c = a
else ( a > b) then c = b
a, b, c are all variables. Is it possible to rewrite ...
0
votes
0answers
21 views
How to write hard ILP problem?
I want to write/create hard ILP problems. When I say hard I mean the question should be solvable in at least 20 minutes with non-commercial ILP solvers. Can someone show me a direction or know how to ...
-2
votes
1answer
31 views
linearizing non-strict inequality If.. else conditional constraint that includes decision variables
I would like to linearize a conditional constraint as follow:
0 <= x1 <= 1.
If 0 <= x1 < 1, then x2 = 1, else x2 = 0.
I find it very difficult because it is not a typical If...then ...
1
vote
1answer
32 views
Linear/Integer Programming: Scheduling task with regular intervals
Given is the following problem: There are $N$ items that have to be processed in given intervals over a year. For example, item $i_1$ is processed about every 14 days, item $i_2$ is processed monthly. ...
1
vote
1answer
59 views
Chance-Constrained Optimization
Let $x \in \mathbb{R}^n$ and $\xi \in \Xi \subset \mathbb{R}^n$ be a random vector with discrete probability distribution $p(\cdot)$, assuming a finite number of values $\{\xi_i\}_{i = 1}^S$. Let $A \...
0
votes
2answers
38 views
Assigning tasks to minimize cost
I have a set of jobs that must be done on a given day in sequence. $J_1, J_2, J_3$, with deadlines $D_1, D_2, D_3$. There are three workers $W_1, W_2, W_3$ that can execute the tasks each one with ...
1
vote
1answer
40 views
Multilevel integer programming
Recently, I have been dealing with an integer program that involves finding a $4$-level integral solution
$$x \in \{-2, -1, 1, 2\}$$
or even $x \in \{\pm n, \pm n-1, \dots, \pm 1\}$ which is ...
1
vote
2answers
98 views
Linearizing the product of a binary and a continuous variable
I have an MIP optimization problem that has a constraint $p\geq xy$, where $x$ is a binary variable, $p$ and $y$ are non-negative continuous variables.
I tried the Big-M method. However, the upper ...
1
vote
1answer
59 views
Linearize objective function for intlinprog
This is the predecessor to the following question:
I have some constraints based on which I have written a Matlab program that provides me some feasible binary bits for Finite state machines(FSM). ...
1
vote
1answer
75 views
Formulating Constraints into Mixed-Integer Linear Programming
Is there a way to formulate the following Linear Program in a mixed-integer LP that I could solve with most linear programs in R/Python that support Mixed Integer Linear Programs (MILP)?
So my ...
1
vote
1answer
26 views
possible bin packing question
what is known: you are given 3 packs of boards of different lengths. ie pack A is 3.9m, B is 3m and C 2.4m and an arbitrary distance to cover, d. how do I pose and then solve this question?
3.9A + 3B ...
0
votes
2answers
48 views
Modeling following constraints in MILP
I want to know how I should formulate the following constraints in my MIP problem?
$$x= x_1 z_1+ \dots +x_n z_n \text{ and }
y_1 \le y \le y_n \text{ and }
z_1+\dots+z_n=1$$
OR
$$y= y_1 w_1+\...
0
votes
0answers
32 views
Why For any integer point in the feasible region the right side of this equation is less than 1 and the left side is an integer?
I wanted to find Why Gomory's cut works. wikipedia Gomory's cut explains:
An integer programming problem be formulated (in Standard Form) as:
\begin{aligned}{\text{Maximize }}&c^{T}x\\{\text{...
0
votes
1answer
42 views
Linear programming formulation confusion
I have a silly confusion.
For this constraint here, $a_{i1,j1} + a_{i2,j2} ≤ 1$ if $0 < |i1−i2|+|j1−j2| < d$.
I understand this constraint but I want to ensure that this encompasses all $i$ ...
1
vote
1answer
41 views
Modeling problem (of Operational Research)
Consider a logistics system consisting of $n$ production sites and $m$ warehouses. For a given product, the monthly production capacity of the production sites is $p_i$ units, with $i = 1,\dots, n$. ...
0
votes
1answer
30 views
Are all mixed integer nonlinear problems non-convex? If not, is my problem non-convex? And what solvers can we use?
My apologies for asking (basic) questions on mixed-integer nonlinear problems.
Question 1: Are all mixed-integer nonlinear problems non-convex? If not, why do people say it is very hard to solve it? ...
1
vote
2answers
90 views
How to relax logical constraints
Consider two $m\times 1$ vectors, $x\equiv (x_1,x_2,...,x_m),\tilde{x}\equiv (\tilde{x}_1,\tilde{x}_2,...,\tilde{x}_m)$.
Let $x\leq \tilde{x}$ if and only if $x_i\leq \tilde{x}_i$ for each $i=1,...,m$....
0
votes
0answers
40 views
How can I solve this nonlinear-projection optimization problem?
How can I solve this nonlinear projection problem?
Can you give me any idea?
Constraints are as shown in the image.
The norm can be anyone.
Variables : $z_1,\;z_2,\;\underline{x}\in\mathbb{R}^d,\;\...
