Questions tagged [linear-programming]

Optimization with a linear objective function, subject to linear equality and linear inequality constraints.

Filter by
Sorted by
Tagged with
0
votes
1answer
32 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 ...
0
votes
0answers
20 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
49 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
1answer
61 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 ...
2
votes
1answer
128 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
132 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 ...
0
votes
0answers
13 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
1answer
136 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
126 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
20 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
151 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
26 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
21 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 ...
4
votes
1answer
52 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
203 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
64 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
42 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
85 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
59 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
46 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 ...
6
votes
1answer
275 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
1answer
43 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
41 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
82 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
1
vote
1answer
36 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
75 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). ...
-1
votes
1answer
68 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
423 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
42 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
298 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
1k 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
533 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
306 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 ...
6
votes
1answer
436 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 ...
0
votes
0answers
62 views

How to model an ''affinity constraint'' in assignment problem

Working on an optimization problem formulated using the well known assignment problem. My decision variable is defined as follows : $$\alpha _{x}^{r,u} = 1\begin{cases} & \text{ 1 if } \mathbf{...
0
votes
0answers
23 views

Problem with formulating LP problem using binary variables

I have a problem with a task shown below. I have I am supposed to use big M method, but I don't know how to estimate/compute the minimal value of it and how to implement it into the equations. Any ...
2
votes
1answer
122 views

Converting nested absolute value into linear programming

I am having trouble writing the following optimization problem as a linear program (LP) $$\min_{x \in \mathbb R^2} \big| | x_{1} - a_{1} | - | x_{2} - a_{2} | \big|$$ where $a \in \mathbb Z^2$ is ...
1
vote
1answer
34 views

Example of $c^Tx' = c^Tx$ where x is the optimal solution for the linear relaxation (LP) of x' (ILP)

I am looking for an example where the optimal solution for the LP problem is equal to the optimal solution of the ILP problem, but the solutions are different. All I managed to think of was the ...
0
votes
1answer
13 views

Relating indexes for parameters and variables

I am trying to solve a referee assignment problem, but I simply can't think of a way to relate my variable to one of the parameters, and I hope that someone in here can help. I have the following ...
1
vote
0answers
163 views

LP realaxation for multicut problem with polynomial number of constraints

The integer linear programming formulation for the multicut problem for the given graph $G = (V,E)$ and distinguished source-sink pairs of vertices $(s_1,t_1),...,(s_k,t_k)$ is: \begin{alignat}{3} \...
1
vote
1answer
86 views

Can LP for matroid polytopes be solved using the greedy algorithm?

For general linear programming (LP), i.e. optimization of a linear objective over a general polyhedron, to the best of my knowledge/recollection one can use the simplex algorithm (or hypothetically, ...
2
votes
1answer
469 views

Questions about Amdahl's law?

Doing exam papers now and I came across two questions which I cannot get my head around sadly. Both are regarding Amdahl's law and Parallel Computing but they seem rather simple and frustratingly ...
1
vote
0answers
34 views

Time complexity bounds for the approximation of optimal values of bounded linear programs

Assume we are given a LP maximization problem defined by a linear functional $c^Tx$ and a non-empty feasible region $\{x:Ax\leq b\}$ that is known to be bounded by a hypercube of side $R>0$, say $[...
0
votes
1answer
259 views

Converting between (standard) primal to dual forms (LP)

I'm working on a HW assignment as follows: Given the primal canonical problem: $$min \langle c,x \rangle \text{ s.t. } Ax \geq b, x \geq 0$$ and the canonical dual problem: $$ max \langle b,y \rangle ...
2
votes
1answer
55 views

Maximize the number of edges in subgraph

We are given a graph $G=(V,E)$ and we want an algorithm to find a set of vertices $U$ to maximize the following quantity : $\frac{|E(U)|}{|U|}$ where $E(U)$ denotes the number of edges in the subgraph ...
0
votes
1answer
203 views

LP formulation and integer solution existance

I’m trying to prove that the following problem has an integer optimal solution. This will hold if the corresponding linear program would have totally unimodular constraint matrix. We have $m$ pieces ...
0
votes
1answer
40 views

Why is the target function minimized at (0,0) if I can get to a negative number?

I just started learning LP and I saw this Q in my textbook: $$ min : -x -y \\ S.T. : x + 2y \le 3, 2x +y \le 3, x \ge 0, y \ge 0 $$ It is easy to see that the polygon created from these constraints ...
1
vote
1answer
358 views

Finding integrality gap for maximum weight independent set

One of the exercises I was given was to formulate Integer Linear Program (ILP) and relaxed version of it (LP) to solve the maximum weight independent set, and I need to find an integrality gap of my ...
0
votes
1answer
61 views

Objective function and constraint satisfaction over a set of multi-attributes elements

I'm looking for an approach to solve a problem consisting of maximizing an objective function over a set of discrete elements, while respecting a set of constraints. To illustrate my point, I'll try ...
1
vote
1answer
47 views

Simplex Algorithm: Why must the optimal value of the LP lie on the face or vertex of a polyhedron?

The feasible region of a Linear Program (LP) is $\{x \in {\bf R}^n: Ax \le b, x\ge 0 \}$. This is an intersection of halfspaces, a polyhedron. If the LP is bounded and feasible, its optimal value will ...