Questions tagged [linear-programming]
Optimization with a linear objective function, subject to linear equality and linear inequality constraints.
237 questions
2
votes
0answers
11 views
Relaxations for MILP with logical constraints
I have an LP with a (non-fixed) number of logical constraints in the form of $X_1 \rightarrow X_2$ (where $X_1$ and $X_2$ are linear functions inequalities of the $n$ input variables). To express ...
5
votes
0answers
61 views
+50
Solving an LP with at most m-1 nonzeros
Consider the linear program:
$$
A x = b, ~~~~~~ x\geq 0
$$
where $A$ is an $m$-by-$n$ matrix, $x$ is an $n$-by-1 vector, $b$ is an $m$-by-1 vector, and $m<n$.
It is known that, if this ...
0
votes
0answers
12 views
Given a set of solutions, find an IP formulation with the same solution set
Input:
A list of integer variables $x_1, ..., x_n$.
A finite set of feasible solutions $S \subset \mathbb{Z}^n$.
Task:
Find an integer linear program (IP) on the integer variables $x_1,...,x_n$ ...
1
vote
0answers
33 views
7
votes
2answers
124 views
Reducing linear programming to positive linear programming
Suppose we have an oracle that solves problems of the form
\begin{align*}
\text{maximize} ~~ & c^T x
\\
\text{subject to} ~~ & A x = b, x\geq 0
\end{align*}
when $c\geq 0$ (all coefficients ...
0
votes
0answers
26 views
Branch and bound Dual Gap
Let's suppose we want to solve the knapsack problem using the Branch and Bound algorithm.
I know that the algorithm ends when the optimality gap is = 0. However i have not understood how the dual ...
0
votes
0answers
15 views
How to formulate initial costs in linear programming?
Consider this example problem:
Suppose the cost for setting up a factory to generate a pencil is 1000 and to generate a pen is 2000. The profit for each pencil is 10 and the profit for each pen is 12....
0
votes
1answer
23 views
How to formulate constraints in zero-one linear programming
There is a factory which produces 5 types of ice cream. If the $i_{th}$ ice cream is produced then $b_i=1$ otherwise $b_i=0$
How can I express the following constraints:
The simultaneous production ...
0
votes
1answer
28 views
Complexity of linear programming with restricted quadratic constraints
A problem instance is a linear program with the following kind of quadratic inequalities allowed: For some of the variables $x_i$, there is a variable $s_i$ (intuitively for approximating $x_i^2$, and ...
-1
votes
0answers
9 views
Integer Linear Programming Branch and Bound: Bounding criteria
I'm studying the branch and bound algorithm to solve an integer linear programming problem. Suppose to have the following problem in standard form:
$ (ILP) \ \min z(x) \\ s.t. \\ Ax = b \\ x \ge 0 \...
0
votes
0answers
14 views
Reducing weighted linear threshold gate to unweighted one
Reading "On the power of threshold circuits with small weights" by Siu and Bruck I have faced several problems understanding how unweighted linear threshold element can be built efficiently from the ...
1
vote
0answers
28 views
Big M method for continuous variables
Is there any way to model the big M method for continuous variables?
Something similar to this but $B, C \in \mathbb{R}_{\geq 0}$ and $A\in\{0,1\}$.
Due to the precision problem, when the $B$ and $C$ ...
1
vote
0answers
17 views
(M)ILP overlap of two intervals
I got an ILP Model where $c_i$ represents the starting time for a visit$_i$.
$c_i$ is already constraint by a number of constraints, one is $c_i > 0$.
I have now outside of my model 0 or multiple ...
-1
votes
0answers
35 views
Comparison between SAT, SMT, LP and CSP
How to know which method is better for modelling and solving a problem. I am generally asking about solving a problem as a satisfiability problem (SAT or SMT) vs. Solving as a linear programming ...
2
votes
1answer
113 views
What is the right term/theory for prediction of Binary Variables based upon their continuous value?
I am working with a linear programming problem in which we have around 3500 binary variables.
Usually IBM's Cplex takes around 72 hours to get an objective with a gap of around 15-20% with best ...
1
vote
1answer
38 views
LP Relaxation of Maximum Coverage Problem
So I know from some research I've done that the OPT-IP <= OPT-LP for the maximum coverage problem, however I'm having some difficulty following the explanations I find. Does an example exist where ...
-1
votes
0answers
28 views
How to convert the result of a linear program in to graph path?
I would like to know how can I convert the result of a linear program into a graph path.
For example, I am using CPLEX in Python to solve multicommodity flow problems, where it assigns a portion of ...
0
votes
0answers
6 views
How to understand the separation phrase for generalized subtour constraints?
Suppose the constraints of our integer programming model consist of two parts:
the polynomial-size formulations, that have a size (number of variables and constraints) which is polynomial w.r.t. the ...
0
votes
0answers
11 views
Algorithm for laying out grids (html-like tables) with row/column spans
This problem should have the same solution for the horizontal as well as for the vertical, so I'll only present the horizontal case. Consider the following layout with 3 columns, 3 rows and 2 column ...
0
votes
1answer
37 views
How to write an if then logical constraint given part of the input related to a decision variable?
I am trying to solve an assignment problem-like from a bi-objective persepctive where I have a marketplace of vendors proposing different machines with different types and specs. The goal is to select ...
2
votes
3answers
42 views
Need Help Understanding MST Cutset Formulation
I just started learning about linear programming in my class, and I'm having some trouble understanding the MST Formulation Integer Linear Programming (Cutset Formulation).
This is the definition:
...
0
votes
0answers
10 views
LIP - Minimum Spanning Tree Cutset Formulation [duplicate]
I just started learning about linear programming in my class, and I'm having some trouble understanding the MST Formulation Integer Linear Programming (Cutset Formulation).
This is the definition:
$...
1
vote
0answers
54 views
maximizing absolute value in linear programming
I know that similar questions have been answered several times, and based on the answers, I attempted a solution to my problem. But I simply do not get the right results. The problem is as follows. I ...
2
votes
1answer
19 views
Positioning items to maximize separation
Say we want to place n items on the real line. Let us denote the position of item i by $p_i$. We have interval constraints on the position $p_i$, i.e. we are given $l_i, r_i$ such that $l_i \le p_i \...
1
vote
0answers
10 views
Sparse feasible solution $|x|_0\le k$ for system of linear inequalities $A x \le b$
Suppose the set of linear inequalities $Ax\le b$, in which $A\in\mathbb{R}^{m\times n},x,b\in\mathbb{R}^n$ is given. Is it possible to determine in polynomial time with regard to $m$ and $n$ if there ...
3
votes
1answer
47 views
Is there an algorithm that can find a solution that solves the most number of equations in a linear system of equations?
My apologies if this question makes no sense. I am trying to find an algorithm that can solve a linear system of equations. Unlike most problems like this, this algorithm does not need to find a ...
1
vote
1answer
56 views
A simple way to find the feasible region of a system with simple constraints
I'm coding something... weird, and I'm running into some constraint satisfaction and graph theory problems, which are fields I'm not too experienced in. Here's the problem:
I start out with this ...
2
votes
0answers
61 views
Implementing a linear programming feasibility test in 3D
I have a little problem which requires determining if a system of linear inequalities in 3D is infeasible. The constraints (or oriented planes) are added one by one, so there is an opportunity to stop ...
1
vote
2answers
38 views
Better way to formulate these constraints?
I have a binary variable $x_{ijt}^k$ that is $1$ iff job $i$ is assigned to machine $j$ at time $t$ using processor $k$. I would like to express the following constraints:
If job $i$ is assigned to ...
0
votes
1answer
52 views
Conditional milp formulation
I have two binaries, $\alpha_{ts,it}$ and $\alpha_{ts,gshp} \in \{0,1\} $, and two reals $T_{it}$ and $T_{ts}$ which have upper and lower bounds. How can I model $\alpha_{ts,it}=1$ if the following ...
1
vote
0answers
56 views
Can somebody suggest what is wrong with these constraint? [closed]
I have written two constraints for Mixed integer linear problem. I am working on the scheduling problem i.e., Scheduling of hybrid appliances.
For example, the washing machine is appliance indicated ...
1
vote
2answers
44 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 ...
5
votes
1answer
66 views
How does cycling happen in the simplex method?
I'm reading Schrijver's Theory of Linear and Integer Programming, and I have a problem understanding cycling happens in the simplex method. The simplex is described as below:
Solving $\max\{cx\mid x \...
0
votes
0answers
28 views
Does floor and ceiling in LP implies more than $P=NP$?
We know ability to take floor and ceiling in Linear Programming (LP) implies $P=NP$ (just apply floor and ceiling to variable in $(0,2)$ to get binary variable and from this it follows $0/1$ ...
0
votes
1answer
35 views
Can we split a vector into positive and negative parts in LP?
Say you have a vector $v$ with $n$ length $v=\begin{bmatrix}v_1&\dots&v_{n}\end{bmatrix}$ can we write as $v=v_+-v_-$ where $v_+$ agrees with $v$ on non-negative components and is $0$ ...
1
vote
1answer
35 views
Find coverage for plane from half-planes
The document (see pic. below) states that it is possible to find a cover of the plane by a subset of 3 half-planes. It proposes to use linear programming for this. How to formulate such a program?
...
1
vote
0answers
43 views
How to solve this optimization problem with logarithmic objective function?
I have this optimization problem
I have no idea how to solve it. Is Lagrange suitable for this problem?
Thank you
0
votes
0answers
34 views
mLP to mAGTSP formulation
In the paper Scheduling Twin Yard Cranes in a Container Block authors provide a mILP to solve scheduling twin cranes to execute requests in a block at a seaport to minimize makespan of the cranes. ...
0
votes
0answers
59 views
Is $P\neq NP\iff 3SAT$ not reducible to LP?
If $3SAT$ in $n$ variable and $m$ clauses reduces to LP with $O((nm)^c)$ variables and $O((nm)^c)$ constraints at a fixed $c$ then $P=NP$.
Conversely if $P=NP$ then does $3SAT$ in $n$ variable and $m$...
1
vote
1answer
34 views
Fractional vertex cover number may not be feasible? Very confusing!
For my project, I try to use minimum fractional vertex cover number (MFVC). (Please find below definition details) MFVC can be formulated as optimal solution of a linear program relaxation.
However I ...
0
votes
1answer
54 views
How do you proceed if your milp is not solvable
We are currently developing an ilp/milp model to fit the best routes with given resources (people) in a given timeframe and given visits and costs to travel from one visit to another (asymetrical).
...
0
votes
0answers
38 views
On a condition in real linear programming
For me $a,x,y\in(0,1]$ and I want to select $b=x$ if $a\leq0.5$ or else I want $b=y$.
Is it possible to set this condition in real linear program?
-1
votes
1answer
64 views
Can we use ILP here?
Is it possible to encode $y=0\implies G=0$ else $G=x$ by Integer Linear Programming where $x,y,G$ are integer variables?
The answer mentioned below gets to the point of taking absolute value of ...
-1
votes
1answer
185 views
On if then condition in linear programming?
I have variables $a,b\in\mathbb R$ and if $a>1$ I want $b=1$ or else $b=0$.
Can this be encoded by linear programming (no integer variables)? Even $b<0.5$ and $b>0.5$ is ok.
0
votes
0answers
37 views
Linear Programming if-then-else [duplicate]
I have a binary variable $y\ \epsilon\ \{0,1\} $ and a real $x$ which has the following boundaries $-100\leq\ x \leq\ 100$. How can I reformulate the following statement:
$$
y =
\begin{cases}
0 & ...
3
votes
2answers
204 views
How to check if a specific ILP problem can be solved in polynomial time or not?
How can we know that a specific ILP problem is solvable in polynomial time or not given the constraints?
2
votes
1answer
544 views
Why is integer programming more difficult than (real) linear programming? [duplicate]
Why is integer programming (IP) more difficult than (real) linear programming (LP)?
I searched a lot on the web, but I didn't find an answer.
1
vote
0answers
272 views
Restriction for greater than constraint in linear programming
I have a model that considers real values and that uses a binary variable $x$. In this model, the following conditions should apply:
\begin{equation}
x=
\begin{cases}
0, & \text{if}\...
2
votes
1answer
173 views
Bipartite Perfect Matching “Assignment Problem” - finding an assignment of a particular weight
The assignment problem is to find the minimum weight perfect matching in a weighted bipartite graph. This problem can be solved using the Hungarian algorithm in polynomial time. It is also possible to ...
7
votes
1answer
423 views
How to find the supremum over all the “good” (interior) polytopes for a given set of 3D points?
Let $S \subset \mathbf{R}^3$ be a set of points in 3D and let $O=(x_0,y_0,z_0)$ be the origin/point of reference.
We consider a convex polytope $P$ good / interior if:
$P$ is wholly contained ...
